ViewVC Help

View File | Revision Log | Show Annotations | Download File | Root Listing

root/jsr166/jsr166/src/main/java/util/LinkedList.java

Comparing jsr166/src/main/java/util/LinkedList.java (file contents):
Revision 1.49 by jsr166, Sun May 18 23:59:57 2008 UTC vs.
Revision 1.50 by jsr166, Sat Jan 9 07:06:40 2010 UTC

#	Line 26 | Line 26
26		package java.util;
27
28		/**
29	<	* Linked list implementation of the <tt>List</tt> interface.  Implements all
29	>	* Linked list implementation of the {@code List} interface.  Implements all
30		* optional list operations, and permits all elements (including
31	<	* <tt>null</tt>).  In addition to implementing the <tt>List</tt> interface,
32	<	* the <tt>LinkedList</tt> class provides uniformly named methods to
33	<	* <tt>get</tt>, <tt>remove</tt> and <tt>insert</tt> an element at the
31	>	* {@code null}).  In addition to implementing the {@code List} interface,
32	>	* the {@code LinkedList} class provides uniformly named methods to
33	>	* {@code get}, {@code remove} and {@code insert} an element at the
34		* beginning and end of the list.  These operations allow linked lists to be
35		* used as a stack, {@linkplain Queue queue}, or {@linkplain Deque
36	<	* double-ended queue}. <p>
36	>	* double-ended queue}.
37		*
38	<	* The class implements the <tt>Deque</tt> interface, providing
39	<	* first-in-first-out queue operations for <tt>add</tt>,
40	<	* <tt>poll</tt>, along with other stack and deque operations.<p>
38	>	* <p>The class implements the {@code Deque} interface, providing
39	>	* first-in-first-out queue operations for {@code add},
40	>	* {@code poll}, along with other stack and deque operations.
41		*
42	<	* All of the operations perform as could be expected for a doubly-linked
42	>	* <p>All of the operations perform as could be expected for a doubly-linked
43		* list.  Operations that index into the list will traverse the list from
44	<	* the beginning or the end, whichever is closer to the specified index.<p>
44	>	* the beginning or the end, whichever is closer to the specified index.
45		*
46		* <p><strong>Note that this implementation is not synchronized.</strong>
47		* If multiple threads access a linked list concurrently, and at least
#	Line 58 | Line 58 | package java.util;
58		* unsynchronized access to the list:<pre>
59		*   List list = Collections.synchronizedList(new LinkedList(...));</pre>
60		*
61	<	* <p>The iterators returned by this class's <tt>iterator</tt> and
62	<	* <tt>listIterator</tt> methods are <i>fail-fast</i>: if the list is
61	>	* <p>The iterators returned by this class's {@code iterator} and
62	>	* {@code listIterator} methods are <i>fail-fast</i>: if the list is
63		* structurally modified at any time after the iterator is created, in
64	<	* any way except through the Iterator's own <tt>remove</tt> or
65	<	* <tt>add</tt> methods, the iterator will throw a {@link
64	>	* any way except through the Iterator's own {@code remove} or
65	>	* {@code add} methods, the iterator will throw a {@link
66		* ConcurrentModificationException}.  Thus, in the face of concurrent
67		* modification, the iterator fails quickly and cleanly, rather than
68		* risking arbitrary, non-deterministic behavior at an undetermined
#	Line 71 | Line 71 | package java.util;
71		* <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
72		* as it is, generally speaking, impossible to make any hard guarantees in the
73		* presence of unsynchronized concurrent modification.  Fail-fast iterators
74	<	* throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
74	>	* throw {@code ConcurrentModificationException} on a best-effort basis.
75		* Therefore, it would be wrong to write a program that depended on this
76		* exception for its correctness:   <i>the fail-fast behavior of iterators
77		* should be used only to detect bugs.</i>
#	Line 83 | Line 83 | package java.util;
83		* @author  Josh Bloch
84		* @see     List
85		* @see     ArrayList
86	–	* @see     Vector
86		* @since 1.2
87		* @param <E> the type of elements held in this collection
88		*/
#	Line 92 | Line 91 | public class LinkedList<E>
91		extends AbstractSequentialList<E>
92		implements List<E>, Deque<E>, Cloneable, java.io.Serializable
93		{
94	<	private transient Entry<E> header = new Entry<E>(null, null, null);
95	<	private transient int size = 0;
94	>	transient int size = 0;
95	>
96	>	/**
97	>	* Pointer to first node.
98	>	* Invariant: (first == null && last == null) ||
99	>	*            (first.prev == null && first.item != null)
100	>	*/
101	>	transient Node<E> first;
102	>
103	>	/**
104	>	* Pointer to last node.
105	>	* Invariant: (first == null && last == null) ||
106	>	*            (last.next == null && last.item != null)
107	>	*/
108	>	transient Node<E> last;
109
110		/**
111		* Constructs an empty list.
112		*/
113		public LinkedList() {
102	–	header.next = header.previous = header;
114		}
115
116		/**
#	Line 116 | Line 127 | public class LinkedList<E>
127		}
128
129		/**
130	+	* Links e as first element.
131	+	*/
132	+	private void linkFirst(E e) {
133	+	final Node<E> f = first;
134	+	final Node<E> newNode = new Node<E>(null, e, f);
135	+	first = newNode;
136	+	if (f == null)
137	+	last = newNode;
138	+	else
139	+	f.prev = newNode;
140	+	size++;
141	+	modCount++;
142	+	}
143	+
144	+	/**
145	+	* Links e as last element.
146	+	*/
147	+	void linkLast(E e) {
148	+	final Node<E> l = last;
149	+	final Node<E> newNode = new Node<E>(l, e, null);
150	+	last = newNode;
151	+	if (l == null)
152	+	first = newNode;
153	+	else
154	+	l.next = newNode;
155	+	size++;
156	+	modCount++;
157	+	}
158	+
159	+	/**
160	+	* Inserts element e before non-null Node succ.
161	+	*/
162	+	void linkBefore(E e, Node<E> succ) {
163	+	// assert succ != null;
164	+	final Node<E> pred = succ.prev;
165	+	final Node<E> newNode = new Node<E>(pred, e, succ);
166	+	succ.prev = newNode;
167	+	if (pred == null)
168	+	first = newNode;
169	+	else
170	+	pred.next = newNode;
171	+	size++;
172	+	modCount++;
173	+	}
174	+
175	+	/**
176	+	* Unlinks non-null first node f.
177	+	*/
178	+	private E unlinkFirst(Node<E> f) {
179	+	// assert f == first && f != null;
180	+	final E element = f.item;
181	+	final Node<E> next = f.next;
182	+	f.item = null;
183	+	f.next = null; // help GC
184	+	first = next;
185	+	if (next == null)
186	+	last = null;
187	+	else
188	+	next.prev = null;
189	+	size--;
190	+	modCount++;
191	+	return element;
192	+	}
193	+
194	+	/**
195	+	* Unlinks non-null last node l.
196	+	*/
197	+	private E unlinkLast(Node<E> l) {
198	+	// assert l == last && l != null;
199	+	final E element = l.item;
200	+	final Node<E> prev = l.prev;
201	+	l.item = null;
202	+	l.prev = null; // help GC
203	+	last = prev;
204	+	if (prev == null)
205	+	first = null;
206	+	else
207	+	prev.next = null;
208	+	size--;
209	+	modCount++;
210	+	return element;
211	+	}
212	+
213	+	/**
214	+	* Unlinks non-null node x.
215	+	*/
216	+	E unlink(Node<E> x) {
217	+	// assert x != null;
218	+	final E element = x.item;
219	+	final Node<E> next = x.next;
220	+	final Node<E> prev = x.prev;
221	+
222	+	if (prev == null) {
223	+	first = next;
224	+	} else {
225	+	prev.next = next;
226	+	x.prev = null;
227	+	}
228	+
229	+	if (next == null) {
230	+	last = prev;
231	+	} else {
232	+	next.prev = prev;
233	+	x.next = null;
234	+	}
235	+
236	+	x.item = null;
237	+	size--;
238	+	modCount++;
239	+	return element;
240	+	}
241	+
242	+	/**
243		* Returns the first element in this list.
244		*
245		* @return the first element in this list
246		* @throws NoSuchElementException if this list is empty
247		*/
248		public E getFirst() {
249	<	if (size==0)
249	>	final Node<E> f = first;
250	>	if (f == null)
251		throw new NoSuchElementException();
252	<
128	<	return header.next.element;
252	>	return f.item;
253		}
254
255		/**
#	Line 135 | Line 259 | public class LinkedList<E>
259		* @throws NoSuchElementException if this list is empty
260		*/
261		public E getLast()  {
262	<	if (size==0)
262	>	final Node<E> l = last;
263	>	if (l == null)
264		throw new NoSuchElementException();
265	<
141	<	return header.previous.element;
265	>	return l.item;
266		}
267
268		/**
#	Line 148 | Line 272 | public class LinkedList<E>
272		* @throws NoSuchElementException if this list is empty
273		*/
274		public E removeFirst() {
275	<	return remove(header.next);
275	>	final Node<E> f = first;
276	>	if (f == null)
277	>	throw new NoSuchElementException();
278	>	return unlinkFirst(f);
279		}
280
281		/**
#	Line 158 | Line 285 | public class LinkedList<E>
285		* @throws NoSuchElementException if this list is empty
286		*/
287		public E removeLast() {
288	<	return remove(header.previous);
288	>	final Node<E> l = last;
289	>	if (l == null)
290	>	throw new NoSuchElementException();
291	>	return unlinkLast(l);
292		}
293
294		/**
#	Line 167 | Line 297 | public class LinkedList<E>
297		* @param e the element to add
298		*/
299		public void addFirst(E e) {
300	<	addBefore(e, header.next);
300	>	linkFirst(e);
301		}
302
303		/**
#	Line 178 | Line 308 | public class LinkedList<E>
308		* @param e the element to add
309		*/
310		public void addLast(E e) {
311	<	addBefore(e, header);
311	>	linkLast(e);
312		}
313
314		/**
315	<	* Returns <tt>true</tt> if this list contains the specified element.
316	<	* More formally, returns <tt>true</tt> if and only if this list contains
317	<	* at least one element <tt>e</tt> such that
315	>	* Returns {@code true} if this list contains the specified element.
316	>	* More formally, returns {@code true} if and only if this list contains
317	>	* at least one element {@code e} such that
318		* <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>.
319		*
320		* @param o element whose presence in this list is to be tested
321	<	* @return <tt>true</tt> if this list contains the specified element
321	>	* @return {@code true} if this list contains the specified element
322		*/
323		public boolean contains(Object o) {
324		return indexOf(o) != -1;
#	Line 209 | Line 339 | public class LinkedList<E>
339		* <p>This method is equivalent to {@link #addLast}.
340		*
341		* @param e element to be appended to this list
342	<	* @return <tt>true</tt> (as specified by {@link Collection#add})
342	>	* @return {@code true} (as specified by {@link Collection#add})
343		*/
344		public boolean add(E e) {
345	<	addBefore(e, header);
345	>	linkLast(e);
346		return true;
347		}
348
#	Line 220 | Line 350 | public class LinkedList<E>
350		* Removes the first occurrence of the specified element from this list,
351		* if it is present.  If this list does not contain the element, it is
352		* unchanged.  More formally, removes the element with the lowest index
353	<	* <tt>i</tt> such that
353	>	* {@code i} such that
354		* <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>
355	<	* (if such an element exists).  Returns <tt>true</tt> if this list
355	>	* (if such an element exists).  Returns {@code true} if this list
356		* contained the specified element (or equivalently, if this list
357		* changed as a result of the call).
358		*
359		* @param o element to be removed from this list, if present
360	<	* @return <tt>true</tt> if this list contained the specified element
360	>	* @return {@code true} if this list contained the specified element
361		*/
362		public boolean remove(Object o) {
363	<	if (o==null) {
364	<	for (Entry<E> e = header.next; e != header; e = e.next) {
365	<	if (e.element==null) {
366	<	remove(e);
363	>	if (o == null) {
364	>	for (Node<E> x = first; x != null; x = x.next) {
365	>	if (x.item == null) {
366	>	unlink(x);
367		return true;
368		}
369		}
370		} else {
371	<	for (Entry<E> e = header.next; e != header; e = e.next) {
372	<	if (o.equals(e.element)) {
373	<	remove(e);
371	>	for (Node<E> x = first; x != null; x = x.next) {
372	>	if (o.equals(x.item)) {
373	>	unlink(x);
374		return true;
375		}
376		}
#	Line 257 | Line 387 | public class LinkedList<E>
387		* this list, and it's nonempty.)
388		*
389		* @param c collection containing elements to be added to this list
390	<	* @return <tt>true</tt> if this list changed as a result of the call
390	>	* @return {@code true} if this list changed as a result of the call
391		* @throws NullPointerException if the specified collection is null
392		*/
393		public boolean addAll(Collection<? extends E> c) {
#	Line 275 | Line 405 | public class LinkedList<E>
405		* @param index index at which to insert the first element
406		*              from the specified collection
407		* @param c collection containing elements to be added to this list
408	<	* @return <tt>true</tt> if this list changed as a result of the call
408	>	* @return {@code true} if this list changed as a result of the call
409		* @throws IndexOutOfBoundsException {@inheritDoc}
410		* @throws NullPointerException if the specified collection is null
411		*/
412		public boolean addAll(int index, Collection<? extends E> c) {
413	<	if (index < 0 || index > size)
414	<	throw new IndexOutOfBoundsException("Index: "+index+
285	<	", Size: "+size);
413	>	checkPositionIndex(index);
414	>
415		Object[] a = c.toArray();
416		int numNew = a.length;
417	<	if (numNew==0)
417	>	if (numNew == 0)
418		return false;
290	–	modCount++;
419
420	<	Entry<E> successor = (index==size ? header : entry(index));
421	<	Entry<E> predecessor = successor.previous;
422	<	for (int i=0; i<numNew; i++) {
423	<	Entry<E> e = new Entry<E>((E)a[i], successor, predecessor);
424	<	predecessor.next = e;
425	<	predecessor = e;
420	>	Node<E> pred, succ;
421	>	if (index == size) {
422	>	succ = null;
423	>	pred = last;
424	>	} else {
425	>	succ = node(index);
426	>	pred = succ.prev;
427	>	}
428	>
429	>	for (Object o : a) {
430	>	@SuppressWarnings("unchecked") E e = (E) o;
431	>	Node<E> newNode = new Node<E>(pred, e, null);
432	>	if (pred == null)
433	>	first = newNode;
434	>	else
435	>	pred.next = newNode;
436	>	pred = newNode;
437	>	}
438	>
439	>	if (succ == null) {
440	>	last = pred;
441	>	} else {
442	>	pred.next = succ;
443	>	succ.prev = pred;
444		}
299	–	successor.previous = predecessor;
445
446		size += numNew;
447	+	modCount++;
448		return true;
449		}
450
451		/**
452		* Removes all of the elements from this list.
453	+	* The list will be empty after this call returns.
454		*/
455		public void clear() {
456	<	Entry<E> e = header.next;
457	<	while (e != header) {
458	<	Entry<E> next = e.next;
459	<	e.next = e.previous = null;
460	<	e.element = null;
461	<	e = next;
456	>	// Clearing all of the links between nodes is "unnecessary", but:
457	>	// - helps a generational GC if the discarded nodes inhabit
458	>	//   more than one generation
459	>	// - is sure to free memory even if there is a reachable Iterator
460	>	for (Node<E> x = first; x != null; ) {
461	>	Node<E> next = x.next;
462	>	x.item = null;
463	>	x.next = null;
464	>	x.prev = null;
465	>	x = next;
466		}
467	<	header.next = header.previous = header;
467	>	first = last = null;
468		size = 0;
469		modCount++;
470		}
#	Line 329 | Line 480 | public class LinkedList<E>
480		* @throws IndexOutOfBoundsException {@inheritDoc}
481		*/
482		public E get(int index) {
483	<	return entry(index).element;
483	>	checkElementIndex(index);
484	>	return node(index).item;
485		}
486
487		/**
#	Line 342 | Line 494 | public class LinkedList<E>
494		* @throws IndexOutOfBoundsException {@inheritDoc}
495		*/
496		public E set(int index, E element) {
497	<	Entry<E> e = entry(index);
498	<	E oldVal = e.element;
499	<	e.element = element;
497	>	checkElementIndex(index);
498	>	Node<E> x = node(index);
499	>	E oldVal = x.item;
500	>	x.item = element;
501		return oldVal;
502		}
503
#	Line 358 | Line 511 | public class LinkedList<E>
511		* @throws IndexOutOfBoundsException {@inheritDoc}
512		*/
513		public void add(int index, E element) {
514	<	addBefore(element, (index==size ? header : entry(index)));
514	>	checkPositionIndex(index);
515	>
516	>	if (index == size)
517	>	linkLast(element);
518	>	else
519	>	linkBefore(element, node(index));
520		}
521
522		/**
#	Line 371 | Line 529 | public class LinkedList<E>
529		* @throws IndexOutOfBoundsException {@inheritDoc}
530		*/
531		public E remove(int index) {
532	<	return remove(entry(index));
532	>	checkElementIndex(index);
533	>	return unlink(node(index));
534	>	}
535	>
536	>	/**
537	>	* Tells if the argument is the index of an existing element.
538	>	*/
539	>	private boolean isElementIndex(int index) {
540	>	return index >= 0 && index < size;
541	>	}
542	>
543	>	/**
544	>	* Tells if the argument is the index of a valid position for an
545	>	* iterator or an add operation.
546	>	*/
547	>	private boolean isPositionIndex(int index) {
548	>	return index >= 0 && index <= size;
549	>	}
550	>
551	>	/**
552	>	* Constructs an IndexOutOfBoundsException detail message.
553	>	* Of the many possible refactorings of the error handling code,
554	>	* this "outlining" performs best with both server and client VMs.
555	>	*/
556	>	private String outOfBoundsMsg(int index) {
557	>	return "Index: "+index+", Size: "+size;
558	>	}
559	>
560	>	private void checkElementIndex(int index) {
561	>	if (!isElementIndex(index))
562	>	throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
563	>	}
564	>
565	>	private void checkPositionIndex(int index) {
566	>	if (!isPositionIndex(index))
567	>	throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
568		}
569
570		/**
571	<	* Returns the indexed entry.
571	>	* Returns the (non-null) Node at the specified element index.
572		*/
573	<	private Entry<E> entry(int index) {
574	<	if (index < 0 || index >= size)
575	<	throw new IndexOutOfBoundsException("Index: "+index+
383	<	", Size: "+size);
384	<	Entry<E> e = header;
573	>	Node<E> node(int index) {
574	>	// assert isElementIndex(index);
575	>
576		if (index < (size >> 1)) {
577	<	for (int i = 0; i <= index; i++)
578	<	e = e.next;
577	>	Node<E> x = first;
578	>	for (int i = 0; i < index; i++)
579	>	x = x.next;
580	>	return x;
581		} else {
582	<	for (int i = size; i > index; i--)
583	<	e = e.previous;
582	>	Node<E> x = last;
583	>	for (int i = size - 1; i > index; i--)
584	>	x = x.prev;
585	>	return x;
586		}
392	–	return e;
587		}
588
395	–
589		// Search Operations
590
591		/**
592		* Returns the index of the first occurrence of the specified element
593		* in this list, or -1 if this list does not contain the element.
594	<	* More formally, returns the lowest index <tt>i</tt> such that
594	>	* More formally, returns the lowest index {@code i} such that
595		* <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>,
596		* or -1 if there is no such index.
597		*
#	Line 408 | Line 601 | public class LinkedList<E>
601		*/
602		public int indexOf(Object o) {
603		int index = 0;
604	<	if (o==null) {
605	<	for (Entry e = header.next; e != header; e = e.next) {
606	<	if (e.element==null)
604	>	if (o == null) {
605	>	for (Node<E> x = first; x != null; x = x.next) {
606	>	if (x.item == null)
607		return index;
608		index++;
609		}
610		} else {
611	<	for (Entry e = header.next; e != header; e = e.next) {
612	<	if (o.equals(e.element))
611	>	for (Node<E> x = first; x != null; x = x.next) {
612	>	if (o.equals(x.item))
613		return index;
614		index++;
615		}
#	Line 427 | Line 620 | public class LinkedList<E>
620		/**
621		* Returns the index of the last occurrence of the specified element
622		* in this list, or -1 if this list does not contain the element.
623	<	* More formally, returns the highest index <tt>i</tt> such that
623	>	* More formally, returns the highest index {@code i} such that
624		* <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>,
625		* or -1 if there is no such index.
626		*
#	Line 437 | Line 630 | public class LinkedList<E>
630		*/
631		public int lastIndexOf(Object o) {
632		int index = size;
633	<	if (o==null) {
634	<	for (Entry e = header.previous; e != header; e = e.previous) {
633	>	if (o == null) {
634	>	for (Node<E> x = last; x != null; x = x.prev) {
635		index--;
636	<	if (e.element==null)
636	>	if (x.item == null)
637		return index;
638		}
639		} else {
640	<	for (Entry e = header.previous; e != header; e = e.previous) {
640	>	for (Node<E> x = last; x != null; x = x.prev) {
641		index--;
642	<	if (o.equals(e.element))
642	>	if (o.equals(x.item))
643		return index;
644		}
645		}
#	Line 457 | Line 650 | public class LinkedList<E>
650
651		/**
652		* Retrieves, but does not remove, the head (first element) of this list.
653	<	* @return the head of this list, or <tt>null</tt> if this list is empty
653	>	*
654	>	* @return the head of this list, or {@code null} if this list is empty
655		* @since 1.5
656		*/
657		public E peek() {
658	<	if (size==0)
659	<	return null;
466	<	return getFirst();
658	>	final Node<E> f = first;
659	>	return (f == null) ? null : f.item;
660		}
661
662		/**
663		* Retrieves, but does not remove, the head (first element) of this list.
664	+	*
665		* @return the head of this list
666		* @throws NoSuchElementException if this list is empty
667		* @since 1.5
#	Line 477 | Line 671 | public class LinkedList<E>
671		}
672
673		/**
674	<	* Retrieves and removes the head (first element) of this list
675	<	* @return the head of this list, or <tt>null</tt> if this list is empty
674	>	* Retrieves and removes the head (first element) of this list.
675	>	*
676	>	* @return the head of this list, or {@code null} if this list is empty
677		* @since 1.5
678		*/
679		public E poll() {
680	<	if (size==0)
681	<	return null;
487	<	return removeFirst();
680	>	final Node<E> f = first;
681	>	return (f == null) ? null : unlinkFirst(f);
682		}
683
684		/**
#	Line 502 | Line 696 | public class LinkedList<E>
696		* Adds the specified element as the tail (last element) of this list.
697		*
698		* @param e the element to add
699	<	* @return <tt>true</tt> (as specified by {@link Queue#offer})
699	>	* @return {@code true} (as specified by {@link Queue#offer})
700		* @since 1.5
701		*/
702		public boolean offer(E e) {
#	Line 514 | Line 708 | public class LinkedList<E>
708		* Inserts the specified element at the front of this list.
709		*
710		* @param e the element to insert
711	<	* @return <tt>true</tt> (as specified by {@link Deque#offerFirst})
711	>	* @return {@code true} (as specified by {@link Deque#offerFirst})
712		* @since 1.6
713		*/
714		public boolean offerFirst(E e) {
#	Line 526 | Line 720 | public class LinkedList<E>
720		* Inserts the specified element at the end of this list.
721		*
722		* @param e the element to insert
723	<	* @return <tt>true</tt> (as specified by {@link Deque#offerLast})
723	>	* @return {@code true} (as specified by {@link Deque#offerLast})
724		* @since 1.6
725		*/
726		public boolean offerLast(E e) {
#	Line 536 | Line 730 | public class LinkedList<E>
730
731		/**
732		* Retrieves, but does not remove, the first element of this list,
733	<	* or returns <tt>null</tt> if this list is empty.
733	>	* or returns {@code null} if this list is empty.
734		*
735	<	* @return the first element of this list, or <tt>null</tt>
735	>	* @return the first element of this list, or {@code null}
736		*         if this list is empty
737		* @since 1.6
738		*/
739		public E peekFirst() {
740	<	if (size==0)
741	<	return null;
742	<	return getFirst();
549	<	}
740	>	final Node<E> f = first;
741	>	return (f == null) ? null : f.item;
742	>	}
743
744		/**
745		* Retrieves, but does not remove, the last element of this list,
746	<	* or returns <tt>null</tt> if this list is empty.
746	>	* or returns {@code null} if this list is empty.
747		*
748	<	* @return the last element of this list, or <tt>null</tt>
748	>	* @return the last element of this list, or {@code null}
749		*         if this list is empty
750		* @since 1.6
751		*/
752		public E peekLast() {
753	<	if (size==0)
754	<	return null;
562	<	return getLast();
753	>	final Node<E> l = last;
754	>	return (l == null) ? null : l.item;
755		}
756
757		/**
758		* Retrieves and removes the first element of this list,
759	<	* or returns <tt>null</tt> if this list is empty.
759	>	* or returns {@code null} if this list is empty.
760		*
761	<	* @return the first element of this list, or <tt>null</tt> if
761	>	* @return the first element of this list, or {@code null} if
762		*     this list is empty
763		* @since 1.6
764		*/
765		public E pollFirst() {
766	<	if (size==0)
767	<	return null;
576	<	return removeFirst();
766	>	final Node<E> f = first;
767	>	return (f == null) ? null : unlinkFirst(f);
768		}
769
770		/**
771		* Retrieves and removes the last element of this list,
772	<	* or returns <tt>null</tt> if this list is empty.
772	>	* or returns {@code null} if this list is empty.
773		*
774	<	* @return the last element of this list, or <tt>null</tt> if
774	>	* @return the last element of this list, or {@code null} if
775		*     this list is empty
776		* @since 1.6
777		*/
778		public E pollLast() {
779	<	if (size==0)
780	<	return null;
590	<	return removeLast();
779	>	final Node<E> l = last;
780	>	return (l == null) ? null : unlinkLast(l);
781		}
782
783		/**
#	Line 624 | Line 814 | public class LinkedList<E>
814		* does not contain the element, it is unchanged.
815		*
816		* @param o element to be removed from this list, if present
817	<	* @return <tt>true</tt> if the list contained the specified element
817	>	* @return {@code true} if the list contained the specified element
818		* @since 1.6
819		*/
820		public boolean removeFirstOccurrence(Object o) {
#	Line 637 | Line 827 | public class LinkedList<E>
827		* does not contain the element, it is unchanged.
828		*
829		* @param o element to be removed from this list, if present
830	<	* @return <tt>true</tt> if the list contained the specified element
830	>	* @return {@code true} if the list contained the specified element
831		* @since 1.6
832		*/
833		public boolean removeLastOccurrence(Object o) {
834	<	if (o==null) {
835	<	for (Entry<E> e = header.previous; e != header; e = e.previous) {
836	<	if (e.element==null) {
837	<	remove(e);
834	>	if (o == null) {
835	>	for (Node<E> x = last; x != null; x = x.prev) {
836	>	if (x.item == null) {
837	>	unlink(x);
838		return true;
839		}
840		}
841		} else {
842	<	for (Entry<E> e = header.previous; e != header; e = e.previous) {
843	<	if (o.equals(e.element)) {
844	<	remove(e);
842	>	for (Node<E> x = last; x != null; x = x.prev) {
843	>	if (o.equals(x.item)) {
844	>	unlink(x);
845		return true;
846		}
847		}
#	Line 662 | Line 852 | public class LinkedList<E>
852		/**
853		* Returns a list-iterator of the elements in this list (in proper
854		* sequence), starting at the specified position in the list.
855	<	* Obeys the general contract of <tt>List.listIterator(int)</tt>.<p>
855	>	* Obeys the general contract of {@code List.listIterator(int)}.<p>
856		*
857		* The list-iterator is <i>fail-fast</i>: if the list is structurally
858		* modified at any time after the Iterator is created, in any way except
859	<	* through the list-iterator's own <tt>remove</tt> or <tt>add</tt>
859	>	* through the list-iterator's own {@code remove} or {@code add}
860		* methods, the list-iterator will throw a
861	<	* <tt>ConcurrentModificationException</tt>.  Thus, in the face of
861	>	* {@code ConcurrentModificationException}.  Thus, in the face of
862		* concurrent modification, the iterator fails quickly and cleanly, rather
863		* than risking arbitrary, non-deterministic behavior at an undetermined
864		* time in the future.
865		*
866		* @param index index of the first element to be returned from the
867	<	*              list-iterator (by a call to <tt>next</tt>)
867	>	*              list-iterator (by a call to {@code next})
868		* @return a ListIterator of the elements in this list (in proper
869		*         sequence), starting at the specified position in the list
870		* @throws IndexOutOfBoundsException {@inheritDoc}
871		* @see List#listIterator(int)
872		*/
873		public ListIterator<E> listIterator(int index) {
874	+	checkPositionIndex(index);
875		return new ListItr(index);
876		}
877
878		private class ListItr implements ListIterator<E> {
879	<	private Entry<E> lastReturned = header;
880	<	private Entry<E> next;
879	>	private Node<E> lastReturned = null;
880	>	private Node<E> next;
881		private int nextIndex;
882		private int expectedModCount = modCount;
883
884		ListItr(int index) {
885	<	if (index < 0 || index > size)
886	<	throw new IndexOutOfBoundsException("Index: "+index+
887	<	", Size: "+size);
697	<	if (index < (size >> 1)) {
698	<	next = header.next;
699	<	for (nextIndex=0; nextIndex<index; nextIndex++)
700	<	next = next.next;
701	<	} else {
702	<	next = header;
703	<	for (nextIndex=size; nextIndex>index; nextIndex--)
704	<	next = next.previous;
705	<	}
885	>	// assert isPositionIndex(index);
886	>	next = (index == size) ? null : node(index);
887	>	nextIndex = index;
888		}
889
890		public boolean hasNext() {
891	<	return nextIndex != size;
891	>	return nextIndex < size;
892		}
893
894		public E next() {
895		checkForComodification();
896	<	if (nextIndex == size)
896	>	if (!hasNext())
897		throw new NoSuchElementException();
898
899		lastReturned = next;
900		next = next.next;
901		nextIndex++;
902	<	return lastReturned.element;
902	>	return lastReturned.item;
903		}
904
905		public boolean hasPrevious() {
906	<	return nextIndex != 0;
906	>	return nextIndex > 0;
907		}
908
909		public E previous() {
910	<	if (nextIndex == 0)
910	>	checkForComodification();
911	>	if (!hasPrevious())
912		throw new NoSuchElementException();
913
914	<	lastReturned = next = next.previous;
914	>	lastReturned = next = (next == null) ? last : next.prev;
915		nextIndex--;
916	<	checkForComodification();
734	<	return lastReturned.element;
916	>	return lastReturned.item;
917		}
918
919		public int nextIndex() {
#	Line 739 | Line 921 | public class LinkedList<E>
921		}
922
923		public int previousIndex() {
924	<	return nextIndex-1;
924	>	return nextIndex - 1;
925		}
926
927		public void remove() {
928		checkForComodification();
929	<	Entry<E> lastNext = lastReturned.next;
748	<	try {
749	<	LinkedList.this.remove(lastReturned);
750	<	} catch (NoSuchElementException e) {
929	>	if (lastReturned == null)
930		throw new IllegalStateException();
931	<	}
932	<	if (next==lastReturned)
931	>
932	>	Node<E> lastNext = lastReturned.next;
933	>	unlink(lastReturned);
934	>	if (next == lastReturned)
935		next = lastNext;
936		else
937		nextIndex--;
938	<	lastReturned = header;
938	>	lastReturned = null;
939		expectedModCount++;
940		}
941
942		public void set(E e) {
943	<	if (lastReturned == header)
943	>	if (lastReturned == null)
944		throw new IllegalStateException();
945		checkForComodification();
946	<	lastReturned.element = e;
946	>	lastReturned.item = e;
947		}
948
949		public void add(E e) {
950		checkForComodification();
951	<	lastReturned = header;
952	<	addBefore(e, next);
951	>	lastReturned = null;
952	>	if (next == null)
953	>	linkLast(e);
954	>	else
955	>	linkBefore(e, next);
956		nextIndex++;
957		expectedModCount++;
958		}
#	Line 779 | Line 963 | public class LinkedList<E>
963		}
964		}
965
966	<	private static class Entry<E> {
967	<	E element;
968	<	Entry<E> next;
969	<	Entry<E> previous;
966	>	private static class Node<E> {
967	>	E item;
968	>	Node<E> next;
969	>	Node<E> prev;
970
971	<	Entry(E element, Entry<E> next, Entry<E> previous) {
972	<	this.element = element;
971	>	Node(Node<E> prev, E element, Node<E> next) {
972	>	this.item = element;
973		this.next = next;
974	<	this.previous = previous;
974	>	this.prev = prev;
975		}
976		}
977
794	–	private Entry<E> addBefore(E e, Entry<E> entry) {
795	–	Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);
796	–	newEntry.previous.next = newEntry;
797	–	newEntry.next.previous = newEntry;
798	–	size++;
799	–	modCount++;
800	–	return newEntry;
801	–	}
802	–
803	–	private E remove(Entry<E> e) {
804	–	if (e == header)
805	–	throw new NoSuchElementException();
806	–
807	–	E result = e.element;
808	–	e.previous.next = e.next;
809	–	e.next.previous = e.previous;
810	–	e.next = e.previous = null;
811	–	e.element = null;
812	–	size--;
813	–	modCount++;
814	–	return result;
815	–	}
816	–
978		/**
979		* @since 1.6
980		*/
#	Line 821 | Line 982 | public class LinkedList<E>
982		return new DescendingIterator();
983		}
984
985	<	/** Adapter to provide descending iterators via ListItr.previous */
986	<	private class DescendingIterator implements Iterator {
987	<	final ListItr itr = new ListItr(size());
985	>	/**
986	>	* Adapter to provide descending iterators via ListItr.previous
987	>	*/
988	>	private class DescendingIterator implements Iterator<E> {
989	>	private final ListItr itr = new ListItr(size());
990		public boolean hasNext() {
991		return itr.hasPrevious();
992		}
#	Line 835 | Line 998 | public class LinkedList<E>
998		}
999		}
1000
1001	+	@SuppressWarnings("unchecked")
1002	+	private LinkedList<E> superClone() {
1003	+	try {
1004	+	return (LinkedList<E>) super.clone();
1005	+	} catch (CloneNotSupportedException e) {
1006	+	throw new InternalError();
1007	+	}
1008	+	}
1009	+
1010		/**
1011	<	* Returns a shallow copy of this <tt>LinkedList</tt>. (The elements
1011	>	* Returns a shallow copy of this {@code LinkedList}. (The elements
1012		* themselves are not cloned.)
1013		*
1014	<	* @return a shallow copy of this <tt>LinkedList</tt> instance
1014	>	* @return a shallow copy of this {@code LinkedList} instance
1015		*/
1016		public Object clone() {
1017	<	LinkedList<E> clone = null;
846	<	try {
847	<	clone = (LinkedList<E>) super.clone();
848	<	} catch (CloneNotSupportedException e) {
849	<	throw new InternalError();
850	<	}
1017	>	LinkedList<E> clone = superClone();
1018
1019		// Put clone into "virgin" state
1020	<	clone.header = new Entry<E>(null, null, null);
854	<	clone.header.next = clone.header.previous = clone.header;
1020	>	clone.first = clone.last = null;
1021		clone.size = 0;
1022		clone.modCount = 0;
1023
1024		// Initialize clone with our elements
1025	<	for (Entry<E> e = header.next; e != header; e = e.next)
1026	<	clone.add(e.element);
1025	>	for (Node<E> x = first; x != null; x = x.next)
1026	>	clone.add(x.item);
1027
1028		return clone;
1029		}
#	Line 879 | Line 1045 | public class LinkedList<E>
1045		public Object[] toArray() {
1046		Object[] result = new Object[size];
1047		int i = 0;
1048	<	for (Entry<E> e = header.next; e != header; e = e.next)
1049	<	result[i++] = e.element;
1048	>	for (Node<E> x = first; x != null; x = x.next)
1049	>	result[i++] = x.item;
1050		return result;
1051		}
1052
#	Line 894 | Line 1060 | public class LinkedList<E>
1060		*
1061		* <p>If the list fits in the specified array with room to spare (i.e.,
1062		* the array has more elements than the list), the element in the array
1063	<	* immediately following the end of the list is set to <tt>null</tt>.
1063	>	* immediately following the end of the list is set to {@code null}.
1064		* (This is useful in determining the length of the list <i>only</i> if
1065		* the caller knows that the list does not contain any null elements.)
1066		*
#	Line 903 | Line 1069 | public class LinkedList<E>
1069		* precise control over the runtime type of the output array, and may,
1070		* under certain circumstances, be used to save allocation costs.
1071		*
1072	<	* <p>Suppose <tt>x</tt> is a list known to contain only strings.
1072	>	* <p>Suppose {@code x} is a list known to contain only strings.
1073		* The following code can be used to dump the list into a newly
1074	<	* allocated array of <tt>String</tt>:
1074	>	* allocated array of {@code String}:
1075		*
1076		* <pre>
1077		*     String[] y = x.toArray(new String[0]);</pre>
1078		*
1079	<	* Note that <tt>toArray(new Object[0])</tt> is identical in function to
1080	<	* <tt>toArray()</tt>.
1079	>	* Note that {@code toArray(new Object[0])} is identical in function to
1080	>	* {@code toArray()}.
1081		*
1082		* @param a the array into which the elements of the list are to
1083		*          be stored, if it is big enough; otherwise, a new array of the
#	Line 922 | Line 1088 | public class LinkedList<E>
1088		*         this list
1089		* @throws NullPointerException if the specified array is null
1090		*/
1091	+	@SuppressWarnings("unchecked")
1092		public <T> T[] toArray(T[] a) {
1093		if (a.length < size)
1094		a = (T[])java.lang.reflect.Array.newInstance(
1095		a.getClass().getComponentType(), size);
1096		int i = 0;
1097		Object[] result = a;
1098	<	for (Entry<E> e = header.next; e != header; e = e.next)
1099	<	result[i++] = e.element;
1098	>	for (Node<E> x = first; x != null; x = x.next)
1099	>	result[i++] = x.item;
1100
1101		if (a.length > size)
1102		a[size] = null;
#	Line 940 | Line 1107 | public class LinkedList<E>
1107		private static final long serialVersionUID = 876323262645176354L;
1108
1109		/**
1110	<	* Save the state of this <tt>LinkedList</tt> instance to a stream (that
1111	<	* is, serialize it).
1110	>	* Saves the state of this {@code LinkedList} instance to a stream
1111	>	* (that is, serializes it).
1112		*
1113		* @serialData The size of the list (the number of elements it
1114		*             contains) is emitted (int), followed by all of its
#	Line 956 | Line 1123 | public class LinkedList<E>
1123		s.writeInt(size);
1124
1125		// Write out all elements in the proper order.
1126	<	for (Entry e = header.next; e != header; e = e.next)
1127	<	s.writeObject(e.element);
1126	>	for (Node<E> x = first; x != null; x = x.next)
1127	>	s.writeObject(x.item);
1128		}
1129
1130		/**
1131	<	* Reconstitute this <tt>LinkedList</tt> instance from a stream (that is
1132	<	* deserialize it).
1131	>	* Reconstitutes this {@code LinkedList} instance from a stream
1132	>	* (that is, deserializes it).
1133		*/
1134	+	@SuppressWarnings("unchecked")
1135		private void readObject(java.io.ObjectInputStream s)
1136		throws java.io.IOException, ClassNotFoundException {
1137		// Read in any hidden serialization magic
#	Line 972 | Line 1140 | public class LinkedList<E>
1140		// Read in size
1141		int size = s.readInt();
1142
975	–	// Initialize header
976	–	header = new Entry<E>(null, null, null);
977	–	header.next = header.previous = header;
978	–
1143		// Read in all elements in the proper order.
1144	<	for (int i=0; i<size; i++)
1145	<	addBefore((E)s.readObject(), header);
1144	>	for (int i = 0; i < size; i++)
1145	>	linkLast((E)s.readObject());
1146		}
1147		}

Diff Legend

–	Removed lines
+	Added lines
<	Changed lines
>	Changed lines