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.2 by dl, Thu Aug 7 15:59:46 2003 UTC vs.
Revision 1.53 by jsr166, Thu Dec 2 04:17:19 2010 UTC

#	Line 1 | Line 1
1		/*
2	<	* @(#)LinkedList.java  1.43 01/12/03
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 2002 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	<	* <b>JSR166: Added Queue operations</b>.<p>
30	<	* Linked list implementation of the <tt>List</tt> interface.  Implements all
31	<	* optional list operations, and permits all elements (including
14	<	* <tt>null</tt>).  In addition to implementing the <tt>List</tt> interface,
15	<	* the <tt>LinkedList</tt> class provides uniformly named methods to
16	<	* <tt>get</tt>, <tt>remove</tt> and <tt>insert</tt> an element at the
17	<	* beginning and end of the list.  These operations allow linked lists to be
18	<	* used as a stack, queue, or double-ended queue (deque).<p>
19	<	*
20	<	* All of the stack/queue/deque operations could be easily recast in terms of
21	<	* the standard list operations.  They're included here primarily for
22	<	* convenience, though they may run slightly faster than the equivalent List
23	<	* 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 begining 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
51	<	* a structural modification.)  This is typically accomplished by
52	<	* synchronizing on some object that naturally encapsulates the list.  If no
53	<	* such object exists, the list should be "wrapped" using the
54	<	* Collections.synchronizedList method.  This is best done at creation time,
55	<	* to prevent accidental unsynchronized access to the list: <pre>
56	<	*     List list = Collections.synchronizedList(new LinkedList(...));
57	<	* </pre><p>
58	<	*
59	<	* The iterators returned by the this class's <tt>iterator</tt> and
60	<	* <tt>listIterator</tt> methods are <i>fail-fast</i>: if the list is
44	<	* structurally modified at any time after the iterator is created, in any way
45	<	* except through the Iterator's own <tt>remove</tt> or <tt>add</tt> methods,
46	<	* the iterator will throw a <tt>ConcurrentModificationException</tt>.  Thus,
47	<	* in the face of concurrent modification, the iterator fails quickly and
48	<	* cleanly, rather than risking arbitrary, non-deterministic behavior at an
49	<	* undetermined time in the future.
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 {@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 {@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
60	>	* time in the future.
61		*
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}/../technotes/guides/collections/index.html">
72	+	* Java Collections Framework</a>.
73	+	*
74		* @author  Josh Bloch
75	<	* @version 1.43, 12/03/01
76	<	* @see     java.util.List
62	<	* @see     java.util.ArrayList
63	<	* @see     java.util.Vector
64	<	* @see     java.util.Collections#synchronizedList(java.util.List)
75	>	* @see     List
76	>	* @see     ArrayList
77		* @since 1.2
78	+	* @param <E> the type of elements held in this collection
79		*/
80
81	<	public class LinkedList extends AbstractSequentialList
82	<	implements List, Queue, Cloneable, java.io.Serializable
81	>	public class LinkedList<E>
82	>	extends AbstractSequentialList<E>
83	>	implements List<E>, Deque<E>, Cloneable, java.io.Serializable
84		{
85	<	private transient Entry header = new Entry(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() {
78	–	header.next = header.previous = header;
105		}
106
107		/**
#	Line 83 | Line 109 | public class LinkedList extends Abstract
109		* collection, in the order they are returned by the collection's
110		* iterator.
111		*
112	<	* @param  c the collection whose elements are to be placed into this list.
113	<	* @throws NullPointerException if the specified collection is null.
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 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.
235		*
236	<	* @return the first element in this list.
237	<	* @throws    NoSuchElementException if this list is empty.
236	>	* @return the first element in this list
237	>	* @throws NoSuchElementException if this list is empty
238		*/
239	<	public Object getFirst() {
240	<	if (size==0)
239	>	public E getFirst() {
240	>	final Node<E> f = first;
241	>	if (f == null)
242		throw new NoSuchElementException();
243	<
104	<	return header.next.element;
243	>	return f.item;
244		}
245
246		/**
247		* Returns the last element in this list.
248		*
249	<	* @return the last element in this list.
250	<	* @throws    NoSuchElementException if this list is empty.
249	>	* @return the last element in this list
250	>	* @throws NoSuchElementException if this list is empty
251		*/
252	<	public Object getLast()  {
253	<	if (size==0)
252	>	public E getLast() {
253	>	final Node<E> l = last;
254	>	if (l == null)
255		throw new NoSuchElementException();
256	<
117	<	return header.previous.element;
256	>	return l.item;
257		}
258
259		/**
260		* Removes and returns the first element from this list.
261		*
262	<	* @return the first element from this list.
263	<	* @throws    NoSuchElementException if this list is empty.
262	>	* @return the first element from this list
263	>	* @throws NoSuchElementException if this list is empty
264		*/
265	<	public Object removeFirst() {
266	<	Object first = header.next.element;
267	<	remove(header.next);
268	<	return first;
265	>	public E removeFirst() {
266	>	final Node<E> f = first;
267	>	if (f == null)
268	>	throw new NoSuchElementException();
269	>	return unlinkFirst(f);
270		}
271
272		/**
273		* Removes and returns the last element from this list.
274		*
275	<	* @return the last element from this list.
276	<	* @throws    NoSuchElementException if this list is empty.
275	>	* @return the last element from this list
276	>	* @throws NoSuchElementException if this list is empty
277		*/
278	<	public Object removeLast() {
279	<	Object last = header.previous.element;
280	<	remove(header.previous);
281	<	return last;
278	>	public E removeLast() {
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.
287	<	*
288	<	* @param o the element to be inserted at the beginning of this list.
286	>	* Inserts the specified element at the beginning of this list.
287	>	*
288	>	* @param e the element to add
289		*/
290	<	public void addFirst(Object o) {
291	<	addBefore(o, header.next);
290	>	public void addFirst(E e) {
291	>	linkFirst(e);
292		}
293
294		/**
295	<	* Appends the given element to the end of this list.  (Identical in
296	<	* function to the <tt>add</tt> method; included only for consistency.)
297	<	*
298	<	* @param o the element to be inserted at the end of this list.
295	>	* Appends the specified element to the end of this list.
296	>	*
297	>	* <p>This method is equivalent to {@link #add}.
298	>	*
299	>	* @param e the element to add
300		*/
301	<	public void addLast(Object o) {
302	<	addBefore(o, header);
301	>	public void addLast(E e) {
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 <tt>(o==null ? e==null
309	<	* : o.equals(e))</tt>.
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.
311	>	* @param o element whose presence in this list is to be tested
312	>	* @return {@code true} if this list contains the specified element
313		*/
314		public boolean contains(Object o) {
315		return indexOf(o) != -1;
#	Line 176 | Line 318 | public class LinkedList extends Abstract
318		/**
319		* Returns the number of elements in this list.
320		*
321	<	* @return the number of elements in this list.
321	>	* @return the number of elements in this list
322		*/
323		public int size() {
324		return size;
#	Line 185 | Line 327 | public class LinkedList extends Abstract
327		/**
328		* Appends the specified element to the end of this list.
329		*
330	<	* @param o element to be appended to this list.
331	<	* @return <tt>true</tt> (as per the general contract of
332	<	* <tt>Collection.add</tt>).
330	>	* <p>This method is equivalent to {@link #addLast}.
331	>	*
332	>	* @param e element to be appended to this list
333	>	* @return {@code true} (as specified by {@link Collection#add})
334		*/
335	<	public boolean add(Object o) {
336	<	addBefore(o, header);
335	>	public boolean add(E e) {
336	>	linkLast(e);
337		return true;
338		}
339
340		/**
341	<	* Removes the first occurrence of the specified element in this list.  If
342	<	* the list does not contain the element, it is unchanged.  More formally,
343	<	* removes the element with the lowest index <tt>i</tt> such that
344	<	* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt> (if such an
345	<	* element exists).
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	>	* {@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 {@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 the list contained the specified element.
350	>	* @param o element to be removed from this list, if present
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 = 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 = 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 228 | Line 374 | public class LinkedList extends Abstract
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.
382	<	* @throws NullPointerException if the specified collection is null.
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 c) {
384	>	public boolean addAll(Collection<? extends E> c) {
385		return addAll(size, c);
386		}
387
#	Line 247 | Line 393 | public class LinkedList extends Abstract
393		* in the list in the order that they are returned by the
394		* specified collection's iterator.
395		*
396	<	* @param index index at which to insert 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.
400	<	* @throws IndexOutOfBoundsException if the specified index is out of
401	<	*            range (<tt>index &lt; 0 || index &gt; size()</tt>).
402	<	* @throws NullPointerException if the specified collection is null.
403	<	*/
404	<	public boolean addAll(int index, Collection c) {
405	<	int numNew = c.size();
406	<	if (numNew==0) {
407	<	if (index < 0 || index >= size)
408	<	throw new IndexOutOfBoundsException();
396	>	* @param index index at which to insert the first element
397	>	*              from the specified collection
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	>	checkPositionIndex(index);
405	>
406	>	Object[] a = c.toArray();
407	>	int numNew = a.length;
408	>	if (numNew == 0)
409	>	return false;
410	>
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	<	return false;
426	>	pred.next = newNode;
427	>	pred = newNode;
428		}
266	–	modCount++;
429
430	<	Entry successor = (index==size ? header : entry(index));
431	<	Entry predecessor = successor.previous;
432	<	Iterator it = c.iterator();
433	<	for (int i=0; i<numNew; i++) {
434	<	Entry e = new Entry(it.next(), successor, predecessor);
273	<	predecessor.next = e;
274	<	predecessor = e;
430	>	if (succ == null) {
431	>	last = pred;
432	>	} else {
433	>	pred.next = succ;
434	>	succ.prev = pred;
435		}
276	–	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	<	modCount++;
448	<	header.next = header.previous = header;
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	>	first = last = null;
459		size = 0;
460	+	modCount++;
461		}
462
463
#	Line 294 | Line 466 | public class LinkedList extends Abstract
466		/**
467		* Returns the element at the specified position in this list.
468		*
469	<	* @param index index of element to return.
470	<	* @return the element at the specified position in this list.
471	<	*
472	<	* @throws IndexOutOfBoundsException if the specified index is is out of
473	<	* range (<tt>index &lt; 0 || index &gt;= size()</tt>).
474	<	*/
475	<	public Object get(int index) {
304	<	return entry(index).element;
469	>	* @param index index of the element to return
470	>	* @return the element at the specified position in this list
471	>	* @throws IndexOutOfBoundsException {@inheritDoc}
472	>	*/
473	>	public E get(int index) {
474	>	checkElementIndex(index);
475	>	return node(index).item;
476		}
477
478		/**
479		* Replaces the element at the specified position in this list with the
480		* specified element.
481		*
482	<	* @param index index of element to replace.
483	<	* @param element element to be stored at the specified position.
484	<	* @return the element previously at the specified position.
485	<	* @throws IndexOutOfBoundsException if the specified index is out of
486	<	*            range (<tt>index &lt; 0 || index &gt;= size()</tt>).
487	<	*/
488	<	public Object set(int index, Object element) {
489	<	Entry e = entry(index);
490	<	Object oldVal = e.element;
491	<	e.element = element;
482	>	* @param index index of the element to replace
483	>	* @param element element to be stored at the specified position
484	>	* @return the element previously at the specified position
485	>	* @throws IndexOutOfBoundsException {@inheritDoc}
486	>	*/
487	>	public E set(int index, E 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 326 | Line 497 | public class LinkedList extends Abstract
497		* Shifts the element currently at that position (if any) and any
498		* subsequent elements to the right (adds one to their indices).
499		*
500	<	* @param index index at which the specified element is to be inserted.
501	<	* @param element element to be inserted.
502	<	*
503	<	* @throws IndexOutOfBoundsException if the specified index is out of
504	<	*            range (<tt>index &lt; 0 || index &gt; size()</tt>).
505	<	*/
506	<	public void add(int index, Object element) {
507	<	addBefore(element, (index==size ? header : entry(index)));
500	>	* @param index index at which the specified element is to be inserted
501	>	* @param element element to be inserted
502	>	* @throws IndexOutOfBoundsException {@inheritDoc}
503	>	*/
504	>	public void add(int index, E element) {
505	>	checkPositionIndex(index);
506	>
507	>	if (index == size)
508	>	linkLast(element);
509	>	else
510	>	linkBefore(element, node(index));
511		}
512
513		/**
#	Line 341 | Line 515 | public class LinkedList extends Abstract
515		* subsequent elements to the left (subtracts one from their indices).
516		* Returns the element that was removed from the list.
517		*
518	<	* @param index the index of the element to removed.
519	<	* @return the element previously at the specified position.
520	<	*
521	<	* @throws IndexOutOfBoundsException if the specified index is out of
522	<	*            range (<tt>index &lt; 0 || index &gt;= size()</tt>).
523	<	*/
524	<	public Object remove(int index) {
525	<	Entry e = entry(index);
526	<	remove(e);
527	<	return e.element;
518	>	* @param index the index of the element to be removed
519	>	* @return the element previously at the specified position
520	>	* @throws IndexOutOfBoundsException {@inheritDoc}
521	>	*/
522	>	public E remove(int index) {
523	>	checkElementIndex(index);
524	>	return unlink(node(index));
525	>	}
526	>
527	>	/**
528	>	* Tells if the argument is the index of an existing element.
529	>	*/
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	<	* Return the indexed entry.
563	<	*/
564	<	private Entry entry(int index) {
565	<	if (index < 0 || index >= size)
566	<	throw new IndexOutOfBoundsException("Index: "+index+
362	<	", Size: "+size);
363	<	Entry e = header;
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.
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.
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 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 extends Abstract
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.
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.
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 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		}
637		return -1;
638		}
639
640	+	// Queue operations.
641	+
642	+	/**
643	+	* Retrieves, but does not remove, the head (first element) of this list.
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	+	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
659	+	*/
660	+	public E element() {
661	+	return getFirst();
662	+	}
663	+
664	+	/**
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	+	final Node<E> f = first;
672	+	return (f == null) ? null : unlinkFirst(f);
673	+	}
674	+
675	+	/**
676	+	* Retrieves and removes the head (first element) of this list.
677	+	*
678	+	* @return the head of this list
679	+	* @throws NoSuchElementException if this list is empty
680	+	* @since 1.5
681	+	*/
682	+	public E remove() {
683	+	return removeFirst();
684	+	}
685	+
686	+	/**
687	+	* Adds the specified element as the tail (last element) of this list.
688	+	*
689	+	* @param e the element to add
690	+	* @return {@code true} (as specified by {@link Queue#offer})
691	+	* @since 1.5
692	+	*/
693	+	public boolean offer(E e) {
694	+	return add(e);
695	+	}
696	+
697	+	// Deque operations
698	+	/**
699	+	* Inserts the specified element at the front of this list.
700	+	*
701	+	* @param e the element to insert
702	+	* @return {@code true} (as specified by {@link Deque#offerFirst})
703	+	* @since 1.6
704	+	*/
705	+	public boolean offerFirst(E e) {
706	+	addFirst(e);
707	+	return true;
708	+	}
709	+
710	+	/**
711	+	* Inserts the specified element at the end of this list.
712	+	*
713	+	* @param e the element to insert
714	+	* @return {@code true} (as specified by {@link Deque#offerLast})
715	+	* @since 1.6
716	+	*/
717	+	public boolean offerLast(E e) {
718	+	addLast(e);
719	+	return true;
720	+	}
721	+
722	+	/**
723	+	* Retrieves, but does not remove, the first element of this list,
724	+	* or returns {@code null} if this list is empty.
725	+	*
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	+	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 {@code null} if this list is empty.
738	+	*
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	+	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,
750	+	* or returns {@code null} if this list is empty.
751	+	*
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	+	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,
763	+	* or returns {@code null} if this list is empty.
764	+	*
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	+	final Node<E> l = last;
771	+	return (l == null) ? null : unlinkLast(l);
772	+	}
773	+
774	+	/**
775	+	* Pushes an element onto the stack represented by this list.  In other
776	+	* words, inserts the element at the front of this list.
777	+	*
778	+	* <p>This method is equivalent to {@link #addFirst}.
779	+	*
780	+	* @param e the element to push
781	+	* @since 1.6
782	+	*/
783	+	public void push(E e) {
784	+	addFirst(e);
785	+	}
786	+
787	+	/**
788	+	* Pops an element from the stack represented by this list.  In other
789	+	* words, removes and returns the first element of this list.
790	+	*
791	+	* <p>This method is equivalent to {@link #removeFirst()}.
792	+	*
793	+	* @return the element at the front of this list (which is the top
794	+	*         of the stack represented by this list)
795	+	* @throws NoSuchElementException if this list is empty
796	+	* @since 1.6
797	+	*/
798	+	public E pop() {
799	+	return removeFirst();
800	+	}
801	+
802	+	/**
803	+	* Removes the first occurrence of the specified element in this
804	+	* list (when traversing the list from head to tail).  If the list
805	+	* does not contain the element, it is unchanged.
806	+	*
807	+	* @param o element to be removed from this list, if present
808	+	* @return {@code true} if the list contained the specified element
809	+	* @since 1.6
810	+	*/
811	+	public boolean removeFirstOccurrence(Object o) {
812	+	return remove(o);
813	+	}
814	+
815	+	/**
816	+	* Removes the last occurrence of the specified element in this
817	+	* list (when traversing the list from head to tail).  If the list
818	+	* does not contain the element, it is unchanged.
819	+	*
820	+	* @param o element to be removed from this list, if present
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 (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 (Node<E> x = last; x != null; x = x.prev) {
834	+	if (o.equals(x.item)) {
835	+	unlink(x);
836	+	return true;
837	+	}
838	+	}
839	+	}
840	+	return false;
841	+	}
842	+
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 first element to be returned from the
858	<	*              list-iterator (by a call to <tt>next</tt>).
857	>	* @param index index of the first element to be returned from the
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 if index is out of range
862	<	*            (<tt>index &lt; 0 || index &gt; size()</tt>).
457	<	* @see java.util.List#listIterator(int)
860	>	*         sequence), starting at the specified position in the list
861	>	* @throws IndexOutOfBoundsException {@inheritDoc}
862	>	* @see List#listIterator(int)
863		*/
864	<	public ListIterator listIterator(int index) {
864	>	public ListIterator<E> listIterator(int index) {
865	>	checkPositionIndex(index);
866		return new ListItr(index);
867		}
868
869	<	private class ListItr implements ListIterator {
870	<	private Entry lastReturned = header;
871	<	private Entry next;
869	>	private class ListItr implements ListIterator<E> {
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	<	if (index < 0 || index > size)
877	<	throw new IndexOutOfBoundsException("Index: "+index+
878	<	", Size: "+size);
473	<	if (index < (size >> 1)) {
474	<	next = header.next;
475	<	for (nextIndex=0; nextIndex<index; nextIndex++)
476	<	next = next.next;
477	<	} else {
478	<	next = header;
479	<	for (nextIndex=size; nextIndex>index; nextIndex--)
480	<	next = next.previous;
481	<	}
876	>	// assert isPositionIndex(index);
877	>	next = (index == size) ? null : node(index);
878	>	nextIndex = index;
879		}
880
881		public boolean hasNext() {
882	<	return nextIndex != size;
882	>	return nextIndex < size;
883		}
884
885	<	public Object next() {
885	>	public E next() {
886		checkForComodification();
887	<	if (nextIndex == size)
887	>	if (!hasNext())
888		throw new NoSuchElementException();
889
890		lastReturned = next;
891		next = next.next;
892		nextIndex++;
893	<	return lastReturned.element;
893	>	return lastReturned.item;
894		}
895
896		public boolean hasPrevious() {
897	<	return nextIndex != 0;
897	>	return nextIndex > 0;
898		}
899
900	<	public Object previous() {
901	<	if (nextIndex == 0)
900	>	public E previous() {
901	>	checkForComodification();
902	>	if (!hasPrevious())
903		throw new NoSuchElementException();
904
905	<	lastReturned = next = next.previous;
905	>	lastReturned = next = (next == null) ? last : next.prev;
906		nextIndex--;
907	<	checkForComodification();
510	<	return lastReturned.element;
907	>	return lastReturned.item;
908		}
909
910		public int nextIndex() {
#	Line 515 | Line 912 | public class LinkedList extends Abstract
912		}
913
914		public int previousIndex() {
915	<	return nextIndex-1;
915	>	return nextIndex - 1;
916		}
917
918		public void remove() {
919		checkForComodification();
920	<	try {
524	<	LinkedList.this.remove(lastReturned);
525	<	} catch (NoSuchElementException e) {
920	>	if (lastReturned == null)
921		throw new IllegalStateException();
922	<	}
923	<	if (next==lastReturned)
924	<	next = lastReturned.next;
922	>
923	>	Node<E> lastNext = lastReturned.next;
924	>	unlink(lastReturned);
925	>	if (next == lastReturned)
926	>	next = lastNext;
927		else
928		nextIndex--;
929	<	lastReturned = header;
929	>	lastReturned = null;
930		expectedModCount++;
931		}
932
933	<	public void set(Object o) {
934	<	if (lastReturned == header)
933	>	public void set(E e) {
934	>	if (lastReturned == null)
935		throw new IllegalStateException();
936		checkForComodification();
937	<	lastReturned.element = o;
937	>	lastReturned.item = e;
938		}
939
940	<	public void add(Object o) {
940	>	public void add(E e) {
941		checkForComodification();
942	<	lastReturned = header;
943	<	addBefore(o, next);
942	>	lastReturned = null;
943	>	if (next == null)
944	>	linkLast(e);
945	>	else
946	>	linkBefore(e, next);
947		nextIndex++;
948		expectedModCount++;
949		}
#	Line 554 | Line 954 | public class LinkedList extends Abstract
954		}
955		}
956
957	<	private static class Entry {
958	<	Object element;
959	<	Entry next;
960	<	Entry previous;
957	>	private static class Node<E> {
958	>	E item;
959	>	Node<E> next;
960	>	Node<E> prev;
961
962	<	Entry(Object element, Entry next, Entry previous) {
963	<	this.element = element;
962	>	Node(Node<E> prev, E element, Node<E> next) {
963	>	this.item = element;
964		this.next = next;
965	<	this.previous = previous;
965	>	this.prev = prev;
966		}
967		}
968
969	<	private Entry addBefore(Object o, Entry e) {
970	<	Entry newEntry = new Entry(o, e, e.previous);
971	<	newEntry.previous.next = newEntry;
972	<	newEntry.next.previous = newEntry;
973	<	size++;
574	<	modCount++;
575	<	return newEntry;
969	>	/**
970	>	* @since 1.6
971	>	*/
972	>	public Iterator<E> descendingIterator() {
973	>	return new DescendingIterator();
974		}
975
976	<	private void remove(Entry e) {
977	<	if (e == header)
978	<	throw new NoSuchElementException();
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	<	e.previous.next = e.next;
993	<	e.next.previous = e.previous;
994	<	size--;
995	<	modCount++;
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 <tt>LinkedList</tt>. (The elements
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 clone = null;
596	<	try {
597	<	clone = (LinkedList)super.clone();
598	<	} catch (CloneNotSupportedException e) {
599	<	throw new InternalError();
600	<	}
1008	>	LinkedList<E> clone = superClone();
1009
1010		// Put clone into "virgin" state
1011	<	clone.header = new Entry(null, null, null);
604	<	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 = 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];
1038		int i = 0;
1039	<	for (Entry e = header.next; e != header; e = e.next)
1040	<	result[i++] = e.element;
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.
1079	<	* @throws NullPointerException if the specified array is null.
1076	>	* @return an array containing the elements of the 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	<	public Object[] toArray(Object a[]) {
1082	>	@SuppressWarnings("unchecked")
1083	>	public <T> T[] toArray(T[] a) {
1084		if (a.length < size)
1085	<	a = (Object[])java.lang.reflect.Array.newInstance(
1085	>	a = (T[])java.lang.reflect.Array.newInstance(
1086		a.getClass().getComponentType(), size);
1087		int i = 0;
1088	<	for (Entry e = header.next; e != header; e = e.next)
1089	<	a[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 666 | Line 1098 | public class LinkedList extends Abstract
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
1106	<	* elements (each an Object) in the proper order.
1106	>	*             elements (each an Object) in the proper order.
1107		*/
1108	<	private synchronized void writeObject(java.io.ObjectOutputStream s)
1108	>	private void writeObject(java.io.ObjectOutputStream s)
1109		throws java.io.IOException {
1110		// Write out any hidden serialization magic
1111		s.defaultWriteObject();
#	Line 682 | Line 1114 | public class LinkedList extends Abstract
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);
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	<	private synchronized void readObject(java.io.ObjectInputStream s)
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();
#	Line 698 | Line 1131 | public class LinkedList extends Abstract
1131		// Read in size
1132		int size = s.readInt();
1133
701	–	// Initialize header
702	–	header = new Entry(null, null, null);
703	–	header.next = header.previous = header;
704	–
1134		// Read in all elements in the proper order.
1135	<	for (int i=0; i<size; i++)
1136	<	add(s.readObject());
1135	>	for (int i = 0; i < size; i++)
1136	>	linkLast((E)s.readObject());
1137		}
709	–
710	–	public Object peek() {
711	–	if (size==0)
712	–	return null;
713	–	return getFirst();
714	–	}
715	–
716	–	public Object element() {
717	–	return getFirst();
718	–	}
719	–
720	–	public Object poll() {
721	–	if (size==0)
722	–	return null;
723	–	return removeFirst();
724	–	}
725	–
726	–	public Object remove() {
727	–	return removeFirst();
728	–	}
729	–
730	–	public boolean offer(Object x) {
731	–	return add(x);
732	–	}
733	–
1138		}

Diff Legend

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