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

Diff Legend

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