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.23 by jsr166, Mon Apr 18 05:18:29 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
8	<	package java.util;
8	>	package java.util;
9
10		/**
11		* Linked list implementation of the <tt>List</tt> interface.  Implements all
#	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 63 | Line 61 | package java.util;
61		*
62		* @author  Josh Bloch
63		* @version %I%, %G%
64	<	* @see     List
65	<	* @see     ArrayList
66	<	* @see     Vector
67	<	* @see     Collections#synchronizedList(List)
64	>	* @see     List
65	>	* @see     ArrayList
66	>	* @see     Vector
67	>	* @see     Collections#synchronizedList(List)
68		* @since 1.2
69		* @param <E> the type of elements held in this collection
70		*/
71
72		public class LinkedList<E>
73		extends AbstractSequentialList<E>
74	<	implements List<E>, Queue<E>, Cloneable, java.io.Serializable
74	>	implements List<E>, Deque<E>, Cloneable, java.io.Serializable
75		{
76		private transient Entry<E> header = new Entry<E>(null, null, null);
77		private transient int size = 0;
#	Line 93 | Line 91 | public class LinkedList<E>
91		* @param  c the collection whose elements are to be placed into this list.
92		* @throws NullPointerException if the specified collection is null.
93		*/
94	<	public LinkedList(Collection<? extends E> c) {
95	<	this();
96	<	addAll(c);
97	<	}
94	>	public LinkedList(Collection<? extends E> c) {
95	>	this();
96	>	addAll(c);
97	>	}
98
99		/**
100		* Returns the first element in this list.
#	Line 105 | Line 103 | public class LinkedList<E>
103		* @throws    NoSuchElementException if this list is empty.
104		*/
105		public E getFirst() {
106	<	if (size==0)
107	<	throw new NoSuchElementException();
106	>	if (size==0)
107	>	throw new NoSuchElementException();
108
109	<	return header.next.element;
109	>	return header.next.element;
110		}
111
112		/**
#	Line 118 | Line 116 | public class LinkedList<E>
116		* @throws    NoSuchElementException if this list is empty.
117		*/
118		public E getLast()  {
119	<	if (size==0)
120	<	throw new NoSuchElementException();
119	>	if (size==0)
120	>	throw new NoSuchElementException();
121
122	<	return header.previous.element;
122	>	return header.previous.element;
123		}
124
125		/**
#	Line 131 | Line 129 | public class LinkedList<E>
129		* @throws    NoSuchElementException if this list is empty.
130		*/
131		public E removeFirst() {
132	<	E first = header.next.element;
135	<	remove(header.next);
136	<	return first;
132	>	return remove(header.next);
133		}
134
135		/**
#	Line 143 | Line 139 | public class LinkedList<E>
139		* @throws    NoSuchElementException if this list is empty.
140		*/
141		public E removeLast() {
142	<	E last = header.previous.element;
147	<	remove(header.previous);
148	<	return last;
142	>	return remove(header.previous);
143		}
144
145		/**
#	Line 154 | Line 148 | public class LinkedList<E>
148		* @param o the element to be inserted at the beginning of this list.
149		*/
150		public void addFirst(E o) {
151	<	addBefore(o, header.next);
151	>	addBefore(o, header.next);
152		}
153
154		/**
155	<	* Appends the given element to the end of this list.  (Identical in
155	>	* Appends the given element at the end of this list.  (Identical in
156		* function to the <tt>add</tt> method; included only for consistency.)
157		*
158		* @param o the element to be inserted at the end of this list.
159		*/
160		public void addLast(E o) {
161	<	addBefore(o, header);
161	>	addBefore(o, header);
162		}
163
164		/**
#	Line 186 | Line 180 | public class LinkedList<E>
180		* @return the number of elements in this list.
181		*/
182		public int size() {
183	<	return size;
183	>	return size;
184		}
185
186		/**
187	<	* Appends the specified element to the end of this list.
187	>	* Appends the specified element at the end of this list.
188		*
189		* @param o element to be appended to this list.
190		* @return <tt>true</tt> (as per the general contract of
191		* <tt>Collection.add</tt>).
192		*/
193		public boolean add(E o) {
194	<	addBefore(o, header);
194	>	addBefore(o, header);
195		return true;
196		}
197
#	Line 231 | Line 225 | public class LinkedList<E>
225		}
226
227		/**
228	<	* Appends all of the elements in the specified collection to the end of
228	>	* Appends all of the elements in the specified collection at the end of
229		* this list, in the order that they are returned by the specified
230		* collection's iterator.  The behavior of this operation is undefined if
231		* the specified collection is modified while the operation is in
#	Line 255 | Line 249 | public class LinkedList<E>
249		* specified collection's iterator.
250		*
251		* @param index index at which to insert first element
252	<	*              from the specified collection.
252	>	*              from the specified collection.
253		* @param c elements to be inserted into this list.
254		* @return <tt>true</tt> if this list changed as a result of the call.
255		* @throws IndexOutOfBoundsException if the specified index is out of
#	Line 270 | Line 264 | public class LinkedList<E>
264		int numNew = a.length;
265		if (numNew==0)
266		return false;
267	<	modCount++;
267	>	modCount++;
268
269		Entry<E> successor = (index==size ? header : entry(index));
270		Entry<E> predecessor = successor.previous;
271	<	for (int i=0; i<numNew; i++) {
271	>	for (int i=0; i<numNew; i++) {
272		Entry<E> e = new Entry<E>((E)a[i], successor, predecessor);
273		predecessor.next = e;
274		predecessor = e;
#	Line 289 | Line 283 | public class LinkedList<E>
283		* Removes all of the elements from this list.
284		*/
285		public void clear() {
286	<	modCount++;
286	>	Entry<E> e = header.next;
287	>	while (e != header) {
288	>	Entry<E> next = e.next;
289	>	e.next = e.previous = null;
290	>	e.element = null;
291	>	e = next;
292	>	}
293		header.next = header.previous = header;
294		size = 0;
295	+	modCount++;
296		}
297
298
#	Line 303 | Line 304 | public class LinkedList<E>
304		* @param index index of element to return.
305		* @return the element at the specified position in this list.
306		*
307	<	* @throws IndexOutOfBoundsException if the specified index is is out of
307	>	* @throws IndexOutOfBoundsException if the specified index is out of
308		* range (<tt>index &lt; 0 || index &gt;= size()</tt>).
309		*/
310		public E get(int index) {
#	Line 318 | Line 319 | public class LinkedList<E>
319		* @param element element to be stored at the specified position.
320		* @return the element previously at the specified position.
321		* @throws IndexOutOfBoundsException if the specified index is out of
322	<	*            range (<tt>index &lt; 0 || index &gt;= size()</tt>).
322	>	*            range (<tt>index &lt; 0 || index &gt;= size()</tt>).
323		*/
324		public E set(int index, E element) {
325		Entry<E> e = entry(index);
#	Line 336 | Line 337 | public class LinkedList<E>
337		* @param element element to be inserted.
338		*
339		* @throws IndexOutOfBoundsException if the specified index is out of
340	<	*            range (<tt>index &lt; 0 || index &gt; size()</tt>).
340	>	*            range (<tt>index &lt; 0 || index &gt; size()</tt>).
341		*/
342		public void add(int index, E element) {
343		addBefore(element, (index==size ? header : entry(index)));
#	Line 351 | Line 352 | public class LinkedList<E>
352		* @return the element previously at the specified position.
353		*
354		* @throws IndexOutOfBoundsException if the specified index is out of
355	<	*            range (<tt>index &lt; 0 || index &gt;= size()</tt>).
355	>	*            range (<tt>index &lt; 0 || index &gt;= size()</tt>).
356		*/
357		public E remove(int index) {
358	<	Entry<E> e = entry(index);
358	<	remove(e);
359	<	return e.element;
358	>	return remove(entry(index));
359		}
360
361		/**
#	Line 389 | Line 388 | public class LinkedList<E>
388		*
389		* @param o element to search for.
390		* @return the index in this list of the first occurrence of the
391	<	*         specified element, or -1 if the list does not contain this
392	<	*         element.
391	>	*         specified element, or -1 if the list does not contain this
392	>	*         element.
393		*/
394		public int indexOf(Object o) {
395		int index = 0;
#	Line 419 | Line 418 | public class LinkedList<E>
418		*
419		* @param o element to search for.
420		* @return the index in this list of the last occurrence of the
421	<	*         specified element, or -1 if the list does not contain this
422	<	*         element.
421	>	*         specified element, or -1 if the list does not contain this
422	>	*         element.
423		*/
424		public int lastIndexOf(Object o) {
425		int index = size;
#	Line 444 | Line 443 | public class LinkedList<E>
443
444		/**
445		* Retrieves, but does not remove, the head (first element) of this list.
446	<	* @return the head of this queue, or <tt>null</tt> if this queue is empty.
446	>	* @return the head of this list, or <tt>null</tt> if this list is empty.
447		* @since 1.5
448		*/
449		public E peek() {
#	Line 455 | Line 454 | public class LinkedList<E>
454
455		/**
456		* Retrieves, but does not remove, the head (first element) of this list.
457	<	* @return the head of this queue.
458	<	* @throws NoSuchElementException if this queue is empty.
457	>	* @return the head of this list.
458	>	* @throws NoSuchElementException if this list is empty.
459		* @since 1.5
460		*/
461		public E element() {
#	Line 465 | Line 464 | public class LinkedList<E>
464
465		/**
466		* Retrieves and removes the head (first element) of this list.
467	<	* @return the head of this queue, or <tt>null</tt> if this queue is empty.
467	>	* @return the head of this list, or <tt>null</tt> if this list is empty.
468		* @since 1.5
469		*/
470		public E poll() {
#	Line 476 | Line 475 | public class LinkedList<E>
475
476		/**
477		* Retrieves and removes the head (first element) of this list.
478	<	* @return the head of this queue.
479	<	* @throws NoSuchElementException if this queue is empty.
478	>	* @return the head of this list.
479	>	* @throws NoSuchElementException if this list is empty.
480		* @since 1.5
481		*/
482		public E remove() {
#	Line 496 | Line 495 | public class LinkedList<E>
495		return add(o);
496		}
497
498	+	// Deque operations
499	+	/**
500	+	* Inserts the specified element at the front of this list.
501	+	*
502	+	* @param e the element to insert
503	+	* @return <tt>true</tt> (as per the spec for {@link Deque#offerFirst})
504	+	* @since 1.6
505	+	*/
506	+	public boolean offerFirst(E e) {
507	+	addFirst(e);
508	+	return true;
509	+	}
510	+
511	+	/**
512	+	* Inserts the specified element at the end of this list.
513	+	*
514	+	* @param e the element to insert
515	+	* @return <tt>true</tt> (as per the spec for {@link Deque#offerLast})
516	+	* @since 1.6
517	+	*/
518	+	public boolean offerLast(E e) {
519	+	addLast(e);
520	+	return true;
521	+	}
522	+
523	+	/**
524	+	* Retrieves, but does not remove, the first element of this list,
525	+	* returning <tt>null</tt> if this list is empty.
526	+	*
527	+	* @return the first element of this list, or <tt>null</tt> if
528	+	*     this list is empty
529	+	* @since 1.6
530	+	*/
531	+	public E peekFirst() {
532	+	if (size==0)
533	+	return null;
534	+	return getFirst();
535	+	}
536	+
537	+	/**
538	+	* Retrieves, but does not remove, the last element of this list,
539	+	* returning <tt>null</tt> if this list is empty.
540	+	*
541	+	* @return the last element of this list, or <tt>null</tt> if this list
542	+	*     is empty
543	+	* @since 1.6
544	+	*/
545	+	public E peekLast() {
546	+	if (size==0)
547	+	return null;
548	+	return getLast();
549	+	}
550	+
551	+	/**
552	+	* Retrieves and removes the first element of this list, or
553	+	* <tt>null</tt> if this list is empty.
554	+	*
555	+	* @return the first element of this list, or <tt>null</tt> if
556	+	*     this list is empty
557	+	* @since 1.6
558	+	*/
559	+	public E pollFirst() {
560	+	if (size==0)
561	+	return null;
562	+	return removeFirst();
563	+	}
564	+
565	+	/**
566	+	* Retrieves and removes the last element of this list, or
567	+	* <tt>null</tt> if this list is empty.
568	+	*
569	+	* @return the last element of this list, or <tt>null</tt> if
570	+	*     this list is empty
571	+	* @since 1.6
572	+	*/
573	+	public E pollLast() {
574	+	if (size==0)
575	+	return null;
576	+	return removeLast();
577	+	}
578	+
579	+	/**
580	+	* Pushes an element onto the stack represented by this list.  In other
581	+	* words, inserts the element at the front of this list.
582	+	*
583	+	* <p>This method is equivalent to {@link #addFirst}.
584	+	*
585	+	* @param e the element to push
586	+	* @since 1.6
587	+	*/
588	+	public void push(E e) {
589	+	addFirst(e);
590	+	}
591	+
592	+	/**
593	+	* Pops an element from the stack represented by this list.  In other
594	+	* words, removes and returns the first element of this list.
595	+	*
596	+	* <p>This method is equivalent to {@link #removeFirst()}.
597	+	*
598	+	* @return the element at the front of this list (which is the top
599	+	*     of the stack represented by this list)
600	+	* @throws NoSuchElementException if this list is empty
601	+	* @since 1.6
602	+	*/
603	+	public E pop() {
604	+	return removeFirst();
605	+	}
606	+
607	+	/**
608	+	* Removes the first occurrence of the specified element in this
609	+	* list (when traversing the list from head to tail).  If the list
610	+	* does not contain the element, it is unchanged.
611	+	*
612	+	* @param o element to be removed from this list, if present
613	+	* @return <tt>true</tt> if the list contained the specified element
614	+	* @since 1.6
615	+	*/
616	+	public boolean removeFirstOccurrence(Object o) {
617	+	return remove(o);
618	+	}
619	+
620	+	/**
621	+	* Removes the last occurrence of the specified element in this
622	+	* list (when traversing the list from head to tail).  If the list
623	+	* does not contain the element, it is unchanged.
624	+	*
625	+	* @param o element to be removed from this list, if present
626	+	* @return <tt>true</tt> if the list contained the specified element
627	+	* @since 1.6
628	+	*/
629	+	public boolean removeLastOccurrence(Object o) {
630	+	if (o==null) {
631	+	for (Entry e = header.previous; e != header; e = e.previous) {
632	+	if (e.element==null) {
633	+	remove(e);
634	+	return true;
635	+	}
636	+	}
637	+	} else {
638	+	for (Entry e = header.previous; e != header; e = e.previous) {
639	+	if (o.equals(e.element)) {
640	+	remove(e);
641	+	return true;
642	+	}
643	+	}
644	+	}
645	+	return false;
646	+	}
647	+
648		/**
649		* Returns a list-iterator of the elements in this list (in proper
650		* sequence), starting at the specified position in the list.
#	Line 511 | Line 660 | public class LinkedList<E>
660		* time in the future.
661		*
662		* @param index index of first element to be returned from the
663	<	*              list-iterator (by a call to <tt>next</tt>).
663	>	*              list-iterator (by a call to <tt>next</tt>).
664		* @return a ListIterator of the elements in this list (in proper
665	<	*         sequence), starting at the specified position in the list.
665	>	*         sequence), starting at the specified position in the list.
666		* @throws    IndexOutOfBoundsException if index is out of range
667	<	*            (<tt>index &lt; 0 || index &gt; size()</tt>).
667	>	*            (<tt>index &lt; 0 || index &gt; size()</tt>).
668		* @see List#listIterator(int)
669		*/
670		public ListIterator<E> listIterator(int index) {
671	<	return new ListItr(index);
671	>	return new ListItr(index);
672		}
673
674		private class ListItr implements ListIterator<E> {
675	<	private Entry<E> lastReturned = header;
676	<	private Entry<E> next;
677	<	private int nextIndex;
678	<	private int expectedModCount = modCount;
679	<
680	<	ListItr(int index) {
681	<	if (index < 0 || index > size)
682	<	throw new IndexOutOfBoundsException("Index: "+index+
683	<	", Size: "+size);
684	<	if (index < (size >> 1)) {
685	<	next = header.next;
686	<	for (nextIndex=0; nextIndex<index; nextIndex++)
687	<	next = next.next;
688	<	} else {
689	<	next = header;
690	<	for (nextIndex=size; nextIndex>index; nextIndex--)
691	<	next = next.previous;
692	<	}
693	<	}
675	>	private Entry<E> lastReturned = header;
676	>	private Entry<E> next;
677	>	private int nextIndex;
678	>	private int expectedModCount = modCount;
679	>
680	>	ListItr(int index) {
681	>	if (index < 0 || index > size)
682	>	throw new IndexOutOfBoundsException("Index: "+index+
683	>	", Size: "+size);
684	>	if (index < (size >> 1)) {
685	>	next = header.next;
686	>	for (nextIndex=0; nextIndex<index; nextIndex++)
687	>	next = next.next;
688	>	} else {
689	>	next = header;
690	>	for (nextIndex=size; nextIndex>index; nextIndex--)
691	>	next = next.previous;
692	>	}
693	>	}
694	>
695	>	public boolean hasNext() {
696	>	return nextIndex != size;
697	>	}
698	>
699	>	public E next() {
700	>	checkForComodification();
701	>	if (nextIndex == size)
702	>	throw new NoSuchElementException();
703	>
704	>	lastReturned = next;
705	>	next = next.next;
706	>	nextIndex++;
707	>	return lastReturned.element;
708	>	}
709	>
710	>	public boolean hasPrevious() {
711	>	return nextIndex != 0;
712	>	}
713	>
714	>	public E previous() {
715	>	if (nextIndex == 0)
716	>	throw new NoSuchElementException();
717	>
718	>	lastReturned = next = next.previous;
719	>	nextIndex--;
720	>	checkForComodification();
721	>	return lastReturned.element;
722	>	}
723	>
724	>	public int nextIndex() {
725	>	return nextIndex;
726	>	}
727	>
728	>	public int previousIndex() {
729	>	return nextIndex-1;
730	>	}
731
732	<	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() {
732	>	public void remove() {
733		checkForComodification();
734	+	Entry<E> lastNext = lastReturned.next;
735		try {
736		LinkedList.this.remove(lastReturned);
737		} catch (NoSuchElementException e) {
738		throw new IllegalStateException();
739		}
740	<	if (next==lastReturned)
741	<	next = lastReturned.next;
740	>	if (next==lastReturned)
741	>	next = lastNext;
742		else
743	<	nextIndex--;
744	<	lastReturned = header;
745	<	expectedModCount++;
746	<	}
747	<
748	<	public void set(E o) {
749	<	if (lastReturned == header)
750	<	throw new IllegalStateException();
751	<	checkForComodification();
752	<	lastReturned.element = o;
753	<	}
754	<
755	<	public void add(E o) {
756	<	checkForComodification();
757	<	lastReturned = header;
758	<	addBefore(o, next);
759	<	nextIndex++;
760	<	expectedModCount++;
761	<	}
762	<
763	<	final void checkForComodification() {
764	<	if (modCount != expectedModCount)
765	<	throw new ConcurrentModificationException();
766	<	}
743	>	nextIndex--;
744	>	lastReturned = header;
745	>	expectedModCount++;
746	>	}
747	>
748	>	public void set(E o) {
749	>	if (lastReturned == header)
750	>	throw new IllegalStateException();
751	>	checkForComodification();
752	>	lastReturned.element = o;
753	>	}
754	>
755	>	public void add(E o) {
756	>	checkForComodification();
757	>	lastReturned = header;
758	>	addBefore(o, next);
759	>	nextIndex++;
760	>	expectedModCount++;
761	>	}
762	>
763	>	final void checkForComodification() {
764	>	if (modCount != expectedModCount)
765	>	throw new ConcurrentModificationException();
766	>	}
767		}
768
769		private static class Entry<E> {
770	<	E element;
771	<	Entry<E> next;
772	<	Entry<E> previous;
773	<
774	<	Entry(E element, Entry<E> next, Entry<E> previous) {
775	<	this.element = element;
776	<	this.next = next;
777	<	this.previous = previous;
778	<	}
770	>	E element;
771	>	Entry<E> next;
772	>	Entry<E> previous;
773	>
774	>	Entry(E element, Entry<E> next, Entry<E> previous) {
775	>	this.element = element;
776	>	this.next = next;
777	>	this.previous = previous;
778	>	}
779		}
780
781		private Entry<E> addBefore(E o, Entry<E> e) {
782	<	Entry<E> newEntry = new Entry<E>(o, e, e.previous);
783	<	newEntry.previous.next = newEntry;
784	<	newEntry.next.previous = newEntry;
785	<	size++;
786	<	modCount++;
787	<	return newEntry;
788	<	}
789	<
790	<	private void remove(Entry<E> e) {
791	<	if (e == header)
792	<	throw new NoSuchElementException();
793	<
794	<	e.previous.next = e.next;
795	<	e.next.previous = e.previous;
796	<	size--;
797	<	modCount++;
782	>	Entry<E> newEntry = new Entry<E>(o, e, e.previous);
783	>	newEntry.previous.next = newEntry;
784	>	newEntry.next.previous = newEntry;
785	>	size++;
786	>	modCount++;
787	>	return newEntry;
788	>	}
789	>
790	>	private E remove(Entry<E> e) {
791	>	if (e == header)
792	>	throw new NoSuchElementException();
793	>
794	>	E result = e.element;
795	>	e.previous.next = e.next;
796	>	e.next.previous = e.previous;
797	>	e.next = e.previous = null;
798	>	e.element = null;
799	>	size--;
800	>	modCount++;
801	>	return result;
802		}
803
804		/**
#	Line 655 | Line 809 | public class LinkedList<E>
809		*/
810		public Object clone() {
811		LinkedList<E> clone = null;
812	<	try {
813	<	clone = (LinkedList<E>) super.clone();
814	<	} catch (CloneNotSupportedException e) {
815	<	throw new InternalError();
816	<	}
812	>	try {
813	>	clone = (LinkedList<E>) super.clone();
814	>	} catch (CloneNotSupportedException e) {
815	>	throw new InternalError();
816	>	}
817
818		// Put clone into "virgin" state
819		clone.header = new Entry<E>(null, null, null);
#	Line 679 | Line 833 | public class LinkedList<E>
833		* in the correct order.
834		*
835		* @return an array containing all of the elements in this list
836	<	*         in the correct order.
836	>	*         in the correct order.
837		*/
838		public Object[] toArray() {
839	<	Object[] result = new Object[size];
839	>	Object[] result = new Object[size];
840		int i = 0;
841		for (Entry<E> e = header.next; e != header; e = e.next)
842		result[i++] = e.element;
843	<	return result;
843	>	return result;
844		}
845
846		/**
#	Line 704 | Line 858 | public class LinkedList<E>
858		* does not contain any null elements.
859		*
860		* @param a the array into which the elements of the list are to
861	<	*          be stored, if it is big enough; otherwise, a new array of the
862	<	*          same runtime type is allocated for this purpose.
861	>	*          be stored, if it is big enough; otherwise, a new array of the
862	>	*          same runtime type is allocated for this purpose.
863		* @return an array containing the elements of the list.
864		* @throws ArrayStoreException if the runtime type of a is not a
865		*         supertype of the runtime type of every element in this list.
#	Line 716 | Line 870 | public class LinkedList<E>
870		a = (T[])java.lang.reflect.Array.newInstance(
871		a.getClass().getComponentType(), size);
872		int i = 0;
873	<	Object[] result = a;
873	>	Object[] result = a;
874		for (Entry<E> e = header.next; e != header; e = e.next)
875		result[i++] = e.element;
876
#	Line 733 | Line 887 | public class LinkedList<E>
887		* is, serialize it).
888		*
889		* @serialData The size of the list (the number of elements it
890	<	*             contains) is emitted (int), followed by all of its
890	>	*             contains) is emitted (int), followed by all of its
891		* elements (each an Object) in the proper order.
892		*/
893		private void writeObject(java.io.ObjectOutputStream s)
894		throws java.io.IOException {
895	<	// Write out any hidden serialization magic
896	<	s.defaultWriteObject();
895	>	// Write out any hidden serialization magic
896	>	s.defaultWriteObject();
897
898		// Write out size
899		s.writeInt(size);
900
901	<	// Write out all elements in the proper order.
901	>	// Write out all elements in the proper order.
902		for (Entry e = header.next; e != header; e = e.next)
903		s.writeObject(e.element);
904		}
#	Line 755 | Line 909 | public class LinkedList<E>
909		*/
910		private void readObject(java.io.ObjectInputStream s)
911		throws java.io.IOException, ClassNotFoundException {
912	<	// Read in any hidden serialization magic
913	<	s.defaultReadObject();
912	>	// Read in any hidden serialization magic
913	>	s.defaultReadObject();
914
915		// Read in size
916		int size = s.readInt();
#	Line 765 | Line 919 | public class LinkedList<E>
919		header = new Entry<E>(null, null, null);
920		header.next = header.previous = header;
921
922	<	// Read in all elements in the proper order.
923	<	for (int i=0; i<size; i++)
922	>	// Read in all elements in the proper order.
923	>	for (int i=0; i<size; i++)
924		addBefore((E)s.readObject(), header);
925		}
926		}

Diff Legend

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