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.13 by jozart, Mon Nov 17 08:09:34 2003 UTC vs.
Revision 1.24 by jsr166, Tue Apr 26 19:54:03 2005 UTC

#	Line 1 | Line 1
1		/*
2		* %W% %E%
3		*
4	<	* Copyright 2003 Sun Microsystems, Inc. All rights reserved.
4	>	* Copyright 2005 Sun Microsystems, Inc. All rights reserved.
5		* SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
6		*/
7
#	Line 14 | Line 14 | package java.util;
14		* the <tt>LinkedList</tt> class provides uniformly named methods to
15		* <tt>get</tt>, <tt>remove</tt> and <tt>insert</tt> an element at the
16		* beginning and end of the list.  These operations allow linked lists to be
17	<	* used as a stack, queue, or double-ended queue (deque).<p>
17	>	* used as a stack, {@linkplain Queue queue}, or {@linkplain Deque
18	>	* double-ended queue}. <p>
19		*
20	<	* The class implements the <tt>Queue</tt> interface, providing
20	>	* The class implements the <tt>Deque</tt> interface, providing
21		* first-in-first-out queue operations for <tt>add</tt>,
22	<	* <tt>poll</tt>, etc. Other stack and deque operations could be
22	<	* easily recast in terms of the standard list operations.  They're
23	<	* included here primarily for convenience, though they may run
24	<	* slightly faster than the equivalent List operations.<p>
22	>	* <tt>poll</tt>, along with other stack and deque operations.<p>
23		*
24		* All of the operations perform as could be expected for a doubly-linked
25		* list.  Operations that index into the list will traverse the list from
#	Line 38 | Line 36 | package java.util;
36		* Collections.synchronizedList method.  This is best done at creation time,
37		* to prevent accidental unsynchronized access to the list: <pre>
38		*     List list = Collections.synchronizedList(new LinkedList(...));
39	<	* </pre><p>
39	>	* </pre>
40		*
41	<	* The iterators returned by the this class's <tt>iterator</tt> and
41	>	* <p>The iterators returned by this class's <tt>iterator</tt> and
42		* <tt>listIterator</tt> methods are <i>fail-fast</i>: if the list is
43	<	* structurally modified at any time after the iterator is created, in any way
44	<	* except through the Iterator's own <tt>remove</tt> or <tt>add</tt> methods,
45	<	* the iterator will throw a <tt>ConcurrentModificationException</tt>.  Thus,
46	<	* in the face of concurrent modification, the iterator fails quickly and
47	<	* cleanly, rather than risking arbitrary, non-deterministic behavior at an
48	<	* undetermined time in the future.
43	>	* structurally modified at any time after the iterator is created, in
44	>	* any way except through the Iterator's own <tt>remove</tt> or
45	>	* <tt>add</tt> methods, the iterator will throw a {@link
46	>	* ConcurrentModificationException}.  Thus, in the face of concurrent
47	>	* modification, the iterator fails quickly and cleanly, rather than
48	>	* risking arbitrary, non-deterministic behavior at an undetermined
49	>	* time in the future.
50		*
51		* <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
52		* as it is, generally speaking, impossible to make any hard guarantees in the
#	Line 55 | Line 54 | package java.util;
54		* throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
55		* Therefore, it would be wrong to write a program that depended on this
56		* exception for its correctness:   <i>the fail-fast behavior of iterators
57	<	* should be used only to detect bugs.</i><p>
57	>	* should be used only to detect bugs.</i>
58		*
59	<	* This class is a member of the
59	>	* <p>This class is a member of the
60		* <a href="{@docRoot}/../guide/collections/index.html">
61		* Java Collections Framework</a>.
62		*
63		* @author  Josh Bloch
64		* @version %I%, %G%
65	<	* @see     List
66	<	* @see     ArrayList
67	<	* @see     Vector
68	<	* @see     Collections#synchronizedList(List)
65	>	* @see     List
66	>	* @see     ArrayList
67	>	* @see     Vector
68	>	* @see     Collections#synchronizedList(List)
69		* @since 1.2
70		* @param <E> the type of elements held in this collection
71		*/
72
73		public class LinkedList<E>
74		extends AbstractSequentialList<E>
75	<	implements List<E>, Queue<E>, Cloneable, java.io.Serializable
75	>	implements List<E>, Deque<E>, Cloneable, java.io.Serializable
76		{
77		private transient Entry<E> header = new Entry<E>(null, null, null);
78		private transient int size = 0;
#	Line 93 | Line 92 | public class LinkedList<E>
92		* @param  c the collection whose elements are to be placed into this list.
93		* @throws NullPointerException if the specified collection is null.
94		*/
95	<	public LinkedList(Collection<? extends E> c) {
96	<	this();
97	<	addAll(c);
98	<	}
95	>	public LinkedList(Collection<? extends E> c) {
96	>	this();
97	>	addAll(c);
98	>	}
99
100		/**
101		* Returns the first element in this list.
#	Line 105 | Line 104 | public class LinkedList<E>
104		* @throws    NoSuchElementException if this list is empty.
105		*/
106		public E getFirst() {
107	<	if (size==0)
108	<	throw new NoSuchElementException();
107	>	if (size==0)
108	>	throw new NoSuchElementException();
109
110	<	return header.next.element;
110	>	return header.next.element;
111		}
112
113		/**
#	Line 118 | Line 117 | public class LinkedList<E>
117		* @throws    NoSuchElementException if this list is empty.
118		*/
119		public E getLast()  {
120	<	if (size==0)
121	<	throw new NoSuchElementException();
120	>	if (size==0)
121	>	throw new NoSuchElementException();
122
123	<	return header.previous.element;
123	>	return header.previous.element;
124		}
125
126		/**
#	Line 131 | Line 130 | public class LinkedList<E>
130		* @throws    NoSuchElementException if this list is empty.
131		*/
132		public E removeFirst() {
133	<	E first = header.next.element;
135	<	remove(header.next);
136	<	return first;
133	>	return remove(header.next);
134		}
135
136		/**
#	Line 143 | Line 140 | public class LinkedList<E>
140		* @throws    NoSuchElementException if this list is empty.
141		*/
142		public E removeLast() {
143	<	E last = header.previous.element;
147	<	remove(header.previous);
148	<	return last;
143	>	return remove(header.previous);
144		}
145
146		/**
#	Line 154 | Line 149 | public class LinkedList<E>
149		* @param o the element to be inserted at the beginning of this list.
150		*/
151		public void addFirst(E o) {
152	<	addBefore(o, header.next);
152	>	addBefore(o, header.next);
153		}
154
155		/**
#	Line 164 | Line 159 | public class LinkedList<E>
159		* @param o the element to be inserted at the end of this list.
160		*/
161		public void addLast(E o) {
162	<	addBefore(o, header);
162	>	addBefore(o, header);
163		}
164
165		/**
#	Line 186 | Line 181 | public class LinkedList<E>
181		* @return the number of elements in this list.
182		*/
183		public int size() {
184	<	return size;
184	>	return size;
185		}
186
187		/**
#	Line 197 | Line 192 | public class LinkedList<E>
192		* <tt>Collection.add</tt>).
193		*/
194		public boolean add(E o) {
195	<	addBefore(o, header);
195	>	addBefore(o, header);
196		return true;
197		}
198
#	Line 255 | Line 250 | public class LinkedList<E>
250		* specified collection's iterator.
251		*
252		* @param index index at which to insert first element
253	<	*              from the specified collection.
253	>	*              from the specified collection.
254		* @param c elements to be inserted into this list.
255		* @return <tt>true</tt> if this list changed as a result of the call.
256	<	* @throws IndexOutOfBoundsException if the specified index is out of
257	<	*            range (<tt>index &lt; 0 || index &gt; size()</tt>).
256	>	* @throws IndexOutOfBoundsException if the index is out of range
257	>	*         (<tt>index &lt; 0 || index &gt; size()</tt>).
258		* @throws NullPointerException if the specified collection is null.
259		*/
260		public boolean addAll(int index, Collection<? extends E> c) {
#	Line 270 | Line 265 | public class LinkedList<E>
265		int numNew = a.length;
266		if (numNew==0)
267		return false;
268	<	modCount++;
268	>	modCount++;
269
270		Entry<E> successor = (index==size ? header : entry(index));
271		Entry<E> predecessor = successor.previous;
272	<	for (int i=0; i<numNew; i++) {
272	>	for (int i=0; i<numNew; i++) {
273		Entry<E> e = new Entry<E>((E)a[i], successor, predecessor);
274		predecessor.next = e;
275		predecessor = e;
#	Line 289 | Line 284 | public class LinkedList<E>
284		* Removes all of the elements from this list.
285		*/
286		public void clear() {
287	<	modCount++;
287	>	Entry<E> e = header.next;
288	>	while (e != header) {
289	>	Entry<E> next = e.next;
290	>	e.next = e.previous = null;
291	>	e.element = null;
292	>	e = next;
293	>	}
294		header.next = header.previous = header;
295		size = 0;
296	+	modCount++;
297		}
298
299
#	Line 303 | Line 305 | public class LinkedList<E>
305		* @param index index of element to return.
306		* @return the element at the specified position in this list.
307		*
308	<	* @throws IndexOutOfBoundsException if the specified index is is out of
309	<	* range (<tt>index &lt; 0 || index &gt;= size()</tt>).
308	>	* @throws IndexOutOfBoundsException if the index is out of range
309	>	*         (<tt>index &lt; 0 || index &gt; size()</tt>).
310		*/
311		public E get(int index) {
312		return entry(index).element;
#	Line 317 | Line 319 | public class LinkedList<E>
319		* @param index index of element to replace.
320		* @param element element to be stored at the specified position.
321		* @return the element previously at the specified position.
322	<	* @throws IndexOutOfBoundsException if the specified index is out of
323	<	*            range (<tt>index &lt; 0 || index &gt;= size()</tt>).
322	>	* @throws IndexOutOfBoundsException if the index is out of range
323	>	*         (<tt>index &lt; 0 || index &gt; size()</tt>).
324		*/
325		public E set(int index, E element) {
326		Entry<E> e = entry(index);
#	Line 335 | Line 337 | public class LinkedList<E>
337		* @param index index at which the specified element is to be inserted.
338		* @param element element to be inserted.
339		*
340	<	* @throws IndexOutOfBoundsException if the specified index is out of
341	<	*            range (<tt>index &lt; 0 || index &gt; size()</tt>).
340	>	* @throws IndexOutOfBoundsException if the index is out of range
341	>	*         (<tt>index &lt; 0 || index &gt; size()</tt>).
342		*/
343		public void add(int index, E element) {
344		addBefore(element, (index==size ? header : entry(index)));
#	Line 350 | Line 352 | public class LinkedList<E>
352		* @param index the index of the element to removed.
353		* @return the element previously at the specified position.
354		*
355	<	* @throws IndexOutOfBoundsException if the specified index is out of
356	<	*            range (<tt>index &lt; 0 || index &gt;= size()</tt>).
355	>	* @throws IndexOutOfBoundsException if the index is out of range
356	>	*         (<tt>index &lt; 0 || index &gt; size()</tt>).
357		*/
358		public E remove(int index) {
359	<	Entry<E> e = entry(index);
358	<	remove(e);
359	<	return e.element;
359	>	return remove(entry(index));
360		}
361
362		/**
363	<	* Return the indexed entry.
363	>	* Returns the indexed entry.
364		*/
365		private Entry<E> entry(int index) {
366		if (index < 0 || index >= size)
#	Line 389 | Line 389 | public class LinkedList<E>
389		*
390		* @param o element to search for.
391		* @return the index in this list of the first occurrence of the
392	<	*         specified element, or -1 if the list does not contain this
393	<	*         element.
392	>	*         specified element, or -1 if the list does not contain this
393	>	*         element.
394		*/
395		public int indexOf(Object o) {
396		int index = 0;
#	Line 419 | Line 419 | public class LinkedList<E>
419		*
420		* @param o element to search for.
421		* @return the index in this list of the last occurrence of the
422	<	*         specified element, or -1 if the list does not contain this
423	<	*         element.
422	>	*         specified element, or -1 if the list does not contain this
423	>	*         element.
424		*/
425		public int lastIndexOf(Object o) {
426		int index = size;
#	Line 444 | Line 444 | public class LinkedList<E>
444
445		/**
446		* Retrieves, but does not remove, the head (first element) of this list.
447	<	* @return the head of this queue, or <tt>null</tt> if this queue is empty.
447	>	* @return the head of this list, or <tt>null</tt> if this list is empty.
448		* @since 1.5
449		*/
450		public E peek() {
#	Line 455 | Line 455 | public class LinkedList<E>
455
456		/**
457		* Retrieves, but does not remove, the head (first element) of this list.
458	<	* @return the head of this queue.
459	<	* @throws NoSuchElementException if this queue is empty.
458	>	* @return the head of this list.
459	>	* @throws NoSuchElementException if this list is empty.
460		* @since 1.5
461		*/
462		public E element() {
#	Line 465 | Line 465 | public class LinkedList<E>
465
466		/**
467		* Retrieves and removes the head (first element) of this list.
468	<	* @return the head of this queue, or <tt>null</tt> if this queue is empty.
468	>	* @return the head of this list, or <tt>null</tt> if this list is empty.
469		* @since 1.5
470		*/
471		public E poll() {
#	Line 476 | Line 476 | public class LinkedList<E>
476
477		/**
478		* Retrieves and removes the head (first element) of this list.
479	<	* @return the head of this queue.
480	<	* @throws NoSuchElementException if this queue is empty.
479	>	* @return the head of this list.
480	>	* @throws NoSuchElementException if this list is empty.
481		* @since 1.5
482		*/
483		public E remove() {
#	Line 496 | Line 496 | public class LinkedList<E>
496		return add(o);
497		}
498
499	+	// Deque operations
500	+	/**
501	+	* Inserts the specified element at the front of this list.
502	+	*
503	+	* @param e the element to insert
504	+	* @return <tt>true</tt> (as per the spec for {@link Deque#offerFirst})
505	+	* @since 1.6
506	+	*/
507	+	public boolean offerFirst(E e) {
508	+	addFirst(e);
509	+	return true;
510	+	}
511	+
512	+	/**
513	+	* Inserts the specified element at the end of this list.
514	+	*
515	+	* @param e the element to insert
516	+	* @return <tt>true</tt> (as per the spec for {@link Deque#offerLast})
517	+	* @since 1.6
518	+	*/
519	+	public boolean offerLast(E e) {
520	+	addLast(e);
521	+	return true;
522	+	}
523	+
524	+	/**
525	+	* Retrieves, but does not remove, the first element of this list,
526	+	* returning <tt>null</tt> if this list is empty.
527	+	*
528	+	* @return the first element of this list, or <tt>null</tt> if
529	+	*     this list is empty
530	+	* @since 1.6
531	+	*/
532	+	public E peekFirst() {
533	+	if (size==0)
534	+	return null;
535	+	return getFirst();
536	+	}
537	+
538	+	/**
539	+	* Retrieves, but does not remove, the last element of this list,
540	+	* returning <tt>null</tt> if this list is empty.
541	+	*
542	+	* @return the last element of this list, or <tt>null</tt> if this list
543	+	*     is empty
544	+	* @since 1.6
545	+	*/
546	+	public E peekLast() {
547	+	if (size==0)
548	+	return null;
549	+	return getLast();
550	+	}
551	+
552	+	/**
553	+	* Retrieves and removes the first element of this list, or
554	+	* <tt>null</tt> if this list is empty.
555	+	*
556	+	* @return the first element of this list, or <tt>null</tt> if
557	+	*     this list is empty
558	+	* @since 1.6
559	+	*/
560	+	public E pollFirst() {
561	+	if (size==0)
562	+	return null;
563	+	return removeFirst();
564	+	}
565	+
566	+	/**
567	+	* Retrieves and removes the last element of this list, or
568	+	* <tt>null</tt> if this list is empty.
569	+	*
570	+	* @return the last element of this list, or <tt>null</tt> if
571	+	*     this list is empty
572	+	* @since 1.6
573	+	*/
574	+	public E pollLast() {
575	+	if (size==0)
576	+	return null;
577	+	return removeLast();
578	+	}
579	+
580	+	/**
581	+	* Pushes an element onto the stack represented by this list.  In other
582	+	* words, inserts the element at the front of this list.
583	+	*
584	+	* <p>This method is equivalent to {@link #addFirst}.
585	+	*
586	+	* @param e the element to push
587	+	* @since 1.6
588	+	*/
589	+	public void push(E e) {
590	+	addFirst(e);
591	+	}
592	+
593	+	/**
594	+	* Pops an element from the stack represented by this list.  In other
595	+	* words, removes and returns the first element of this list.
596	+	*
597	+	* <p>This method is equivalent to {@link #removeFirst()}.
598	+	*
599	+	* @return the element at the front of this list (which is the top
600	+	*     of the stack represented by this list)
601	+	* @throws NoSuchElementException if this list is empty.
602	+	* @since 1.6
603	+	*/
604	+	public E pop() {
605	+	return removeFirst();
606	+	}
607	+
608	+	/**
609	+	* Removes the first occurrence of the specified element in this
610	+	* list (when traversing the list from head to tail).  If the list
611	+	* does not contain the element, it is unchanged.
612	+	*
613	+	* @param o element to be removed from this list, if present
614	+	* @return <tt>true</tt> if the list contained the specified element
615	+	* @since 1.6
616	+	*/
617	+	public boolean removeFirstOccurrence(Object o) {
618	+	return remove(o);
619	+	}
620	+
621	+	/**
622	+	* Removes the last occurrence of the specified element in this
623	+	* list (when traversing the list from head to tail).  If the list
624	+	* does not contain the element, it is unchanged.
625	+	*
626	+	* @param o element to be removed from this list, if present
627	+	* @return <tt>true</tt> if the list contained the specified element
628	+	* @since 1.6
629	+	*/
630	+	public boolean removeLastOccurrence(Object o) {
631	+	if (o==null) {
632	+	for (Entry e = header.previous; e != header; e = e.previous) {
633	+	if (e.element==null) {
634	+	remove(e);
635	+	return true;
636	+	}
637	+	}
638	+	} else {
639	+	for (Entry e = header.previous; e != header; e = e.previous) {
640	+	if (o.equals(e.element)) {
641	+	remove(e);
642	+	return true;
643	+	}
644	+	}
645	+	}
646	+	return false;
647	+	}
648	+
649		/**
650		* Returns a list-iterator of the elements in this list (in proper
651		* sequence), starting at the specified position in the list.
#	Line 511 | Line 661 | public class LinkedList<E>
661		* time in the future.
662		*
663		* @param index index of first element to be returned from the
664	<	*              list-iterator (by a call to <tt>next</tt>).
664	>	*              list-iterator (by a call to <tt>next</tt>).
665		* @return a ListIterator of the elements in this list (in proper
666	<	*         sequence), starting at the specified position in the list.
667	<	* @throws    IndexOutOfBoundsException if index is out of range
668	<	*            (<tt>index &lt; 0 || index &gt; size()</tt>).
666	>	*         sequence), starting at the specified position in the list.
667	>	* @throws IndexOutOfBoundsException if the index is out of range
668	>	*         (<tt>index &lt; 0 || index &gt; size()</tt>).
669		* @see List#listIterator(int)
670		*/
671		public ListIterator<E> listIterator(int index) {
672	<	return new ListItr(index);
672	>	return new ListItr(index);
673		}
674
675		private class ListItr implements ListIterator<E> {
676	<	private Entry<E> lastReturned = header;
677	<	private Entry<E> next;
678	<	private int nextIndex;
679	<	private int expectedModCount = modCount;
680	<
681	<	ListItr(int index) {
682	<	if (index < 0 || index > size)
683	<	throw new IndexOutOfBoundsException("Index: "+index+
684	<	", Size: "+size);
685	<	if (index < (size >> 1)) {
686	<	next = header.next;
687	<	for (nextIndex=0; nextIndex<index; nextIndex++)
688	<	next = next.next;
689	<	} else {
690	<	next = header;
691	<	for (nextIndex=size; nextIndex>index; nextIndex--)
692	<	next = next.previous;
693	<	}
694	<	}
676	>	private Entry<E> lastReturned = header;
677	>	private Entry<E> next;
678	>	private int nextIndex;
679	>	private int expectedModCount = modCount;
680	>
681	>	ListItr(int index) {
682	>	if (index < 0 || index > size)
683	>	throw new IndexOutOfBoundsException("Index: "+index+
684	>	", Size: "+size);
685	>	if (index < (size >> 1)) {
686	>	next = header.next;
687	>	for (nextIndex=0; nextIndex<index; nextIndex++)
688	>	next = next.next;
689	>	} else {
690	>	next = header;
691	>	for (nextIndex=size; nextIndex>index; nextIndex--)
692	>	next = next.previous;
693	>	}
694	>	}
695	>
696	>	public boolean hasNext() {
697	>	return nextIndex != size;
698	>	}
699	>
700	>	public E next() {
701	>	checkForComodification();
702	>	if (nextIndex == size)
703	>	throw new NoSuchElementException();
704	>
705	>	lastReturned = next;
706	>	next = next.next;
707	>	nextIndex++;
708	>	return lastReturned.element;
709	>	}
710	>
711	>	public boolean hasPrevious() {
712	>	return nextIndex != 0;
713	>	}
714	>
715	>	public E previous() {
716	>	if (nextIndex == 0)
717	>	throw new NoSuchElementException();
718	>
719	>	lastReturned = next = next.previous;
720	>	nextIndex--;
721	>	checkForComodification();
722	>	return lastReturned.element;
723	>	}
724	>
725	>	public int nextIndex() {
726	>	return nextIndex;
727	>	}
728	>
729	>	public int previousIndex() {
730	>	return nextIndex-1;
731	>	}
732
733	<	public boolean hasNext() {
547	<	return nextIndex != size;
548	<	}
549	<
550	<	public E next() {
551	<	checkForComodification();
552	<	if (nextIndex == size)
553	<	throw new NoSuchElementException();
554	<
555	<	lastReturned = next;
556	<	next = next.next;
557	<	nextIndex++;
558	<	return lastReturned.element;
559	<	}
560	<
561	<	public boolean hasPrevious() {
562	<	return nextIndex != 0;
563	<	}
564	<
565	<	public E previous() {
566	<	if (nextIndex == 0)
567	<	throw new NoSuchElementException();
568	<
569	<	lastReturned = next = next.previous;
570	<	nextIndex--;
571	<	checkForComodification();
572	<	return lastReturned.element;
573	<	}
574	<
575	<	public int nextIndex() {
576	<	return nextIndex;
577	<	}
578	<
579	<	public int previousIndex() {
580	<	return nextIndex-1;
581	<	}
582	<
583	<	public void remove() {
733	>	public void remove() {
734		checkForComodification();
735	+	Entry<E> lastNext = lastReturned.next;
736		try {
737		LinkedList.this.remove(lastReturned);
738		} catch (NoSuchElementException e) {
739		throw new IllegalStateException();
740		}
741	<	if (next==lastReturned)
742	<	next = lastReturned.next;
741	>	if (next==lastReturned)
742	>	next = lastNext;
743		else
744	<	nextIndex--;
745	<	lastReturned = header;
746	<	expectedModCount++;
747	<	}
748	<
749	<	public void set(E o) {
750	<	if (lastReturned == header)
751	<	throw new IllegalStateException();
752	<	checkForComodification();
753	<	lastReturned.element = o;
754	<	}
755	<
756	<	public void add(E o) {
757	<	checkForComodification();
758	<	lastReturned = header;
759	<	addBefore(o, next);
760	<	nextIndex++;
761	<	expectedModCount++;
762	<	}
763	<
764	<	final void checkForComodification() {
765	<	if (modCount != expectedModCount)
766	<	throw new ConcurrentModificationException();
767	<	}
744	>	nextIndex--;
745	>	lastReturned = header;
746	>	expectedModCount++;
747	>	}
748	>
749	>	public void set(E o) {
750	>	if (lastReturned == header)
751	>	throw new IllegalStateException();
752	>	checkForComodification();
753	>	lastReturned.element = o;
754	>	}
755	>
756	>	public void add(E o) {
757	>	checkForComodification();
758	>	lastReturned = header;
759	>	addBefore(o, next);
760	>	nextIndex++;
761	>	expectedModCount++;
762	>	}
763	>
764	>	final void checkForComodification() {
765	>	if (modCount != expectedModCount)
766	>	throw new ConcurrentModificationException();
767	>	}
768		}
769
770		private static class Entry<E> {
771	<	E element;
772	<	Entry<E> next;
773	<	Entry<E> previous;
774	<
775	<	Entry(E element, Entry<E> next, Entry<E> previous) {
776	<	this.element = element;
777	<	this.next = next;
778	<	this.previous = previous;
779	<	}
771	>	E element;
772	>	Entry<E> next;
773	>	Entry<E> previous;
774	>
775	>	Entry(E element, Entry<E> next, Entry<E> previous) {
776	>	this.element = element;
777	>	this.next = next;
778	>	this.previous = previous;
779	>	}
780		}
781
782		private Entry<E> addBefore(E o, Entry<E> e) {
783	<	Entry<E> newEntry = new Entry<E>(o, e, e.previous);
784	<	newEntry.previous.next = newEntry;
785	<	newEntry.next.previous = newEntry;
786	<	size++;
787	<	modCount++;
788	<	return newEntry;
789	<	}
790	<
791	<	private void remove(Entry<E> e) {
792	<	if (e == header)
793	<	throw new NoSuchElementException();
794	<
795	<	e.previous.next = e.next;
796	<	e.next.previous = e.previous;
797	<	size--;
798	<	modCount++;
783	>	Entry<E> newEntry = new Entry<E>(o, e, e.previous);
784	>	newEntry.previous.next = newEntry;
785	>	newEntry.next.previous = newEntry;
786	>	size++;
787	>	modCount++;
788	>	return newEntry;
789	>	}
790	>
791	>	private E remove(Entry<E> e) {
792	>	if (e == header)
793	>	throw new NoSuchElementException();
794	>
795	>	E result = e.element;
796	>	e.previous.next = e.next;
797	>	e.next.previous = e.previous;
798	>	e.next = e.previous = null;
799	>	e.element = null;
800	>	size--;
801	>	modCount++;
802	>	return result;
803		}
804
805		/**
#	Line 655 | Line 810 | public class LinkedList<E>
810		*/
811		public Object clone() {
812		LinkedList<E> clone = null;
813	<	try {
814	<	clone = (LinkedList<E>) super.clone();
815	<	} catch (CloneNotSupportedException e) {
816	<	throw new InternalError();
817	<	}
813	>	try {
814	>	clone = (LinkedList<E>) super.clone();
815	>	} catch (CloneNotSupportedException e) {
816	>	throw new InternalError();
817	>	}
818
819		// Put clone into "virgin" state
820		clone.header = new Entry<E>(null, null, null);
#	Line 679 | Line 834 | public class LinkedList<E>
834		* in the correct order.
835		*
836		* @return an array containing all of the elements in this list
837	<	*         in the correct order.
837	>	*         in the correct order.
838		*/
839		public Object[] toArray() {
840	<	Object[] result = new Object[size];
840	>	Object[] result = new Object[size];
841		int i = 0;
842		for (Entry<E> e = header.next; e != header; e = e.next)
843		result[i++] = e.element;
844	<	return result;
844	>	return result;
845		}
846
847		/**
#	Line 704 | Line 859 | public class LinkedList<E>
859		* does not contain any null elements.
860		*
861		* @param a the array into which the elements of the list are to
862	<	*          be stored, if it is big enough; otherwise, a new array of the
863	<	*          same runtime type is allocated for this purpose.
862	>	*          be stored, if it is big enough; otherwise, a new array of the
863	>	*          same runtime type is allocated for this purpose.
864		* @return an array containing the elements of the list.
865		* @throws ArrayStoreException if the runtime type of a is not a
866		*         supertype of the runtime type of every element in this list.
#	Line 716 | Line 871 | public class LinkedList<E>
871		a = (T[])java.lang.reflect.Array.newInstance(
872		a.getClass().getComponentType(), size);
873		int i = 0;
874	<	Object[] result = a;
874	>	Object[] result = a;
875		for (Entry<E> e = header.next; e != header; e = e.next)
876		result[i++] = e.element;
877
#	Line 733 | Line 888 | public class LinkedList<E>
888		* is, serialize it).
889		*
890		* @serialData The size of the list (the number of elements it
891	<	*             contains) is emitted (int), followed by all of its
891	>	*             contains) is emitted (int), followed by all of its
892		* elements (each an Object) in the proper order.
893		*/
894		private void writeObject(java.io.ObjectOutputStream s)
895		throws java.io.IOException {
896	<	// Write out any hidden serialization magic
897	<	s.defaultWriteObject();
896	>	// Write out any hidden serialization magic
897	>	s.defaultWriteObject();
898
899		// Write out size
900		s.writeInt(size);
901
902	<	// Write out all elements in the proper order.
902	>	// Write out all elements in the proper order.
903		for (Entry e = header.next; e != header; e = e.next)
904		s.writeObject(e.element);
905		}
#	Line 755 | Line 910 | public class LinkedList<E>
910		*/
911		private void readObject(java.io.ObjectInputStream s)
912		throws java.io.IOException, ClassNotFoundException {
913	<	// Read in any hidden serialization magic
914	<	s.defaultReadObject();
913	>	// Read in any hidden serialization magic
914	>	s.defaultReadObject();
915
916		// Read in size
917		int size = s.readInt();
#	Line 765 | Line 920 | public class LinkedList<E>
920		header = new Entry<E>(null, null, null);
921		header.next = header.previous = header;
922
923	<	// Read in all elements in the proper order.
924	<	for (int i=0; i<size; i++)
923	>	// Read in all elements in the proper order.
924	>	for (int i=0; i<size; i++)
925		addBefore((E)s.readObject(), header);
926		}
927		}

Diff Legend

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