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.43 by jsr166, Tue Jan 10 21:32:09 2006 UTC vs.
Revision 1.53 by jsr166, Thu Dec 2 04:17:19 2010 UTC

#	Line 1 | Line 1
1		/*
2	<	* %W% %E%
2	>	* Copyright (c) 1997, 2006, Oracle and/or its affiliates. All rights reserved.
3	>	* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4		*
5	<	* Copyright 2006 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;
9	–	import java.util.*; // for javadoc (till 6280605 is fixed)
27
28		/**
29	<	* Linked list implementation of the <tt>List</tt> interface.  Implements all
30	<	* optional list operations, and permits all elements (including
31	<	* <tt>null</tt>).  In addition to implementing the <tt>List</tt> interface,
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, {@linkplain Queue queue}, or {@linkplain Deque
19	<	* double-ended queue}. <p>
20	<	*
21	<	* The class implements the <tt>Deque</tt> interface, providing
22	<	* first-in-first-out queue operations for <tt>add</tt>,
23	<	* <tt>poll</tt>, along with other stack and deque operations.<p>
29	>	* Doubly-linked list implementation of the {@code List} and {@code Deque}
30	>	* interfaces.  Implements all optional list operations, and permits all
31	>	* elements (including {@code null}).
32		*
33	<	* All of the operations perform as could be expected for a doubly-linked
33	>	* <p>All of the operations perform as could be expected for a doubly-linked
34		* list.  Operations that index into the list will traverse the list from
35	<	* the beginning or the end, whichever is closer to the specified index.<p>
35	>	* the beginning or the end, whichever is closer to the specified index.
36		*
37		* <p><strong>Note that this implementation is not synchronized.</strong>
38		* If multiple threads access a linked list concurrently, and at least
#	Line 41 | Line 49 | import java.util.*; // for javadoc (till
49		* unsynchronized access to the list:<pre>
50		*   List list = Collections.synchronizedList(new LinkedList(...));</pre>
51		*
52	<	* <p>The iterators returned by this class's <tt>iterator</tt> and
53	<	* <tt>listIterator</tt> methods are <i>fail-fast</i>: if the list is
52	>	* <p>The iterators returned by this class's {@code iterator} and
53	>	* {@code listIterator} methods are <i>fail-fast</i>: if the list is
54		* structurally modified at any time after the iterator is created, in
55	<	* any way except through the Iterator's own <tt>remove</tt> or
56	<	* <tt>add</tt> methods, the iterator will throw a {@link
55	>	* any way except through the Iterator's own {@code remove} or
56	>	* {@code add} methods, the iterator will throw a {@link
57		* ConcurrentModificationException}.  Thus, in the face of concurrent
58		* modification, the iterator fails quickly and cleanly, rather than
59		* risking arbitrary, non-deterministic behavior at an undetermined
#	Line 54 | Line 62 | import java.util.*; // for javadoc (till
62		* <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
63		* as it is, generally speaking, impossible to make any hard guarantees in the
64		* presence of unsynchronized concurrent modification.  Fail-fast iterators
65	<	* throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
65	>	* throw {@code ConcurrentModificationException} on a best-effort basis.
66		* Therefore, it would be wrong to write a program that depended on this
67		* exception for its correctness:   <i>the fail-fast behavior of iterators
68		* should be used only to detect bugs.</i>
69		*
70		* <p>This class is a member of the
71	<	* <a href="{@docRoot}/../guide/collections/index.html">
71	>	* <a href="{@docRoot}/../technotes/guides/collections/index.html">
72		* Java Collections Framework</a>.
73		*
74		* @author  Josh Bloch
75	<	* @version %I%, %G%
76	<	* @see     List
69	<	* @see     ArrayList
70	<	* @see     Vector
75	>	* @see     List
76	>	* @see     ArrayList
77		* @since 1.2
78		* @param <E> the type of elements held in this collection
79		*/
#	Line 76 | Line 82 | public class LinkedList<E>
82		extends AbstractSequentialList<E>
83		implements List<E>, Deque<E>, Cloneable, java.io.Serializable
84		{
85	<	private transient Entry<E> header = new Entry<E>(null, null, null);
86	<	private transient int size = 0;
85	>	transient int size = 0;
86	>
87	>	/**
88	>	* Pointer to first node.
89	>	* Invariant: (first == null && last == null) ||
90	>	*            (first.prev == null && first.item != null)
91	>	*/
92	>	transient Node<E> first;
93	>
94	>	/**
95	>	* Pointer to last node.
96	>	* Invariant: (first == null && last == null) ||
97	>	*            (last.next == null && last.item != null)
98	>	*/
99	>	transient Node<E> last;
100
101		/**
102		* Constructs an empty list.
103		*/
104		public LinkedList() {
86	–	header.next = header.previous = header;
105		}
106
107		/**
#	Line 95 | Line 113 | public class LinkedList<E>
113		* @throws NullPointerException if the specified collection is null
114		*/
115		public LinkedList(Collection<? extends E> c) {
116	<	this();
117	<	addAll(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		/**
#	Line 106 | Line 237 | public class LinkedList<E>
237		* @throws NoSuchElementException if this list is empty
238		*/
239		public E getFirst() {
240	<	if (size==0)
241	<	throw new NoSuchElementException();
242	<
243	<	return header.next.element;
240	>	final Node<E> f = first;
241	>	if (f == null)
242	>	throw new NoSuchElementException();
243	>	return f.item;
244		}
245
246		/**
#	Line 118 | Line 249 | public class LinkedList<E>
249		* @return the last element in this list
250		* @throws NoSuchElementException if this list is empty
251		*/
252	<	public E getLast()  {
253	<	if (size==0)
254	<	throw new NoSuchElementException();
255	<
256	<	return header.previous.element;
252	>	public E getLast() {
253	>	final Node<E> l = last;
254	>	if (l == null)
255	>	throw new NoSuchElementException();
256	>	return l.item;
257		}
258
259		/**
#	Line 132 | Line 263 | public class LinkedList<E>
263		* @throws NoSuchElementException if this list is empty
264		*/
265		public E removeFirst() {
266	<	return remove(header.next);
266	>	final Node<E> f = first;
267	>	if (f == null)
268	>	throw new NoSuchElementException();
269	>	return unlinkFirst(f);
270		}
271
272		/**
#	Line 142 | Line 276 | public class LinkedList<E>
276		* @throws NoSuchElementException if this list is empty
277		*/
278		public E removeLast() {
279	<	return remove(header.previous);
279	>	final Node<E> l = last;
280	>	if (l == null)
281	>	throw new NoSuchElementException();
282	>	return unlinkLast(l);
283		}
284
285		/**
#	Line 151 | Line 288 | public class LinkedList<E>
288		* @param e the element to add
289		*/
290		public void addFirst(E e) {
291	<	addBefore(e, header.next);
291	>	linkFirst(e);
292		}
293
294		/**
#	Line 162 | Line 299 | public class LinkedList<E>
299		* @param e the element to add
300		*/
301		public void addLast(E e) {
302	<	addBefore(e, header);
302	>	linkLast(e);
303		}
304
305		/**
306	<	* Returns <tt>true</tt> if this list contains the specified element.
307	<	* More formally, returns <tt>true</tt> if and only if this list contains
308	<	* at least one element <tt>e</tt> such that
306	>	* Returns {@code true} if this list contains the specified element.
307	>	* More formally, returns {@code true} if and only if this list contains
308	>	* at least one element {@code e} such that
309		* <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>.
310		*
311		* @param o element whose presence in this list is to be tested
312	<	* @return <tt>true</tt> if this list contains the specified element
312	>	* @return {@code true} if this list contains the specified element
313		*/
314		public boolean contains(Object o) {
315		return indexOf(o) != -1;
#	Line 184 | Line 321 | public class LinkedList<E>
321		* @return the number of elements in this list
322		*/
323		public int size() {
324	<	return size;
324	>	return size;
325		}
326
327		/**
#	Line 193 | Line 330 | public class LinkedList<E>
330		* <p>This method is equivalent to {@link #addLast}.
331		*
332		* @param e element to be appended to this list
333	<	* @return <tt>true</tt> (as specified by {@link Collection#add})
333	>	* @return {@code true} (as specified by {@link Collection#add})
334		*/
335		public boolean add(E e) {
336	<	addBefore(e, header);
336	>	linkLast(e);
337		return true;
338		}
339
#	Line 204 | Line 341 | public class LinkedList<E>
341		* Removes the first occurrence of the specified element from this list,
342		* if it is present.  If this list does not contain the element, it is
343		* unchanged.  More formally, removes the element with the lowest index
344	<	* <tt>i</tt> such that
344	>	* {@code i} such that
345		* <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>
346	<	* (if such an element exists).  Returns <tt>true</tt> if this list
346	>	* (if such an element exists).  Returns {@code true} if this list
347		* contained the specified element (or equivalently, if this list
348		* changed as a result of the call).
349		*
350		* @param o element to be removed from this list, if present
351	<	* @return <tt>true</tt> if this list contained the specified element
351	>	* @return {@code true} if this list contained the specified element
352		*/
353		public boolean remove(Object o) {
354	<	if (o==null) {
355	<	for (Entry<E> e = header.next; e != header; e = e.next) {
356	<	if (e.element==null) {
357	<	remove(e);
354	>	if (o == null) {
355	>	for (Node<E> x = first; x != null; x = x.next) {
356	>	if (x.item == null) {
357	>	unlink(x);
358		return true;
359		}
360		}
361		} else {
362	<	for (Entry<E> e = header.next; e != header; e = e.next) {
363	<	if (o.equals(e.element)) {
364	<	remove(e);
362	>	for (Node<E> x = first; x != null; x = x.next) {
363	>	if (o.equals(x.item)) {
364	>	unlink(x);
365		return true;
366		}
367		}
#	Line 241 | Line 378 | public class LinkedList<E>
378		* this list, and it's nonempty.)
379		*
380		* @param c collection containing elements to be added to this list
381	<	* @return <tt>true</tt> if this list changed as a result of the call
381	>	* @return {@code true} if this list changed as a result of the call
382		* @throws NullPointerException if the specified collection is null
383		*/
384		public boolean addAll(Collection<? extends E> c) {
#	Line 259 | Line 396 | public class LinkedList<E>
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 <tt>true</tt> if this list changed as a result of the call
399	>	* @return {@code true} if this list changed as a result of the call
400		* @throws IndexOutOfBoundsException {@inheritDoc}
401		* @throws NullPointerException if the specified collection is null
402		*/
403		public boolean addAll(int index, Collection<? extends E> c) {
404	<	if (index < 0 || index > size)
405	<	throw new IndexOutOfBoundsException("Index: "+index+
269	<	", Size: "+size);
404	>	checkPositionIndex(index);
405	>
406		Object[] a = c.toArray();
407		int numNew = a.length;
408	<	if (numNew==0)
408	>	if (numNew == 0)
409		return false;
274	–	modCount++;
410
411	<	Entry<E> successor = (index==size ? header : entry(index));
412	<	Entry<E> predecessor = successor.previous;
413	<	for (int i=0; i<numNew; i++) {
414	<	Entry<E> e = new Entry<E>((E)a[i], successor, predecessor);
415	<	predecessor.next = e;
416	<	predecessor = e;
411	>	Node<E> pred, succ;
412	>	if (index == size) {
413	>	succ = null;
414	>	pred = last;
415	>	} else {
416	>	succ = node(index);
417	>	pred = succ.prev;
418	>	}
419	>
420	>	for (Object o : a) {
421	>	@SuppressWarnings("unchecked") E e = (E) o;
422	>	Node<E> newNode = new Node<E>(pred, e, null);
423	>	if (pred == null)
424	>	first = newNode;
425	>	else
426	>	pred.next = newNode;
427	>	pred = newNode;
428	>	}
429	>
430	>	if (succ == null) {
431	>	last = pred;
432	>	} else {
433	>	pred.next = succ;
434	>	succ.prev = pred;
435		}
283	–	successor.previous = predecessor;
436
437		size += numNew;
438	+	modCount++;
439		return true;
440		}
441
442		/**
443		* Removes all of the elements from this list.
444	+	* The list will be empty after this call returns.
445		*/
446		public void clear() {
447	<	Entry<E> e = header.next;
448	<	while (e != header) {
449	<	Entry<E> next = e.next;
450	<	e.next = e.previous = null;
451	<	e.element = null;
452	<	e = next;
447	>	// Clearing all of the links between nodes is "unnecessary", but:
448	>	// - helps a generational GC if the discarded nodes inhabit
449	>	//   more than one generation
450	>	// - is sure to free memory even if there is a reachable Iterator
451	>	for (Node<E> x = first; x != null; ) {
452	>	Node<E> next = x.next;
453	>	x.item = null;
454	>	x.next = null;
455	>	x.prev = null;
456	>	x = next;
457		}
458	<	header.next = header.previous = header;
458	>	first = last = null;
459		size = 0;
460	<	modCount++;
460	>	modCount++;
461		}
462
463
#	Line 313 | Line 471 | public class LinkedList<E>
471		* @throws IndexOutOfBoundsException {@inheritDoc}
472		*/
473		public E get(int index) {
474	<	return entry(index).element;
474	>	checkElementIndex(index);
475	>	return node(index).item;
476		}
477
478		/**
#	Line 326 | Line 485 | public class LinkedList<E>
485		* @throws IndexOutOfBoundsException {@inheritDoc}
486		*/
487		public E set(int index, E element) {
488	<	Entry<E> e = entry(index);
489	<	E oldVal = e.element;
490	<	e.element = element;
488	>	checkElementIndex(index);
489	>	Node<E> x = node(index);
490	>	E oldVal = x.item;
491	>	x.item = element;
492		return oldVal;
493		}
494
#	Line 342 | Line 502 | public class LinkedList<E>
502		* @throws IndexOutOfBoundsException {@inheritDoc}
503		*/
504		public void add(int index, E element) {
505	<	addBefore(element, (index==size ? header : entry(index)));
505	>	checkPositionIndex(index);
506	>
507	>	if (index == size)
508	>	linkLast(element);
509	>	else
510	>	linkBefore(element, node(index));
511		}
512
513		/**
#	Line 355 | Line 520 | public class LinkedList<E>
520		* @throws IndexOutOfBoundsException {@inheritDoc}
521		*/
522		public E remove(int index) {
523	<	return remove(entry(index));
523	>	checkElementIndex(index);
524	>	return unlink(node(index));
525		}
526
527		/**
528	<	* Returns the indexed entry.
528	>	* Tells if the argument is the index of an existing element.
529		*/
530	<	private Entry<E> entry(int index) {
531	<	if (index < 0 || index >= size)
532	<	throw new IndexOutOfBoundsException("Index: "+index+
533	<	", Size: "+size);
534	<	Entry<E> e = header;
530	>	private boolean isElementIndex(int index) {
531	>	return index >= 0 && index < size;
532	>	}
533	>
534	>	/**
535	>	* Tells if the argument is the index of a valid position for an
536	>	* iterator or an add operation.
537	>	*/
538	>	private boolean isPositionIndex(int index) {
539	>	return index >= 0 && index <= size;
540	>	}
541	>
542	>	/**
543	>	* Constructs an IndexOutOfBoundsException detail message.
544	>	* Of the many possible refactorings of the error handling code,
545	>	* this "outlining" performs best with both server and client VMs.
546	>	*/
547	>	private String outOfBoundsMsg(int index) {
548	>	return "Index: "+index+", Size: "+size;
549	>	}
550	>
551	>	private void checkElementIndex(int index) {
552	>	if (!isElementIndex(index))
553	>	throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
554	>	}
555	>
556	>	private void checkPositionIndex(int index) {
557	>	if (!isPositionIndex(index))
558	>	throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
559	>	}
560	>
561	>	/**
562	>	* Returns the (non-null) Node at the specified element index.
563	>	*/
564	>	Node<E> node(int index) {
565	>	// assert isElementIndex(index);
566	>
567		if (index < (size >> 1)) {
568	<	for (int i = 0; i <= index; i++)
569	<	e = e.next;
568	>	Node<E> x = first;
569	>	for (int i = 0; i < index; i++)
570	>	x = x.next;
571	>	return x;
572		} else {
573	<	for (int i = size; i > index; i--)
574	<	e = e.previous;
573	>	Node<E> x = last;
574	>	for (int i = size - 1; i > index; i--)
575	>	x = x.prev;
576	>	return x;
577		}
376	–	return e;
578		}
579
379	–
580		// Search Operations
581
582		/**
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 <tt>i</tt> such that
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		*
#	Line 392 | Line 592 | public class LinkedList<E>
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 411 | Line 611 | public class LinkedList<E>
611		/**
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 <tt>i</tt> such that
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		*
#	Line 421 | Line 621 | public class LinkedList<E>
621		*/
622		public int lastIndexOf(Object o) {
623		int index = size;
624	<	if (o==null) {
625	<	for (Entry e = header.previous; e != header; e = e.previous) {
624	>	if (o == null) {
625	>	for (Node<E> x = last; x != null; x = x.prev) {
626		index--;
627	<	if (e.element==null)
627	>	if (x.item == null)
628		return index;
629		}
630		} else {
631	<	for (Entry e = header.previous; e != header; e = e.previous) {
631	>	for (Node<E> x = last; x != null; x = x.prev) {
632		index--;
633	<	if (o.equals(e.element))
633	>	if (o.equals(x.item))
634		return index;
635		}
636		}
#	Line 441 | Line 641 | public class LinkedList<E>
641
642		/**
643		* Retrieves, but does not remove, the head (first element) of this list.
644	<	* @return the head of this list, or <tt>null</tt> if this list is empty
644	>	*
645	>	* @return the head of this list, or {@code null} if this list is empty
646		* @since 1.5
647		*/
648		public E peek() {
649	<	if (size==0)
650	<	return null;
450	<	return getFirst();
649	>	final Node<E> f = first;
650	>	return (f == null) ? null : f.item;
651		}
652
653		/**
654		* Retrieves, but does not remove, the head (first element) of this list.
655	+	*
656		* @return the head of this list
657		* @throws NoSuchElementException if this list is empty
658		* @since 1.5
#	Line 461 | Line 662 | public class LinkedList<E>
662		}
663
664		/**
665	<	* Retrieves and removes the head (first element) of this list
666	<	* @return the head of this list, or <tt>null</tt> if this list is empty
665	>	* Retrieves and removes the head (first element) of this list.
666	>	*
667	>	* @return the head of this list, or {@code null} if this list is empty
668		* @since 1.5
669		*/
670		public E poll() {
671	<	if (size==0)
672	<	return null;
471	<	return removeFirst();
671	>	final Node<E> f = first;
672	>	return (f == null) ? null : unlinkFirst(f);
673		}
674
675		/**
#	Line 486 | Line 687 | public class LinkedList<E>
687		* Adds the specified element as the tail (last element) of this list.
688		*
689		* @param e the element to add
690	<	* @return <tt>true</tt> (as specified by {@link Queue#offer})
690	>	* @return {@code true} (as specified by {@link Queue#offer})
691		* @since 1.5
692		*/
693		public boolean offer(E e) {
#	Line 498 | Line 699 | public class LinkedList<E>
699		* Inserts the specified element at the front of this list.
700		*
701		* @param e the element to insert
702	<	* @return <tt>true</tt> (as specified by {@link Deque#offerFirst})
702	>	* @return {@code true} (as specified by {@link Deque#offerFirst})
703		* @since 1.6
704		*/
705		public boolean offerFirst(E e) {
#	Line 510 | Line 711 | public class LinkedList<E>
711		* Inserts the specified element at the end of this list.
712		*
713		* @param e the element to insert
714	<	* @return <tt>true</tt> (as specified by {@link Deque#offerLast})
714	>	* @return {@code true} (as specified by {@link Deque#offerLast})
715		* @since 1.6
716		*/
717		public boolean offerLast(E e) {
#	Line 520 | Line 721 | public class LinkedList<E>
721
722		/**
723		* Retrieves, but does not remove, the first element of this list,
724	<	* or returns <tt>null</tt> if this list is empty.
724	>	* or returns {@code null} if this list is empty.
725		*
726	<	* @return the first element of this list, or <tt>null</tt>
726	>	* @return the first element of this list, or {@code null}
727		*         if this list is empty
728		* @since 1.6
729		*/
730		public E peekFirst() {
731	<	if (size==0)
732	<	return null;
733	<	return getFirst();
533	<	}
731	>	final Node<E> f = first;
732	>	return (f == null) ? null : f.item;
733	>	}
734
735		/**
736		* Retrieves, but does not remove, the last element of this list,
737	<	* or returns <tt>null</tt> if this list is empty.
737	>	* or returns {@code null} if this list is empty.
738		*
739	<	* @return the last element of this list, or <tt>null</tt>
739	>	* @return the last element of this list, or {@code null}
740		*         if this list is empty
741		* @since 1.6
742		*/
743		public E peekLast() {
744	<	if (size==0)
745	<	return null;
546	<	return getLast();
744	>	final Node<E> l = last;
745	>	return (l == null) ? null : l.item;
746		}
747
748		/**
749		* Retrieves and removes the first element of this list,
750	<	* or returns <tt>null</tt> if this list is empty.
750	>	* or returns {@code null} if this list is empty.
751		*
752	<	* @return the first element of this list, or <tt>null</tt> if
752	>	* @return the first element of this list, or {@code null} if
753		*     this list is empty
754		* @since 1.6
755		*/
756		public E pollFirst() {
757	<	if (size==0)
758	<	return null;
560	<	return removeFirst();
757	>	final Node<E> f = first;
758	>	return (f == null) ? null : unlinkFirst(f);
759		}
760
761		/**
762		* Retrieves and removes the last element of this list,
763	<	* or returns <tt>null</tt> if this list is empty.
763	>	* or returns {@code null} if this list is empty.
764		*
765	<	* @return the last element of this list, or <tt>null</tt> if
765	>	* @return the last element of this list, or {@code null} if
766		*     this list is empty
767		* @since 1.6
768		*/
769		public E pollLast() {
770	<	if (size==0)
771	<	return null;
574	<	return removeLast();
770	>	final Node<E> l = last;
771	>	return (l == null) ? null : unlinkLast(l);
772		}
773
774		/**
#	Line 608 | Line 805 | public class LinkedList<E>
805		* does not contain the element, it is unchanged.
806		*
807		* @param o element to be removed from this list, if present
808	<	* @return <tt>true</tt> if the list contained the specified element
808	>	* @return {@code true} if the list contained the specified element
809		* @since 1.6
810		*/
811		public boolean removeFirstOccurrence(Object o) {
#	Line 621 | Line 818 | public class LinkedList<E>
818		* does not contain the element, it is unchanged.
819		*
820		* @param o element to be removed from this list, if present
821	<	* @return <tt>true</tt> if the list contained the specified element
821	>	* @return {@code true} if the list contained the specified element
822		* @since 1.6
823		*/
824		public boolean removeLastOccurrence(Object o) {
825	<	if (o==null) {
826	<	for (Entry<E> e = header.previous; e != header; e = e.previous) {
827	<	if (e.element==null) {
828	<	remove(e);
825	>	if (o == null) {
826	>	for (Node<E> x = last; x != null; x = x.prev) {
827	>	if (x.item == null) {
828	>	unlink(x);
829		return true;
830		}
831		}
832		} else {
833	<	for (Entry<E> e = header.previous; e != header; e = e.previous) {
834	<	if (o.equals(e.element)) {
835	<	remove(e);
833	>	for (Node<E> x = last; x != null; x = x.prev) {
834	>	if (o.equals(x.item)) {
835	>	unlink(x);
836		return true;
837		}
838		}
#	Line 646 | Line 843 | public class LinkedList<E>
843		/**
844		* Returns a list-iterator of the elements in this list (in proper
845		* sequence), starting at the specified position in the list.
846	<	* Obeys the general contract of <tt>List.listIterator(int)</tt>.<p>
846	>	* Obeys the general contract of {@code List.listIterator(int)}.<p>
847		*
848		* The list-iterator is <i>fail-fast</i>: if the list is structurally
849		* modified at any time after the Iterator is created, in any way except
850	<	* through the list-iterator's own <tt>remove</tt> or <tt>add</tt>
850	>	* through the list-iterator's own {@code remove} or {@code add}
851		* methods, the list-iterator will throw a
852	<	* <tt>ConcurrentModificationException</tt>.  Thus, in the face of
852	>	* {@code ConcurrentModificationException}.  Thus, in the face of
853		* concurrent modification, the iterator fails quickly and cleanly, rather
854		* than risking arbitrary, non-deterministic behavior at an undetermined
855		* time in the future.
856		*
857		* @param index index of the first element to be returned from the
858	<	*              list-iterator (by a call to <tt>next</tt>)
858	>	*              list-iterator (by a call to {@code next})
859		* @return a ListIterator of the elements in this list (in proper
860		*         sequence), starting at the specified position in the list
861		* @throws IndexOutOfBoundsException {@inheritDoc}
862		* @see List#listIterator(int)
863		*/
864		public ListIterator<E> listIterator(int index) {
865	<	return new ListItr(index);
865	>	checkPositionIndex(index);
866	>	return new ListItr(index);
867		}
868
869		private class ListItr implements ListIterator<E> {
870	<	private Entry<E> lastReturned = header;
871	<	private Entry<E> next;
872	<	private int nextIndex;
873	<	private int expectedModCount = modCount;
874	<
875	<	ListItr(int index) {
876	<	if (index < 0 || index > size)
877	<	throw new IndexOutOfBoundsException("Index: "+index+
878	<	", Size: "+size);
879	<	if (index < (size >> 1)) {
682	<	next = header.next;
683	<	for (nextIndex=0; nextIndex<index; nextIndex++)
684	<	next = next.next;
685	<	} else {
686	<	next = header;
687	<	for (nextIndex=size; nextIndex>index; nextIndex--)
688	<	next = next.previous;
689	<	}
690	<	}
691	<
692	<	public boolean hasNext() {
693	<	return nextIndex != size;
694	<	}
695	<
696	<	public E next() {
697	<	checkForComodification();
698	<	if (nextIndex == size)
699	<	throw new NoSuchElementException();
700	<
701	<	lastReturned = next;
702	<	next = next.next;
703	<	nextIndex++;
704	<	return lastReturned.element;
705	<	}
706	<
707	<	public boolean hasPrevious() {
708	<	return nextIndex != 0;
709	<	}
710	<
711	<	public E previous() {
712	<	if (nextIndex == 0)
713	<	throw new NoSuchElementException();
714	<
715	<	lastReturned = next = next.previous;
716	<	nextIndex--;
717	<	checkForComodification();
718	<	return lastReturned.element;
719	<	}
720	<
721	<	public int nextIndex() {
722	<	return nextIndex;
723	<	}
724	<
725	<	public int previousIndex() {
726	<	return nextIndex-1;
727	<	}
870	>	private Node<E> lastReturned = null;
871	>	private Node<E> next;
872	>	private int nextIndex;
873	>	private int expectedModCount = modCount;
874	>
875	>	ListItr(int index) {
876	>	// assert isPositionIndex(index);
877	>	next = (index == size) ? null : node(index);
878	>	nextIndex = index;
879	>	}
880
881	<	public void remove() {
881	>	public boolean hasNext() {
882	>	return nextIndex < size;
883	>	}
884	>
885	>	public E next() {
886		checkForComodification();
887	<	Entry<E> lastNext = lastReturned.next;
888	<	try {
889	<	LinkedList.this.remove(lastReturned);
890	<	} catch (NoSuchElementException e) {
887	>	if (!hasNext())
888	>	throw new NoSuchElementException();
889	>
890	>	lastReturned = next;
891	>	next = next.next;
892	>	nextIndex++;
893	>	return lastReturned.item;
894	>	}
895	>
896	>	public boolean hasPrevious() {
897	>	return nextIndex > 0;
898	>	}
899	>
900	>	public E previous() {
901	>	checkForComodification();
902	>	if (!hasPrevious())
903	>	throw new NoSuchElementException();
904	>
905	>	lastReturned = next = (next == null) ? last : next.prev;
906	>	nextIndex--;
907	>	return lastReturned.item;
908	>	}
909	>
910	>	public int nextIndex() {
911	>	return nextIndex;
912	>	}
913	>
914	>	public int previousIndex() {
915	>	return nextIndex - 1;
916	>	}
917	>
918	>	public void remove() {
919	>	checkForComodification();
920	>	if (lastReturned == null)
921		throw new IllegalStateException();
922	<	}
923	<	if (next==lastReturned)
922	>
923	>	Node<E> lastNext = lastReturned.next;
924	>	unlink(lastReturned);
925	>	if (next == lastReturned)
926		next = lastNext;
927		else
928	<	nextIndex--;
929	<	lastReturned = header;
930	<	expectedModCount++;
931	<	}
932	<
933	<	public void set(E e) {
934	<	if (lastReturned == header)
935	<	throw new IllegalStateException();
936	<	checkForComodification();
937	<	lastReturned.element = e;
938	<	}
939	<
940	<	public void add(E e) {
941	<	checkForComodification();
942	<	lastReturned = header;
943	<	addBefore(e, next);
944	<	nextIndex++;
945	<	expectedModCount++;
946	<	}
947	<
948	<	final void checkForComodification() {
949	<	if (modCount != expectedModCount)
950	<	throw new ConcurrentModificationException();
951	<	}
952	<	}
953	<
954	<	private static class Entry<E> {
955	<	E element;
956	<	Entry<E> next;
957	<	Entry<E> previous;
958	<
959	<	Entry(E element, Entry<E> next, Entry<E> previous) {
960	<	this.element = element;
961	<	this.next = next;
962	<	this.previous = previous;
963	<	}
964	<	}
965	<
966	<	private Entry<E> addBefore(E e, Entry<E> entry) {
779	<	Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);
780	<	newEntry.previous.next = newEntry;
781	<	newEntry.next.previous = newEntry;
782	<	size++;
783	<	modCount++;
784	<	return newEntry;
785	<	}
786	<
787	<	private E remove(Entry<E> e) {
788	<	if (e == header)
789	<	throw new NoSuchElementException();
790	<
791	<	E result = e.element;
792	<	e.previous.next = e.next;
793	<	e.next.previous = e.previous;
794	<	e.next = e.previous = null;
795	<	e.element = null;
796	<	size--;
797	<	modCount++;
798	<	return result;
928	>	nextIndex--;
929	>	lastReturned = null;
930	>	expectedModCount++;
931	>	}
932	>
933	>	public void set(E e) {
934	>	if (lastReturned == null)
935	>	throw new IllegalStateException();
936	>	checkForComodification();
937	>	lastReturned.item = e;
938	>	}
939	>
940	>	public void add(E e) {
941	>	checkForComodification();
942	>	lastReturned = null;
943	>	if (next == null)
944	>	linkLast(e);
945	>	else
946	>	linkBefore(e, next);
947	>	nextIndex++;
948	>	expectedModCount++;
949	>	}
950	>
951	>	final void checkForComodification() {
952	>	if (modCount != expectedModCount)
953	>	throw new ConcurrentModificationException();
954	>	}
955	>	}
956	>
957	>	private static class Node<E> {
958	>	E item;
959	>	Node<E> next;
960	>	Node<E> prev;
961	>
962	>	Node(Node<E> prev, E element, Node<E> next) {
963	>	this.item = element;
964	>	this.next = next;
965	>	this.prev = prev;
966	>	}
967		}
968
969		/**
#	Line 805 | Line 973 | public class LinkedList<E>
973		return new DescendingIterator();
974		}
975
976	<	/** Adapter to provide descending iterators via ListItr.previous */
977	<	private class DescendingIterator implements Iterator {
978	<	final ListItr itr = new ListItr(size());
979	<	public boolean hasNext() {
980	<	return itr.hasPrevious();
981	<	}
982	<	public E next() {
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() {
987	>	public void remove() {
988		itr.remove();
989		}
990		}
991
992	+	@SuppressWarnings("unchecked")
993	+	private LinkedList<E> superClone() {
994	+	try {
995	+	return (LinkedList<E>) super.clone();
996	+	} catch (CloneNotSupportedException e) {
997	+	throw new InternalError();
998	+	}
999	+	}
1000	+
1001		/**
1002	<	* Returns a shallow copy of this <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<E> clone = null;
830	<	try {
831	<	clone = (LinkedList<E>) super.clone();
832	<	} catch (CloneNotSupportedException e) {
833	<	throw new InternalError();
834	<	}
1008	>	LinkedList<E> clone = superClone();
1009
1010		// Put clone into "virgin" state
1011	<	clone.header = new Entry<E>(null, null, null);
838	<	clone.header.next = clone.header.previous = clone.header;
1011	>	clone.first = clone.last = null;
1012		clone.size = 0;
1013		clone.modCount = 0;
1014
1015		// Initialize clone with our elements
1016	<	for (Entry<E> e = header.next; e != header; e = e.next)
1017	<	clone.add(e.element);
1016	>	for (Node<E> x = first; x != null; x = x.next)
1017	>	clone.add(x.item);
1018
1019		return clone;
1020		}
#	Line 861 | Line 1034 | public class LinkedList<E>
1034		*         in proper sequence
1035		*/
1036		public Object[] toArray() {
1037	<	Object[] result = new Object[size];
1037	>	Object[] result = new Object[size];
1038		int i = 0;
1039	<	for (Entry<E> e = header.next; e != header; e = e.next)
1040	<	result[i++] = e.element;
1041	<	return result;
1039	>	for (Node<E> x = first; x != null; x = x.next)
1040	>	result[i++] = x.item;
1041	>	return result;
1042		}
1043
1044		/**
#	Line 878 | Line 1051 | public class LinkedList<E>
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 <tt>null</tt>.
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		*
#	Line 887 | Line 1060 | public class LinkedList<E>
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 <tt>x</tt> is a list known to contain only strings.
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 <tt>String</tt>:
1065	>	* allocated array of {@code String}:
1066		*
1067		* <pre>
1068		*     String[] y = x.toArray(new String[0]);</pre>
1069		*
1070	<	* Note that <tt>toArray(new Object[0])</tt> is identical in function to
1071	<	* <tt>toArray()</tt>.
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
#	Line 906 | Line 1079 | public class LinkedList<E>
1079		*         this list
1080		* @throws NullPointerException if the specified array is null
1081		*/
1082	+	@SuppressWarnings("unchecked")
1083		public <T> T[] toArray(T[] a) {
1084		if (a.length < size)
1085		a = (T[])java.lang.reflect.Array.newInstance(
1086		a.getClass().getComponentType(), size);
1087		int i = 0;
1088	<	Object[] result = a;
1089	<	for (Entry<E> e = header.next; e != header; e = e.next)
1090	<	result[i++] = e.element;
1088	>	Object[] result = a;
1089	>	for (Node<E> x = first; x != null; x = x.next)
1090	>	result[i++] = x.item;
1091
1092		if (a.length > size)
1093		a[size] = null;
#	Line 924 | Line 1098 | public class LinkedList<E>
1098		private static final long serialVersionUID = 876323262645176354L;
1099
1100		/**
1101	<	* Save the state of this <tt>LinkedList</tt> instance to a stream (that
1102	<	* is, serialize it).
1101	>	* Saves the state of this {@code LinkedList} instance to a stream
1102	>	* (that is, serializes it).
1103		*
1104		* @serialData The size of the list (the number of elements it
1105		*             contains) is emitted (int), followed by all of its
#	Line 933 | Line 1107 | public class LinkedList<E>
1107		*/
1108		private void writeObject(java.io.ObjectOutputStream s)
1109		throws java.io.IOException {
1110	<	// Write out any hidden serialization magic
1111	<	s.defaultWriteObject();
1110	>	// Write out any hidden serialization magic
1111	>	s.defaultWriteObject();
1112
1113		// Write out size
1114		s.writeInt(size);
1115
1116	<	// Write out all elements in the proper order.
1117	<	for (Entry e = header.next; e != header; e = e.next)
1118	<	s.writeObject(e.element);
1116	>	// Write out all elements in the proper order.
1117	>	for (Node<E> x = first; x != null; x = x.next)
1118	>	s.writeObject(x.item);
1119		}
1120
1121		/**
1122	<	* Reconstitute this <tt>LinkedList</tt> instance from a stream (that is
1123	<	* deserialize it).
1122	>	* Reconstitutes this {@code LinkedList} instance from a stream
1123	>	* (that is, deserializes it).
1124		*/
1125	+	@SuppressWarnings("unchecked")
1126		private void readObject(java.io.ObjectInputStream s)
1127		throws java.io.IOException, ClassNotFoundException {
1128	<	// Read in any hidden serialization magic
1129	<	s.defaultReadObject();
1128	>	// Read in any hidden serialization magic
1129	>	s.defaultReadObject();
1130
1131		// Read in size
1132		int size = s.readInt();
1133
1134	<	// Initialize header
1135	<	header = new Entry<E>(null, null, null);
1136	<	header.next = header.previous = header;
962	<
963	<	// Read in all elements in the proper order.
964	<	for (int i=0; i<size; i++)
965	<	addBefore((E)s.readObject(), header);
1134	>	// Read in all elements in the proper order.
1135	>	for (int i = 0; i < size; i++)
1136	>	linkLast((E)s.readObject());
1137		}
1138		}

Diff Legend

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