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.28 by jsr166, Mon May 16 05:17:07 2005 UTC vs.
Revision 1.53 by jsr166, Thu Dec 2 04:17:19 2010 UTC

#	Line 1 | Line 1
1		/*
2	<	* %W% %E%
2	>	* Copyright (c) 1997, 2006, Oracle and/or its affiliates. All rights reserved.
3	>	* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4		*
5	<	* Copyright 2005 Sun Microsystems, Inc. All rights reserved.
6	<	* SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
5	>	* This code is free software; you can redistribute it and/or modify it
6	>	* under the terms of the GNU General Public License version 2 only, as
7	>	* published by the Free Software Foundation.  Sun designates this
8	>	* particular file as subject to the "Classpath" exception as provided
9	>	* by Sun in the LICENSE file that accompanied this code.
10	>	*
11	>	* This code is distributed in the hope that it will be useful, but WITHOUT
12	>	* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13	>	* FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
14	>	* version 2 for more details (a copy is included in the LICENSE file that
15	>	* accompanied this code).
16	>	*
17	>	* You should have received a copy of the GNU General Public License version
18	>	* 2 along with this work; if not, write to the Free Software Foundation,
19	>	* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20	>	*
21	>	* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22	>	* or visit www.oracle.com if you need additional information or have any
23	>	* questions.
24		*/
25
26		package java.util;
27
28		/**
29	<	* Linked list implementation of the <tt>List</tt> 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,
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, {@linkplain Queue queue}, or {@linkplain Deque
18	<	* double-ended queue}. <p>
19	<	*
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>, along with other stack and deque operations.<p>
29	>	* Doubly-linked list implementation of the {@code List} and {@code Deque}
30	>	* interfaces.  Implements all optional list operations, and permits all
31	>	* elements (including {@code null}).
32		*
33	<	* All of the operations perform as could be expected for a doubly-linked
33	>	* <p>All of the operations perform as could be expected for a doubly-linked
34		* list.  Operations that index into the list will traverse the list from
35	<	* the beginning or the end, whichever is closer to the specified index.<p>
35	>	* the beginning or the end, whichever is closer to the specified index.
36	>	*
37	>	* <p><strong>Note that this implementation is not synchronized.</strong>
38	>	* If multiple threads access a linked list concurrently, and at least
39	>	* one of the threads modifies the list structurally, it <i>must</i> be
40	>	* synchronized externally.  (A structural modification is any operation
41	>	* that adds or deletes one or more elements; merely setting the value of
42	>	* an element is not a structural modification.)  This is typically
43	>	* accomplished by synchronizing on some object that naturally
44	>	* encapsulates the list.
45		*
46	<	* <b>Note that this implementation is not synchronized.</b> If multiple
47	<	* threads access a list concurrently, and at least one of the threads
48	<	* modifies the list structurally, it <i>must</i> be synchronized
49	<	* externally.  (A structural modification is any operation that adds or
50	<	* deletes one or more elements; merely setting the value of an element is not
33	<	* a structural modification.)  This is typically accomplished by
34	<	* synchronizing on some object that naturally encapsulates the list.  If no
35	<	* such object exists, the list should be "wrapped" using the
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>
46	>	* If no such object exists, the list should be "wrapped" using the
47	>	* {@link Collections#synchronizedList Collections.synchronizedList}
48	>	* method.  This is best done at creation time, to prevent accidental
49	>	* unsynchronized access to the list:<pre>
50	>	*   List list = Collections.synchronizedList(new LinkedList(...));</pre>
51		*
52	<	* <p>The iterators returned by this class's <tt>iterator</tt> and
53	<	* <tt>listIterator</tt> methods are <i>fail-fast</i>: if the list is
52	>	* <p>The iterators returned by this class's {@code iterator} and
53	>	* {@code listIterator} methods are <i>fail-fast</i>: if the list is
54		* structurally modified at any time after the iterator is created, in
55	<	* any way except through the Iterator's own <tt>remove</tt> or
56	<	* <tt>add</tt> methods, the iterator will throw a {@link
55	>	* any way except through the Iterator's own {@code remove} or
56	>	* {@code add} methods, the iterator will throw a {@link
57		* ConcurrentModificationException}.  Thus, in the face of concurrent
58		* modification, the iterator fails quickly and cleanly, rather than
59		* risking arbitrary, non-deterministic behavior at an undetermined
#	Line 51 | Line 62 | package java.util;
62		* <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
63		* as it is, generally speaking, impossible to make any hard guarantees in the
64		* presence of unsynchronized concurrent modification.  Fail-fast iterators
65	<	* throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
65	>	* throw {@code ConcurrentModificationException} on a best-effort basis.
66		* Therefore, it would be wrong to write a program that depended on this
67		* exception for its correctness:   <i>the fail-fast behavior of iterators
68		* should be used only to detect bugs.</i>
69		*
70		* <p>This class is a member of the
71	<	* <a href="{@docRoot}/../guide/collections/index.html">
71	>	* <a href="{@docRoot}/../technotes/guides/collections/index.html">
72		* Java Collections Framework</a>.
73		*
74		* @author  Josh Bloch
75	<	* @version %I%, %G%
76	<	* @see     List
66	<	* @see     ArrayList
67	<	* @see     Vector
68	<	* @see     Collections#synchronizedList(List)
75	>	* @see     List
76	>	* @see     ArrayList
77		* @since 1.2
78		* @param <E> the type of elements held in this collection
79		*/
#	Line 74 | Line 82 | public class LinkedList<E>
82		extends AbstractSequentialList<E>
83		implements List<E>, Deque<E>, Cloneable, java.io.Serializable
84		{
85	<	private transient Entry<E> header = new Entry<E>(null, null, null);
86	<	private transient int size = 0;
85	>	transient int size = 0;
86	>
87	>	/**
88	>	* Pointer to first node.
89	>	* Invariant: (first == null && last == null) ||
90	>	*            (first.prev == null && first.item != null)
91	>	*/
92	>	transient Node<E> first;
93	>
94	>	/**
95	>	* Pointer to last node.
96	>	* Invariant: (first == null && last == null) ||
97	>	*            (last.next == null && last.item != null)
98	>	*/
99	>	transient Node<E> last;
100
101		/**
102		* Constructs an empty list.
103		*/
104		public LinkedList() {
84	–	header.next = header.previous = header;
105		}
106
107		/**
#	Line 92 | Line 112 | public class LinkedList<E>
112		* @param  c the collection whose elements are to be placed into this list
113		* @throws NullPointerException if the specified collection is null
114		*/
115	<	public LinkedList(Collection<? extends E> c) {
116	<	this();
117	<	addAll(c);
118	<	}
115	>	public LinkedList(Collection<? extends E> c) {
116	>	this();
117	>	addAll(c);
118	>	}
119	>
120	>	/**
121	>	* Links e as first element.
122	>	*/
123	>	private void linkFirst(E e) {
124	>	final Node<E> f = first;
125	>	final Node<E> newNode = new Node<E>(null, e, f);
126	>	first = newNode;
127	>	if (f == null)
128	>	last = newNode;
129	>	else
130	>	f.prev = newNode;
131	>	size++;
132	>	modCount++;
133	>	}
134	>
135	>	/**
136	>	* Links e as last element.
137	>	*/
138	>	void linkLast(E e) {
139	>	final Node<E> l = last;
140	>	final Node<E> newNode = new Node<E>(l, e, null);
141	>	last = newNode;
142	>	if (l == null)
143	>	first = newNode;
144	>	else
145	>	l.next = newNode;
146	>	size++;
147	>	modCount++;
148	>	}
149	>
150	>	/**
151	>	* Inserts element e before non-null Node succ.
152	>	*/
153	>	void linkBefore(E e, Node<E> succ) {
154	>	// assert succ != null;
155	>	final Node<E> pred = succ.prev;
156	>	final Node<E> newNode = new Node<E>(pred, e, succ);
157	>	succ.prev = newNode;
158	>	if (pred == null)
159	>	first = newNode;
160	>	else
161	>	pred.next = newNode;
162	>	size++;
163	>	modCount++;
164	>	}
165	>
166	>	/**
167	>	* Unlinks non-null first node f.
168	>	*/
169	>	private E unlinkFirst(Node<E> f) {
170	>	// assert f == first && f != null;
171	>	final E element = f.item;
172	>	final Node<E> next = f.next;
173	>	f.item = null;
174	>	f.next = null; // help GC
175	>	first = next;
176	>	if (next == null)
177	>	last = null;
178	>	else
179	>	next.prev = null;
180	>	size--;
181	>	modCount++;
182	>	return element;
183	>	}
184	>
185	>	/**
186	>	* Unlinks non-null last node l.
187	>	*/
188	>	private E unlinkLast(Node<E> l) {
189	>	// assert l == last && l != null;
190	>	final E element = l.item;
191	>	final Node<E> prev = l.prev;
192	>	l.item = null;
193	>	l.prev = null; // help GC
194	>	last = prev;
195	>	if (prev == null)
196	>	first = null;
197	>	else
198	>	prev.next = null;
199	>	size--;
200	>	modCount++;
201	>	return element;
202	>	}
203	>
204	>	/**
205	>	* Unlinks non-null node x.
206	>	*/
207	>	E unlink(Node<E> x) {
208	>	// assert x != null;
209	>	final E element = x.item;
210	>	final Node<E> next = x.next;
211	>	final Node<E> prev = x.prev;
212	>
213	>	if (prev == null) {
214	>	first = next;
215	>	} else {
216	>	prev.next = next;
217	>	x.prev = null;
218	>	}
219	>
220	>	if (next == null) {
221	>	last = prev;
222	>	} else {
223	>	next.prev = prev;
224	>	x.next = null;
225	>	}
226	>
227	>	x.item = null;
228	>	size--;
229	>	modCount++;
230	>	return element;
231	>	}
232
233		/**
234		* Returns the first element in this list.
#	Line 104 | Line 237 | public class LinkedList<E>
237		* @throws NoSuchElementException if this list is empty
238		*/
239		public E getFirst() {
240	<	if (size==0)
241	<	throw new NoSuchElementException();
242	<
243	<	return header.next.element;
240	>	final Node<E> f = first;
241	>	if (f == null)
242	>	throw new NoSuchElementException();
243	>	return f.item;
244		}
245
246		/**
#	Line 116 | Line 249 | public class LinkedList<E>
249		* @return the last element in this list
250		* @throws NoSuchElementException if this list is empty
251		*/
252	<	public E getLast()  {
253	<	if (size==0)
254	<	throw new NoSuchElementException();
255	<
256	<	return header.previous.element;
252	>	public E getLast() {
253	>	final Node<E> l = last;
254	>	if (l == null)
255	>	throw new NoSuchElementException();
256	>	return l.item;
257		}
258
259		/**
#	Line 130 | Line 263 | public class LinkedList<E>
263		* @throws NoSuchElementException if this list is empty
264		*/
265		public E removeFirst() {
266	<	return remove(header.next);
266	>	final Node<E> f = first;
267	>	if (f == null)
268	>	throw new NoSuchElementException();
269	>	return unlinkFirst(f);
270		}
271
272		/**
#	Line 140 | Line 276 | public class LinkedList<E>
276		* @throws NoSuchElementException if this list is empty
277		*/
278		public E removeLast() {
279	<	return remove(header.previous);
279	>	final Node<E> l = last;
280	>	if (l == null)
281	>	throw new NoSuchElementException();
282	>	return unlinkLast(l);
283		}
284
285		/**
286	<	* Inserts the given element at the beginning of this list.
286	>	* Inserts the specified element at the beginning of this list.
287		*
288	<	* @param e the element to be inserted at the beginning of this list
288	>	* @param e the element to add
289		*/
290		public void addFirst(E e) {
291	<	addBefore(e, header.next);
291	>	linkFirst(e);
292		}
293
294		/**
295	<	* Appends the given element to the end of this list.  (Identical in
157	<	* function to the <tt>add</tt> method; included only for consistency.)
295	>	* Appends the specified element to the end of this list.
296		*
297	<	* @param e the element to be inserted at the end of this list
297	>	* <p>This method is equivalent to {@link #add}.
298	>	*
299	>	* @param e the element to add
300		*/
301		public void addLast(E e) {
302	<	addBefore(e, header);
302	>	linkLast(e);
303		}
304
305		/**
306	<	* Returns <tt>true</tt> if this list contains the specified element.
307	<	* More formally, returns <tt>true</tt> if and only if this list contains
308	<	* at least one element <tt>e</tt> such that
306	>	* Returns {@code true} if this list contains the specified element.
307	>	* More formally, returns {@code true} if and only if this list contains
308	>	* at least one element {@code e} such that
309		* <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>.
310		*
311		* @param o element whose presence in this list is to be tested
312	<	* @return <tt>true</tt> if this list contains the specified element
312	>	* @return {@code true} if this list contains the specified element
313		*/
314		public boolean contains(Object o) {
315		return indexOf(o) != -1;
#	Line 181 | Line 321 | public class LinkedList<E>
321		* @return the number of elements in this list
322		*/
323		public int size() {
324	<	return size;
324	>	return size;
325		}
326
327		/**
328		* Appends the specified element to the end of this list.
329		*
330	+	* <p>This method is equivalent to {@link #addLast}.
331	+	*
332		* @param e element to be appended to this list
333	<	* @return <tt>true</tt> (as per the spec for {@link Collection#add})
333	>	* @return {@code true} (as specified by {@link Collection#add})
334		*/
335		public boolean add(E e) {
336	<	addBefore(e, header);
336	>	linkLast(e);
337		return true;
338		}
339
#	Line 199 | Line 341 | public class LinkedList<E>
341		* Removes the first occurrence of the specified element from this list,
342		* if it is present.  If this list does not contain the element, it is
343		* unchanged.  More formally, removes the element with the lowest index
344	<	* <tt>i</tt> such that
344	>	* {@code i} such that
345		* <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>
346	<	* (if such an element exists).  Returns <tt>true</tt> if this list
346	>	* (if such an element exists).  Returns {@code true} if this list
347		* contained the specified element (or equivalently, if this list
348		* changed as a result of the call).
349		*
350		* @param o element to be removed from this list, if present
351	<	* @return <tt>true</tt> if this list contained the specified element
351	>	* @return {@code true} if this list contained the specified element
352		*/
353		public boolean remove(Object o) {
354	<	if (o==null) {
355	<	for (Entry<E> e = header.next; e != header; e = e.next) {
356	<	if (e.element==null) {
357	<	remove(e);
354	>	if (o == null) {
355	>	for (Node<E> x = first; x != null; x = x.next) {
356	>	if (x.item == null) {
357	>	unlink(x);
358		return true;
359		}
360		}
361		} else {
362	<	for (Entry<E> e = header.next; e != header; e = e.next) {
363	<	if (o.equals(e.element)) {
364	<	remove(e);
362	>	for (Node<E> x = first; x != null; x = x.next) {
363	>	if (o.equals(x.item)) {
364	>	unlink(x);
365		return true;
366		}
367		}
#	Line 232 | Line 374 | public class LinkedList<E>
374		* this list, in the order that they are returned by the specified
375		* collection's iterator.  The behavior of this operation is undefined if
376		* the specified collection is modified while the operation is in
377	<	* progress.  (This implies that the behavior of this call is undefined if
378	<	* the specified Collection is this list, and this list is nonempty.)
377	>	* progress.  (Note that this will occur if the specified collection is
378	>	* this list, and it's nonempty.)
379		*
380	<	* @param c the elements to be inserted into this list
381	<	* @return <tt>true</tt> if this list changed as a result of the call
380	>	* @param c collection containing elements to be added to this list
381	>	* @return {@code true} if this list changed as a result of the call
382		* @throws NullPointerException if the specified collection is null
383		*/
384		public boolean addAll(Collection<? extends E> c) {
#	Line 253 | Line 395 | public class LinkedList<E>
395		*
396		* @param index index at which to insert the first element
397		*              from the specified collection
398	<	* @param c elements to be inserted into this list
399	<	* @return <tt>true</tt> if this list changed as a result of the call
398	>	* @param c collection containing elements to be added to this list
399	>	* @return {@code true} if this list changed as a result of the call
400		* @throws IndexOutOfBoundsException {@inheritDoc}
401		* @throws NullPointerException if the specified collection is null
402		*/
403		public boolean addAll(int index, Collection<? extends E> c) {
404	<	if (index < 0 || index > size)
405	<	throw new IndexOutOfBoundsException("Index: "+index+
264	<	", Size: "+size);
404	>	checkPositionIndex(index);
405	>
406		Object[] a = c.toArray();
407		int numNew = a.length;
408	<	if (numNew==0)
408	>	if (numNew == 0)
409		return false;
269	–	modCount++;
410
411	<	Entry<E> successor = (index==size ? header : entry(index));
412	<	Entry<E> predecessor = successor.previous;
413	<	for (int i=0; i<numNew; i++) {
414	<	Entry<E> e = new Entry<E>((E)a[i], successor, predecessor);
415	<	predecessor.next = e;
416	<	predecessor = e;
411	>	Node<E> pred, succ;
412	>	if (index == size) {
413	>	succ = null;
414	>	pred = last;
415	>	} else {
416	>	succ = node(index);
417	>	pred = succ.prev;
418	>	}
419	>
420	>	for (Object o : a) {
421	>	@SuppressWarnings("unchecked") E e = (E) o;
422	>	Node<E> newNode = new Node<E>(pred, e, null);
423	>	if (pred == null)
424	>	first = newNode;
425	>	else
426	>	pred.next = newNode;
427	>	pred = newNode;
428	>	}
429	>
430	>	if (succ == null) {
431	>	last = pred;
432	>	} else {
433	>	pred.next = succ;
434	>	succ.prev = pred;
435		}
278	–	successor.previous = predecessor;
436
437		size += numNew;
438	+	modCount++;
439		return true;
440		}
441
442		/**
443		* Removes all of the elements from this list.
444	+	* The list will be empty after this call returns.
445		*/
446		public void clear() {
447	<	Entry<E> e = header.next;
448	<	while (e != header) {
449	<	Entry<E> next = e.next;
450	<	e.next = e.previous = null;
451	<	e.element = null;
452	<	e = next;
447	>	// Clearing all of the links between nodes is "unnecessary", but:
448	>	// - helps a generational GC if the discarded nodes inhabit
449	>	//   more than one generation
450	>	// - is sure to free memory even if there is a reachable Iterator
451	>	for (Node<E> x = first; x != null; ) {
452	>	Node<E> next = x.next;
453	>	x.item = null;
454	>	x.next = null;
455	>	x.prev = null;
456	>	x = next;
457		}
458	<	header.next = header.previous = header;
458	>	first = last = null;
459		size = 0;
460	<	modCount++;
460	>	modCount++;
461		}
462
463
#	Line 308 | Line 471 | public class LinkedList<E>
471		* @throws IndexOutOfBoundsException {@inheritDoc}
472		*/
473		public E get(int index) {
474	<	return entry(index).element;
474	>	checkElementIndex(index);
475	>	return node(index).item;
476		}
477
478		/**
#	Line 321 | Line 485 | public class LinkedList<E>
485		* @throws IndexOutOfBoundsException {@inheritDoc}
486		*/
487		public E set(int index, E element) {
488	<	Entry<E> e = entry(index);
489	<	E oldVal = e.element;
490	<	e.element = element;
488	>	checkElementIndex(index);
489	>	Node<E> x = node(index);
490	>	E oldVal = x.item;
491	>	x.item = element;
492		return oldVal;
493		}
494
#	Line 337 | Line 502 | public class LinkedList<E>
502		* @throws IndexOutOfBoundsException {@inheritDoc}
503		*/
504		public void add(int index, E element) {
505	<	addBefore(element, (index==size ? header : entry(index)));
505	>	checkPositionIndex(index);
506	>
507	>	if (index == size)
508	>	linkLast(element);
509	>	else
510	>	linkBefore(element, node(index));
511		}
512
513		/**
#	Line 350 | Line 520 | public class LinkedList<E>
520		* @throws IndexOutOfBoundsException {@inheritDoc}
521		*/
522		public E remove(int index) {
523	<	return remove(entry(index));
523	>	checkElementIndex(index);
524	>	return unlink(node(index));
525		}
526
527		/**
528	<	* Returns the indexed entry.
528	>	* Tells if the argument is the index of an existing element.
529		*/
530	<	private Entry<E> entry(int index) {
531	<	if (index < 0 || index >= size)
532	<	throw new IndexOutOfBoundsException("Index: "+index+
533	<	", Size: "+size);
534	<	Entry<E> e = header;
530	>	private boolean isElementIndex(int index) {
531	>	return index >= 0 && index < size;
532	>	}
533	>
534	>	/**
535	>	* Tells if the argument is the index of a valid position for an
536	>	* iterator or an add operation.
537	>	*/
538	>	private boolean isPositionIndex(int index) {
539	>	return index >= 0 && index <= size;
540	>	}
541	>
542	>	/**
543	>	* Constructs an IndexOutOfBoundsException detail message.
544	>	* Of the many possible refactorings of the error handling code,
545	>	* this "outlining" performs best with both server and client VMs.
546	>	*/
547	>	private String outOfBoundsMsg(int index) {
548	>	return "Index: "+index+", Size: "+size;
549	>	}
550	>
551	>	private void checkElementIndex(int index) {
552	>	if (!isElementIndex(index))
553	>	throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
554	>	}
555	>
556	>	private void checkPositionIndex(int index) {
557	>	if (!isPositionIndex(index))
558	>	throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
559	>	}
560	>
561	>	/**
562	>	* Returns the (non-null) Node at the specified element index.
563	>	*/
564	>	Node<E> node(int index) {
565	>	// assert isElementIndex(index);
566	>
567		if (index < (size >> 1)) {
568	<	for (int i = 0; i <= index; i++)
569	<	e = e.next;
568	>	Node<E> x = first;
569	>	for (int i = 0; i < index; i++)
570	>	x = x.next;
571	>	return x;
572		} else {
573	<	for (int i = size; i > index; i--)
574	<	e = e.previous;
573	>	Node<E> x = last;
574	>	for (int i = size - 1; i > index; i--)
575	>	x = x.prev;
576	>	return x;
577		}
371	–	return e;
578		}
579
374	–
580		// Search Operations
581
582		/**
583	<	* Returns the index in this list of the first occurrence of the
584	<	* specified element, or -1 if the List does not contain this
585	<	* element.  More formally, returns the lowest index i such that
586	<	* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>, or -1 if
587	<	* there is no such index.
583	>	* Returns the index of the first occurrence of the specified element
584	>	* in this list, or -1 if this list does not contain the element.
585	>	* More formally, returns the lowest index {@code i} such that
586	>	* <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>,
587	>	* or -1 if there is no such index.
588		*
589		* @param o element to search for
590	<	* @return the index in this list of the first occurrence of the
591	<	*         specified element, or -1 if the list does not contain this
387	<	*         element
590	>	* @return the index of the first occurrence of the specified element in
591	>	*         this list, or -1 if this list does not contain the element
592		*/
593		public int indexOf(Object o) {
594		int index = 0;
595	<	if (o==null) {
596	<	for (Entry e = header.next; e != header; e = e.next) {
597	<	if (e.element==null)
595	>	if (o == null) {
596	>	for (Node<E> x = first; x != null; x = x.next) {
597	>	if (x.item == null)
598		return index;
599		index++;
600		}
601		} else {
602	<	for (Entry e = header.next; e != header; e = e.next) {
603	<	if (o.equals(e.element))
602	>	for (Node<E> x = first; x != null; x = x.next) {
603	>	if (o.equals(x.item))
604		return index;
605		index++;
606		}
#	Line 405 | Line 609 | public class LinkedList<E>
609		}
610
611		/**
612	<	* Returns the index in this list of the last occurrence of the
613	<	* specified element, or -1 if the list does not contain this
614	<	* element.  More formally, returns the highest index i such that
615	<	* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>, or -1 if
616	<	* there is no such index.
612	>	* Returns the index of the last occurrence of the specified element
613	>	* in this list, or -1 if this list does not contain the element.
614	>	* More formally, returns the highest index {@code i} such that
615	>	* <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>,
616	>	* or -1 if there is no such index.
617		*
618		* @param o element to search for
619	<	* @return the index in this list of the last occurrence of the
620	<	*         specified element, or -1 if the list does not contain this
417	<	*         element
619	>	* @return the index of the last occurrence of the specified element in
620	>	*         this list, or -1 if this list does not contain the element
621		*/
622		public int lastIndexOf(Object o) {
623		int index = size;
624	<	if (o==null) {
625	<	for (Entry e = header.previous; e != header; e = e.previous) {
624	>	if (o == null) {
625	>	for (Node<E> x = last; x != null; x = x.prev) {
626		index--;
627	<	if (e.element==null)
627	>	if (x.item == null)
628		return index;
629		}
630		} else {
631	<	for (Entry e = header.previous; e != header; e = e.previous) {
631	>	for (Node<E> x = last; x != null; x = x.prev) {
632		index--;
633	<	if (o.equals(e.element))
633	>	if (o.equals(x.item))
634		return index;
635		}
636		}
#	Line 438 | Line 641 | public class LinkedList<E>
641
642		/**
643		* Retrieves, but does not remove, the head (first element) of this list.
644	<	* @return the head of this list, or <tt>null</tt> if this list is empty
644	>	*
645	>	* @return the head of this list, or {@code null} if this list is empty
646		* @since 1.5
647		*/
648		public E peek() {
649	<	if (size==0)
650	<	return null;
447	<	return getFirst();
649	>	final Node<E> f = first;
650	>	return (f == null) ? null : f.item;
651		}
652
653		/**
654		* Retrieves, but does not remove, the head (first element) of this list.
655	+	*
656		* @return the head of this list
657		* @throws NoSuchElementException if this list is empty
658		* @since 1.5
#	Line 458 | Line 662 | public class LinkedList<E>
662		}
663
664		/**
665	<	* Retrieves and removes the head (first element) of this list
666	<	* @return the head of this list, or <tt>null</tt> if this list is empty
665	>	* Retrieves and removes the head (first element) of this list.
666	>	*
667	>	* @return the head of this list, or {@code null} if this list is empty
668		* @since 1.5
669		*/
670		public E poll() {
671	<	if (size==0)
672	<	return null;
468	<	return removeFirst();
671	>	final Node<E> f = first;
672	>	return (f == null) ? null : unlinkFirst(f);
673		}
674
675		/**
#	Line 483 | Line 687 | public class LinkedList<E>
687		* Adds the specified element as the tail (last element) of this list.
688		*
689		* @param e the element to add
690	<	* @return <tt>true</tt> (as per the spec for {@link Queue#offer})
690	>	* @return {@code true} (as specified by {@link Queue#offer})
691		* @since 1.5
692		*/
693		public boolean offer(E e) {
#	Line 495 | Line 699 | public class LinkedList<E>
699		* Inserts the specified element at the front of this list.
700		*
701		* @param e the element to insert
702	<	* @return <tt>true</tt> (as per the spec for {@link Deque#offerFirst})
702	>	* @return {@code true} (as specified by {@link Deque#offerFirst})
703		* @since 1.6
704		*/
705		public boolean offerFirst(E e) {
#	Line 507 | Line 711 | public class LinkedList<E>
711		* Inserts the specified element at the end of this list.
712		*
713		* @param e the element to insert
714	<	* @return <tt>true</tt> (as per the spec for {@link Deque#offerLast})
714	>	* @return {@code true} (as specified by {@link Deque#offerLast})
715		* @since 1.6
716		*/
717		public boolean offerLast(E e) {
#	Line 517 | Line 721 | public class LinkedList<E>
721
722		/**
723		* Retrieves, but does not remove, the first element of this list,
724	<	* or returns <tt>null</tt> if this list is empty.
724	>	* or returns {@code null} if this list is empty.
725		*
726	<	* @return the first element of this list, or <tt>null</tt>
726	>	* @return the first element of this list, or {@code null}
727		*         if this list is empty
728		* @since 1.6
729		*/
730		public E peekFirst() {
731	<	if (size==0)
732	<	return null;
733	<	return getFirst();
530	<	}
731	>	final Node<E> f = first;
732	>	return (f == null) ? null : f.item;
733	>	}
734
735		/**
736		* Retrieves, but does not remove, the last element of this list,
737	<	* or returns <tt>null</tt> if this list is empty.
737	>	* or returns {@code null} if this list is empty.
738		*
739	<	* @return the last element of this list, or <tt>null</tt>
739	>	* @return the last element of this list, or {@code null}
740		*         if this list is empty
741		* @since 1.6
742		*/
743		public E peekLast() {
744	<	if (size==0)
745	<	return null;
543	<	return getLast();
744	>	final Node<E> l = last;
745	>	return (l == null) ? null : l.item;
746		}
747
748		/**
749	<	* Retrieves and removes the first element of this list, or
750	<	* <tt>null</tt> if this list is empty.
749	>	* Retrieves and removes the first element of this list,
750	>	* or returns {@code null} if this list is empty.
751		*
752	<	* @return the first element of this list, or <tt>null</tt> if
752	>	* @return the first element of this list, or {@code null} if
753		*     this list is empty
754		* @since 1.6
755		*/
756		public E pollFirst() {
757	<	if (size==0)
758	<	return null;
557	<	return removeFirst();
757	>	final Node<E> f = first;
758	>	return (f == null) ? null : unlinkFirst(f);
759		}
760
761		/**
762	<	* Retrieves and removes the last element of this list, or
763	<	* <tt>null</tt> if this list is empty.
762	>	* Retrieves and removes the last element of this list,
763	>	* or returns {@code null} if this list is empty.
764		*
765	<	* @return the last element of this list, or <tt>null</tt> if
765	>	* @return the last element of this list, or {@code null} if
766		*     this list is empty
767		* @since 1.6
768		*/
769		public E pollLast() {
770	<	if (size==0)
771	<	return null;
571	<	return removeLast();
770	>	final Node<E> l = last;
771	>	return (l == null) ? null : unlinkLast(l);
772		}
773
774		/**
#	Line 605 | Line 805 | public class LinkedList<E>
805		* does not contain the element, it is unchanged.
806		*
807		* @param o element to be removed from this list, if present
808	<	* @return <tt>true</tt> if the list contained the specified element
808	>	* @return {@code true} if the list contained the specified element
809		* @since 1.6
810		*/
811		public boolean removeFirstOccurrence(Object o) {
#	Line 618 | Line 818 | public class LinkedList<E>
818		* does not contain the element, it is unchanged.
819		*
820		* @param o element to be removed from this list, if present
821	<	* @return <tt>true</tt> if the list contained the specified element
821	>	* @return {@code true} if the list contained the specified element
822		* @since 1.6
823		*/
824		public boolean removeLastOccurrence(Object o) {
825	<	if (o==null) {
826	<	for (Entry e = header.previous; e != header; e = e.previous) {
827	<	if (e.element==null) {
828	<	remove(e);
825	>	if (o == null) {
826	>	for (Node<E> x = last; x != null; x = x.prev) {
827	>	if (x.item == null) {
828	>	unlink(x);
829		return true;
830		}
831		}
832		} else {
833	<	for (Entry e = header.previous; e != header; e = e.previous) {
834	<	if (o.equals(e.element)) {
835	<	remove(e);
833	>	for (Node<E> x = last; x != null; x = x.prev) {
834	>	if (o.equals(x.item)) {
835	>	unlink(x);
836		return true;
837		}
838		}
#	Line 643 | Line 843 | public class LinkedList<E>
843		/**
844		* Returns a list-iterator of the elements in this list (in proper
845		* sequence), starting at the specified position in the list.
846	<	* Obeys the general contract of <tt>List.listIterator(int)</tt>.<p>
846	>	* Obeys the general contract of {@code List.listIterator(int)}.<p>
847		*
848		* The list-iterator is <i>fail-fast</i>: if the list is structurally
849		* modified at any time after the Iterator is created, in any way except
850	<	* through the list-iterator's own <tt>remove</tt> or <tt>add</tt>
850	>	* through the list-iterator's own {@code remove} or {@code add}
851		* methods, the list-iterator will throw a
852	<	* <tt>ConcurrentModificationException</tt>.  Thus, in the face of
852	>	* {@code ConcurrentModificationException}.  Thus, in the face of
853		* concurrent modification, the iterator fails quickly and cleanly, rather
854		* than risking arbitrary, non-deterministic behavior at an undetermined
855		* time in the future.
856		*
857		* @param index index of the first element to be returned from the
858	<	*              list-iterator (by a call to <tt>next</tt>)
858	>	*              list-iterator (by a call to {@code next})
859		* @return a ListIterator of the elements in this list (in proper
860		*         sequence), starting at the specified position in the list
861		* @throws IndexOutOfBoundsException {@inheritDoc}
862		* @see List#listIterator(int)
863		*/
864		public ListIterator<E> listIterator(int index) {
865	<	return new ListItr(index);
865	>	checkPositionIndex(index);
866	>	return new ListItr(index);
867		}
868
869		private class ListItr implements ListIterator<E> {
870	<	private Entry<E> lastReturned = header;
871	<	private Entry<E> next;
872	<	private int nextIndex;
873	<	private int expectedModCount = modCount;
874	<
875	<	ListItr(int index) {
876	<	if (index < 0 || index > size)
877	<	throw new IndexOutOfBoundsException("Index: "+index+
878	<	", Size: "+size);
879	<	if (index < (size >> 1)) {
880	<	next = header.next;
881	<	for (nextIndex=0; nextIndex<index; nextIndex++)
882	<	next = next.next;
883	<	} else {
683	<	next = header;
684	<	for (nextIndex=size; nextIndex>index; nextIndex--)
685	<	next = next.previous;
686	<	}
687	<	}
688	<
689	<	public boolean hasNext() {
690	<	return nextIndex != size;
691	<	}
692	<
693	<	public E next() {
694	<	checkForComodification();
695	<	if (nextIndex == size)
696	<	throw new NoSuchElementException();
697	<
698	<	lastReturned = next;
699	<	next = next.next;
700	<	nextIndex++;
701	<	return lastReturned.element;
702	<	}
703	<
704	<	public boolean hasPrevious() {
705	<	return nextIndex != 0;
706	<	}
707	<
708	<	public E previous() {
709	<	if (nextIndex == 0)
710	<	throw new NoSuchElementException();
711	<
712	<	lastReturned = next = next.previous;
713	<	nextIndex--;
714	<	checkForComodification();
715	<	return lastReturned.element;
716	<	}
717	<
718	<	public int nextIndex() {
719	<	return nextIndex;
720	<	}
721	<
722	<	public int previousIndex() {
723	<	return nextIndex-1;
724	<	}
870	>	private Node<E> lastReturned = null;
871	>	private Node<E> next;
872	>	private int nextIndex;
873	>	private int expectedModCount = modCount;
874	>
875	>	ListItr(int index) {
876	>	// assert isPositionIndex(index);
877	>	next = (index == size) ? null : node(index);
878	>	nextIndex = index;
879	>	}
880	>
881	>	public boolean hasNext() {
882	>	return nextIndex < size;
883	>	}
884
885	<	public void remove() {
885	>	public E next() {
886		checkForComodification();
887	<	Entry<E> lastNext = lastReturned.next;
888	<	try {
889	<	LinkedList.this.remove(lastReturned);
890	<	} catch (NoSuchElementException e) {
887	>	if (!hasNext())
888	>	throw new NoSuchElementException();
889	>
890	>	lastReturned = next;
891	>	next = next.next;
892	>	nextIndex++;
893	>	return lastReturned.item;
894	>	}
895	>
896	>	public boolean hasPrevious() {
897	>	return nextIndex > 0;
898	>	}
899	>
900	>	public E previous() {
901	>	checkForComodification();
902	>	if (!hasPrevious())
903	>	throw new NoSuchElementException();
904	>
905	>	lastReturned = next = (next == null) ? last : next.prev;
906	>	nextIndex--;
907	>	return lastReturned.item;
908	>	}
909	>
910	>	public int nextIndex() {
911	>	return nextIndex;
912	>	}
913	>
914	>	public int previousIndex() {
915	>	return nextIndex - 1;
916	>	}
917	>
918	>	public void remove() {
919	>	checkForComodification();
920	>	if (lastReturned == null)
921		throw new IllegalStateException();
922	<	}
923	<	if (next==lastReturned)
922	>
923	>	Node<E> lastNext = lastReturned.next;
924	>	unlink(lastReturned);
925	>	if (next == lastReturned)
926		next = lastNext;
927		else
928	<	nextIndex--;
929	<	lastReturned = header;
930	<	expectedModCount++;
931	<	}
932	<
933	<	public void set(E e) {
934	<	if (lastReturned == header)
935	<	throw new IllegalStateException();
936	<	checkForComodification();
937	<	lastReturned.element = e;
938	<	}
939	<
940	<	public void add(E e) {
941	<	checkForComodification();
942	<	lastReturned = header;
943	<	addBefore(e, next);
944	<	nextIndex++;
945	<	expectedModCount++;
946	<	}
947	<
948	<	final void checkForComodification() {
949	<	if (modCount != expectedModCount)
950	<	throw new ConcurrentModificationException();
951	<	}
952	<	}
953	<
954	<	private static class Entry<E> {
955	<	E element;
956	<	Entry<E> next;
957	<	Entry<E> previous;
958	<
959	<	Entry(E element, Entry<E> next, Entry<E> previous) {
960	<	this.element = element;
961	<	this.next = next;
962	<	this.previous = previous;
963	<	}
964	<	}
965	<
966	<	private Entry<E> addBefore(E e, Entry<E> entry) {
776	<	Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);
777	<	newEntry.previous.next = newEntry;
778	<	newEntry.next.previous = newEntry;
779	<	size++;
780	<	modCount++;
781	<	return newEntry;
782	<	}
783	<
784	<	private E remove(Entry<E> e) {
785	<	if (e == header)
786	<	throw new NoSuchElementException();
787	<
788	<	E result = e.element;
789	<	e.previous.next = e.next;
790	<	e.next.previous = e.previous;
791	<	e.next = e.previous = null;
792	<	e.element = null;
793	<	size--;
794	<	modCount++;
795	<	return result;
928	>	nextIndex--;
929	>	lastReturned = null;
930	>	expectedModCount++;
931	>	}
932	>
933	>	public void set(E e) {
934	>	if (lastReturned == null)
935	>	throw new IllegalStateException();
936	>	checkForComodification();
937	>	lastReturned.item = e;
938	>	}
939	>
940	>	public void add(E e) {
941	>	checkForComodification();
942	>	lastReturned = null;
943	>	if (next == null)
944	>	linkLast(e);
945	>	else
946	>	linkBefore(e, next);
947	>	nextIndex++;
948	>	expectedModCount++;
949	>	}
950	>
951	>	final void checkForComodification() {
952	>	if (modCount != expectedModCount)
953	>	throw new ConcurrentModificationException();
954	>	}
955	>	}
956	>
957	>	private static class Node<E> {
958	>	E item;
959	>	Node<E> next;
960	>	Node<E> prev;
961	>
962	>	Node(Node<E> prev, E element, Node<E> next) {
963	>	this.item = element;
964	>	this.next = next;
965	>	this.prev = prev;
966	>	}
967		}
968
969		/**
970	<	* Returns a shallow copy of this <tt>LinkedList</tt>. (The elements
970	>	* @since 1.6
971	>	*/
972	>	public Iterator<E> descendingIterator() {
973	>	return new DescendingIterator();
974	>	}
975	>
976	>	/**
977	>	* Adapter to provide descending iterators via ListItr.previous
978	>	*/
979	>	private class DescendingIterator implements Iterator<E> {
980	>	private final ListItr itr = new ListItr(size());
981	>	public boolean hasNext() {
982	>	return itr.hasPrevious();
983	>	}
984	>	public E next() {
985	>	return itr.previous();
986	>	}
987	>	public void remove() {
988	>	itr.remove();
989	>	}
990	>	}
991	>
992	>	@SuppressWarnings("unchecked")
993	>	private LinkedList<E> superClone() {
994	>	try {
995	>	return (LinkedList<E>) super.clone();
996	>	} catch (CloneNotSupportedException e) {
997	>	throw new InternalError();
998	>	}
999	>	}
1000	>
1001	>	/**
1002	>	* Returns a shallow copy of this {@code LinkedList}. (The elements
1003		* themselves are not cloned.)
1004		*
1005	<	* @return a shallow copy of this <tt>LinkedList</tt> instance
1005	>	* @return a shallow copy of this {@code LinkedList} instance
1006		*/
1007		public Object clone() {
1008	<	LinkedList<E> clone = null;
806	<	try {
807	<	clone = (LinkedList<E>) super.clone();
808	<	} catch (CloneNotSupportedException e) {
809	<	throw new InternalError();
810	<	}
1008	>	LinkedList<E> clone = superClone();
1009
1010		// Put clone into "virgin" state
1011	<	clone.header = new Entry<E>(null, null, null);
814	<	clone.header.next = clone.header.previous = clone.header;
1011	>	clone.first = clone.last = null;
1012		clone.size = 0;
1013		clone.modCount = 0;
1014
1015		// Initialize clone with our elements
1016	<	for (Entry<E> e = header.next; e != header; e = e.next)
1017	<	clone.add(e.element);
1016	>	for (Node<E> x = first; x != null; x = x.next)
1017	>	clone.add(x.item);
1018
1019		return clone;
1020		}
1021
1022		/**
1023		* Returns an array containing all of the elements in this list
1024	<	* in the correct order.
1024	>	* in proper sequence (from first to last element).
1025	>	*
1026	>	* <p>The returned array will be "safe" in that no references to it are
1027	>	* maintained by this list.  (In other words, this method must allocate
1028	>	* a new array).  The caller is thus free to modify the returned array.
1029	>	*
1030	>	* <p>This method acts as bridge between array-based and collection-based
1031	>	* APIs.
1032		*
1033		* @return an array containing all of the elements in this list
1034	<	*         in the correct order
1034	>	*         in proper sequence
1035		*/
1036		public Object[] toArray() {
1037	<	Object[] result = new Object[size];
1037	>	Object[] result = new Object[size];
1038		int i = 0;
1039	<	for (Entry<E> e = header.next; e != header; e = e.next)
1040	<	result[i++] = e.element;
1041	<	return result;
1039	>	for (Node<E> x = first; x != null; x = x.next)
1040	>	result[i++] = x.item;
1041	>	return result;
1042		}
1043
1044		/**
1045		* Returns an array containing all of the elements in this list in
1046	<	* the correct order; the runtime type of the returned array is that of
1047	<	* the specified array.  If the list fits in the specified array, it
1048	<	* is returned therein.  Otherwise, a new array is allocated with the
1049	<	* runtime type of the specified array and the size of this list.<p>
1050	<	*
1051	<	* If the list fits in the specified array with room to spare
1052	<	* (i.e., the array has more elements than the list),
1053	<	* the element in the array immediately following the end of the
1054	<	* collection is set to null.  This is useful in determining the length
1055	<	* of the list <i>only</i> if the caller knows that the list
1056	<	* does not contain any null elements.
1046	>	* proper sequence (from first to last element); the runtime type of
1047	>	* the returned array is that of the specified array.  If the list fits
1048	>	* in the specified array, it is returned therein.  Otherwise, a new
1049	>	* array is allocated with the runtime type of the specified array and
1050	>	* the size of this list.
1051	>	*
1052	>	* <p>If the list fits in the specified array with room to spare (i.e.,
1053	>	* the array has more elements than the list), the element in the array
1054	>	* immediately following the end of the list is set to {@code null}.
1055	>	* (This is useful in determining the length of the list <i>only</i> if
1056	>	* the caller knows that the list does not contain any null elements.)
1057	>	*
1058	>	* <p>Like the {@link #toArray()} method, this method acts as bridge between
1059	>	* array-based and collection-based APIs.  Further, this method allows
1060	>	* precise control over the runtime type of the output array, and may,
1061	>	* under certain circumstances, be used to save allocation costs.
1062	>	*
1063	>	* <p>Suppose {@code x} is a list known to contain only strings.
1064	>	* The following code can be used to dump the list into a newly
1065	>	* allocated array of {@code String}:
1066	>	*
1067	>	* <pre>
1068	>	*     String[] y = x.toArray(new String[0]);</pre>
1069	>	*
1070	>	* Note that {@code toArray(new Object[0])} is identical in function to
1071	>	* {@code toArray()}.
1072		*
1073		* @param a the array into which the elements of the list are to
1074		*          be stored, if it is big enough; otherwise, a new array of the
1075		*          same runtime type is allocated for this purpose.
1076		* @return an array containing the elements of the list
1077	<	* @throws ArrayStoreException if the runtime type of a is not a
1078	<	*         supertype of the runtime type of every element in this list
1077	>	* @throws ArrayStoreException if the runtime type of the specified array
1078	>	*         is not a supertype of the runtime type of every element in
1079	>	*         this list
1080		* @throws NullPointerException if the specified array is null
1081		*/
1082	+	@SuppressWarnings("unchecked")
1083		public <T> T[] toArray(T[] a) {
1084		if (a.length < size)
1085		a = (T[])java.lang.reflect.Array.newInstance(
1086		a.getClass().getComponentType(), size);
1087		int i = 0;
1088	<	Object[] result = a;
1089	<	for (Entry<E> e = header.next; e != header; e = e.next)
1090	<	result[i++] = e.element;
1088	>	Object[] result = a;
1089	>	for (Node<E> x = first; x != null; x = x.next)
1090	>	result[i++] = x.item;
1091
1092		if (a.length > size)
1093		a[size] = null;
#	Line 877 | Line 1098 | public class LinkedList<E>
1098		private static final long serialVersionUID = 876323262645176354L;
1099
1100		/**
1101	<	* Save the state of this <tt>LinkedList</tt> instance to a stream (that
1102	<	* is, serialize it).
1101	>	* Saves the state of this {@code LinkedList} instance to a stream
1102	>	* (that is, serializes it).
1103		*
1104		* @serialData The size of the list (the number of elements it
1105		*             contains) is emitted (int), followed by all of its
#	Line 886 | Line 1107 | public class LinkedList<E>
1107		*/
1108		private void writeObject(java.io.ObjectOutputStream s)
1109		throws java.io.IOException {
1110	<	// Write out any hidden serialization magic
1111	<	s.defaultWriteObject();
1110	>	// Write out any hidden serialization magic
1111	>	s.defaultWriteObject();
1112
1113		// Write out size
1114		s.writeInt(size);
1115
1116	<	// Write out all elements in the proper order.
1117	<	for (Entry e = header.next; e != header; e = e.next)
1118	<	s.writeObject(e.element);
1116	>	// Write out all elements in the proper order.
1117	>	for (Node<E> x = first; x != null; x = x.next)
1118	>	s.writeObject(x.item);
1119		}
1120
1121		/**
1122	<	* Reconstitute this <tt>LinkedList</tt> instance from a stream (that is
1123	<	* deserialize it).
1122	>	* Reconstitutes this {@code LinkedList} instance from a stream
1123	>	* (that is, deserializes it).
1124		*/
1125	+	@SuppressWarnings("unchecked")
1126		private void readObject(java.io.ObjectInputStream s)
1127		throws java.io.IOException, ClassNotFoundException {
1128	<	// Read in any hidden serialization magic
1129	<	s.defaultReadObject();
1128	>	// Read in any hidden serialization magic
1129	>	s.defaultReadObject();
1130
1131		// Read in size
1132		int size = s.readInt();
1133
1134	<	// Initialize header
1135	<	header = new Entry<E>(null, null, null);
1136	<	header.next = header.previous = header;
915	<
916	<	// Read in all elements in the proper order.
917	<	for (int i=0; i<size; i++)
918	<	addBefore((E)s.readObject(), header);
1134	>	// Read in all elements in the proper order.
1135	>	for (int i = 0; i < size; i++)
1136	>	linkLast((E)s.readObject());
1137		}
1138		}

Diff Legend

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