| #import "ArrayIterator.h" |
| |
| @class LinkedList; |
| |
| /** |
| * LinkedList entry. |
| */ |
| |
| @interface LLNode : NSObject |
| { |
| LLNode *next; |
| LLNode *prev; |
| id item; |
| } |
| |
| @property(retain) LLNode *next; |
| @property(retain) LLNode *prev; |
| @property(retain) id item; |
| |
| + (LLNode *) newNode:(LLNode *)aPrev element:(id)anElement next:(LLNode *)aNext; |
| |
| - (id) init:(LLNode *)aPrev element:(id)anElement next:(LLNode *)aNext; |
| - (void) dealloc; |
| @end |
| |
| @interface ListIterator : ArrayIterator { |
| LLNode * lastReturned; |
| LLNode * next; |
| NSInteger nextIndex; |
| NSInteger expectedModCount; |
| LinkedList *ll; |
| } |
| |
| + (ListIterator *) newIterator:(LinkedList *)anLL; |
| + (ListIterator *) newIterator:(LinkedList *)anLL withIndex:(NSInteger)anIndex; |
| |
| - (id) init:(LinkedList *)anLL withIndex:(NSInteger)anIndex; |
| - (BOOL) hasNext; |
| - (LLNode *) next; |
| - (BOOL) hasPrevious; |
| - (LLNode *) previous; |
| - (NSInteger) nextIndex; |
| - (NSInteger) previousIndex; |
| - (void) remove; |
| - (void) set:(LLNode *)e; |
| - (void) add:(LLNode *)e; |
| - (void) checkForComodification; |
| @end |
| |
| /** |
| * Adapter to provide descending iterators via ListItr.previous |
| */ |
| |
| @interface DescendingIterator : ListIterator { |
| } |
| |
| + (DescendingIterator *) newIterator:(LinkedList *)anLL; |
| - (id) init:(LinkedList *)anLL; |
| - (BOOL) hasNext; |
| - (LLNode *) next; |
| - (void) remove; |
| - (void) dealloc; |
| @end |
| |
| /** |
| * Doubly-linked list implementation of the {@code List} and {@code Deque} |
| * interfaces. Implements all optional list operations, and permits all |
| * elements (including {@code null}). |
| * |
| * <p>All of the operations perform as could be expected for a doubly-linked |
| * list. Operations that index into the list will traverse the list from |
| * the beginning or the end, whichever is closer to the specified index. |
| * |
| * <p><strong>Note that this implementation is not synchronized.</strong> |
| * If multiple threads access a linked list concurrently, and at least |
| * one of the threads modifies the list structurally, it <i>must</i> be |
| * synchronized externally. (A structural modification is any operation |
| * that adds or deletes one or more elements; merely setting the value of |
| * an element is not a structural modification.) This is typically |
| * accomplished by synchronizing on some object that naturally |
| * encapsulates the list. |
| * |
| * If no such object exists, the list should be "wrapped" using the |
| * {@link Collections#synchronizedList Collections.synchronizedList} |
| * method. This is best done at creation time, to prevent accidental |
| * unsynchronized access to the list:<pre> |
| * List list = Collections.synchronizedList(new LinkedList(...));</pre> |
| * |
| * <p>The iterators returned by this class's {@code iterator} and |
| * {@code listIterator} methods are <i>fail-fast</i>: if the list is |
| * structurally modified at any time after the iterator is created, in |
| * any way except through the Iterator's own {@code remove} or |
| * {@code add} methods, the iterator will throw a {@link |
| * ConcurrentModificationException}. Thus, in the face of concurrent |
| * modification, the iterator fails quickly and cleanly, rather than |
| * risking arbitrary, non-deterministic behavior at an undetermined |
| * time in the future. |
| * |
| * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed |
| * as it is, generally speaking, impossible to make any hard guarantees in the |
| * presence of unsynchronized concurrent modification. Fail-fast iterators |
| * throw {@code ConcurrentModificationException} on a best-effort basis. |
| * Therefore, it would be wrong to write a program that depended on this |
| * exception for its correctness: <i>the fail-fast behavior of iterators |
| * should be used only to detect bugs.</i> |
| * |
| * <p>This class is a member of the |
| * <a href="{@docRoot}/../technotes/guides/collections/index.html"> |
| * Java Collections Framework</a>. |
| * |
| * @author Josh Bloch |
| * @see List |
| * @see ArrayList |
| * @since 1.2 |
| * @param <E> the type of elements held in this collection |
| */ |
| |
| @interface LinkedList : NSObject { |
| /** |
| * Pointer to first node. |
| * Invariant: (first == null && last == null) || |
| * (first.prev == null && first.item != null) |
| */ |
| LLNode *first; |
| |
| /** |
| * Pointer to last node. |
| * Invariant: (first == null && last == null) || |
| * (last.next == null && last.item != null) |
| */ |
| LLNode *last; |
| NSInteger count; |
| NSInteger modCount; |
| } |
| |
| @property(nonatomic, retain) LLNode *first; |
| @property(nonatomic, retain) LLNode *last; |
| @property(assign) NSInteger count; |
| @property(assign) NSInteger modCount; |
| |
| + (LinkedList *)newLinkedList; |
| + (LinkedList *)newLinkedList:(NSArray *)c; |
| |
| - (id) init; |
| - (id) initWithC:(NSArray *)c; |
| - (void) linkLast:(LLNode *)e; |
| - (void) linkBefore:(LLNode *)e succ:(LLNode *)succ; |
| - (LLNode *) unlink:(LLNode *)x; |
| - (LLNode *) removeFirst; |
| - (LLNode *) removeLast; |
| - (void) addFirst:(LLNode *)e; |
| - (void) addLast:(LLNode *)e; |
| - (BOOL) contains:(id)o; |
| - (NSInteger) count; |
| - (BOOL) add:(LLNode *)e; |
| - (BOOL) remove:(id)o; |
| - (BOOL) addAll:(NSArray *)c; |
| - (BOOL) addAll:(NSInteger)index c:(NSArray *)c; |
| - (void) clear; |
| - (LLNode *) get:(NSInteger)index; |
| - (LLNode *) set:(NSInteger)index element:(LLNode *)element; |
| - (void) add:(NSInteger)index element:(LLNode *)element; |
| - (LLNode *) removeIdx:(NSInteger)index; |
| - (void) checkElementIndex:(NSInteger)index; |
| - (void) checkPositionIndex:(NSInteger)index; |
| - (LLNode *) node:(NSInteger)index; |
| - (NSInteger) indexOf:(id)o; |
| - (NSInteger) lastIndexOf:(id)o; |
| - (LLNode *) peek; |
| - (LLNode *) element; |
| - (LLNode *) poll; |
| - (LLNode *) remove; |
| - (BOOL) offer:(LLNode *)e; |
| - (BOOL) offerFirst:(LLNode *)e; |
| - (BOOL) offerLast:(LLNode *)e; |
| - (LLNode *) peekFirst; |
| - (LLNode *) peekLast; |
| - (LLNode *) pollFirst; |
| - (LLNode *) pollLast; |
| - (void) push:(LLNode *)e; |
| - (LLNode *) pop; |
| - (BOOL) removeFirstOccurrence:(id)o; |
| - (BOOL) removeLastOccurrence:(id)o; |
| - (ListIterator *) listIterator:(NSInteger)index; |
| - (NSEnumerator *) descendingIterator; |
| - (id) copyWithZone:(NSZone *)zone; |
| - (NSArray *) toArray; |
| - (NSArray *) toArray:(NSArray *)a; |
| @end |