1 #import "ArrayIterator.h" 2 3 @class LinkedList; 4 5 /** 6 * LinkedList entry. 7 */ 8 9 @interface LLNode : NSObject 10 { 11 LLNode *next; 12 LLNode *prev; 13 id item; 14 } 15 16 @property(retain) LLNode *next; 17 @property(retain) LLNode *prev; 18 @property(retain) id item; 19 20 + (LLNode *) newNode:(LLNode *)aPrev element:(id)anElement next:(LLNode *)aNext; 21 22 - (id) init:(LLNode *)aPrev element:(id)anElement next:(LLNode *)aNext; 23 - (void) dealloc; 24 @end 25 26 @interface ListIterator : ArrayIterator { 27 LLNode * lastReturned; 28 LLNode * next; 29 NSInteger nextIndex; 30 NSInteger expectedModCount; 31 LinkedList *ll; 32 } 33 34 + (ListIterator *) newIterator:(LinkedList *)anLL; 35 + (ListIterator *) newIterator:(LinkedList *)anLL withIndex:(NSInteger)anIndex; 36 37 - (id) init:(LinkedList *)anLL withIndex:(NSInteger)anIndex; 38 - (BOOL) hasNext; 39 - (LLNode *) next; 40 - (BOOL) hasPrevious; 41 - (LLNode *) previous; 42 - (NSInteger) nextIndex; 43 - (NSInteger) previousIndex; 44 - (void) remove; 45 - (void) set:(LLNode *)e; 46 - (void) add:(LLNode *)e; 47 - (void) checkForComodification; 48 @end 49 50 /** 51 * Adapter to provide descending iterators via ListItr.previous 52 */ 53 54 @interface DescendingIterator : ListIterator { 55 } 56 57 + (DescendingIterator *) newIterator:(LinkedList *)anLL; 58 - (id) init:(LinkedList *)anLL; 59 - (BOOL) hasNext; 60 - (LLNode *) next; 61 - (void) remove; 62 - (void) dealloc; 63 @end 64 65 /** 66 * Doubly-linked list implementation of the {@code List} and {@code Deque} 67 * interfaces. Implements all optional list operations, and permits all 68 * elements (including {@code null}). 69 * 70 * <p>All of the operations perform as could be expected for a doubly-linked 71 * list. Operations that index into the list will traverse the list from 72 * the beginning or the end, whichever is closer to the specified index. 73 * 74 * <p><strong>Note that this implementation is not synchronized.</strong> 75 * If multiple threads access a linked list concurrently, and at least 76 * one of the threads modifies the list structurally, it <i>must</i> be 77 * synchronized externally. (A structural modification is any operation 78 * that adds or deletes one or more elements; merely setting the value of 79 * an element is not a structural modification.) This is typically 80 * accomplished by synchronizing on some object that naturally 81 * encapsulates the list. 82 * 83 * If no such object exists, the list should be "wrapped" using the 84 * {@link Collections#synchronizedList Collections.synchronizedList} 85 * method. This is best done at creation time, to prevent accidental 86 * unsynchronized access to the list:<pre> 87 * List list = Collections.synchronizedList(new LinkedList(...));</pre> 88 * 89 * <p>The iterators returned by this class's {@code iterator} and 90 * {@code listIterator} methods are <i>fail-fast</i>: if the list is 91 * structurally modified at any time after the iterator is created, in 92 * any way except through the Iterator's own {@code remove} or 93 * {@code add} methods, the iterator will throw a {@link 94 * ConcurrentModificationException}. Thus, in the face of concurrent 95 * modification, the iterator fails quickly and cleanly, rather than 96 * risking arbitrary, non-deterministic behavior at an undetermined 97 * time in the future. 98 * 99 * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed 100 * as it is, generally speaking, impossible to make any hard guarantees in the 101 * presence of unsynchronized concurrent modification. Fail-fast iterators 102 * throw {@code ConcurrentModificationException} on a best-effort basis. 103 * Therefore, it would be wrong to write a program that depended on this 104 * exception for its correctness: <i>the fail-fast behavior of iterators 105 * should be used only to detect bugs.</i> 106 * 107 * <p>This class is a member of the 108 * <a href="{@docRoot}/../technotes/guides/collections/index.html"> 109 * Java Collections Framework</a>. 110 * 111 * @author Josh Bloch 112 * @see List 113 * @see ArrayList 114 * @since 1.2 115 * @param <E> the type of elements held in this collection 116 */ 117 118 @interface LinkedList : NSObject { 119 /** 120 * Pointer to first node. 121 * Invariant: (first == null && last == null) || 122 * (first.prev == null && first.item != null) 123 */ 124 LLNode *first; 125 126 /** 127 * Pointer to last node. 128 * Invariant: (first == null && last == null) || 129 * (last.next == null && last.item != null) 130 */ 131 LLNode *last; 132 NSInteger count; 133 NSInteger modCount; 134 } 135 136 @property(nonatomic, retain) LLNode *first; 137 @property(nonatomic, retain) LLNode *last; 138 @property(assign) NSInteger count; 139 @property(assign) NSInteger modCount; 140 141 + (LinkedList *)newLinkedList; 142 + (LinkedList *)newLinkedList:(NSArray *)c; 143 144 - (id) init; 145 - (id) initWithC:(NSArray *)c; 146 - (void) linkLast:(LLNode *)e; 147 - (void) linkBefore:(LLNode *)e succ:(LLNode *)succ; 148 - (LLNode *) unlink:(LLNode *)x; 149 - (LLNode *) removeFirst; 150 - (LLNode *) removeLast; 151 - (void) addFirst:(LLNode *)e; 152 - (void) addLast:(LLNode *)e; 153 - (BOOL) contains:(id)o; 154 - (NSInteger) count; 155 - (BOOL) add:(LLNode *)e; 156 - (BOOL) remove:(id)o; 157 - (BOOL) addAll:(NSArray *)c; 158 - (BOOL) addAll:(NSInteger)index c:(NSArray *)c; 159 - (void) clear; 160 - (LLNode *) get:(NSInteger)index; 161 - (LLNode *) set:(NSInteger)index element:(LLNode *)element; 162 - (void) add:(NSInteger)index element:(LLNode *)element; 163 - (LLNode *) removeIdx:(NSInteger)index; 164 - (void) checkElementIndex:(NSInteger)index; 165 - (void) checkPositionIndex:(NSInteger)index; 166 - (LLNode *) node:(NSInteger)index; 167 - (NSInteger) indexOf:(id)o; 168 - (NSInteger) lastIndexOf:(id)o; 169 - (LLNode *) peek; 170 - (LLNode *) element; 171 - (LLNode *) poll; 172 - (LLNode *) remove; 173 - (BOOL) offer:(LLNode *)e; 174 - (BOOL) offerFirst:(LLNode *)e; 175 - (BOOL) offerLast:(LLNode *)e; 176 - (LLNode *) peekFirst; 177 - (LLNode *) peekLast; 178 - (LLNode *) pollFirst; 179 - (LLNode *) pollLast; 180 - (void) push:(LLNode *)e; 181 - (LLNode *) pop; 182 - (BOOL) removeFirstOccurrence:(id)o; 183 - (BOOL) removeLastOccurrence:(id)o; 184 - (ListIterator *) listIterator:(NSInteger)index; 185 - (NSEnumerator *) descendingIterator; 186 - (id) copyWithZone:(NSZone *)zone; 187 - (NSArray *) toArray; 188 - (NSArray *) toArray:(NSArray *)a; 189 @end 190