[ViewVC] Diff of: jsr166/jsr166/src/main/java/util/LinkedList.java

Comparing jsr166/src/main/java/util/LinkedList.java (file contents):
Revision 1.1 by tim, Wed May 14 21:30:44 2003 UTC vs.
Revision 1.49 by jsr166, Sun May 18 23:59:57 2008 UTC

#	Line 1 \| Line 1
1		/*
2	<	* @(#)LinkedList.java 1.43 01/12/03
2	>	* Copyright 1997-2006 Sun Microsystems, Inc. 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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
22	>	* CA 95054 USA or visit www.sun.com if you need additional information or
23	>	* have any questions.
24		*/
25
26		package java.util;
27
28		/**
11	–	* <b>JSR166: Added Queue operations</b>.<p>
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,
32		* the <tt>LinkedList</tt> class provides uniformly named methods to
33		* <tt>get</tt>, <tt>remove</tt> and <tt>insert</tt> an element at the
34		* beginning and end of the list. These operations allow linked lists to be
35	<	* used as a stack, queue, or double-ended queue (deque).<p>
35	>	* used as a stack, {@linkplain Queue queue}, or {@linkplain Deque
36	>	* double-ended queue}. <p>
37		*
38	<	* All of the stack/queue/deque operations could be easily recast in terms of
39	<	* the standard list operations. They're included here primarily for
40	<	* convenience, though they may run slightly faster than the equivalent List
23	<	* operations.<p>
38	>	* The class implements the <tt>Deque</tt> interface, providing
39	>	* first-in-first-out queue operations for <tt>add</tt>,
40	>	* <tt>poll</tt>, along with other stack and deque operations.<p>
41		*
42		* All of the operations perform as could be expected for a doubly-linked
43		* list. Operations that index into the list will traverse the list from
44	<	* the begining or the end, whichever is closer to the specified index.<p>
44	>	* the beginning or the end, whichever is closer to the specified index.<p>
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
37	<	* Collections.synchronizedList method. This is best done at creation time,
38	<	* to prevent accidental unsynchronized access to the list: <pre>
39	<	* List list = Collections.synchronizedList(new LinkedList(...));
40	<	* </pre><p>
46	>	* <p><strong>Note that this implementation is not synchronized.</strong>
47	>	* If multiple threads access a linked list concurrently, and at least
48	>	* one of the threads modifies the list structurally, it <i>must</i> be
49	>	* synchronized externally. (A structural modification is any operation
50	>	* that adds or deletes one or more elements; merely setting the value of
51	>	* an element is not a structural modification.) This is typically
52	>	* accomplished by synchronizing on some object that naturally
53	>	* encapsulates the list.
54		*
55	<	* The iterators returned by the this class's <tt>iterator</tt> and
55	>	* If no such object exists, the list should be "wrapped" using the
56	>	* {@link Collections#synchronizedList Collections.synchronizedList}
57	>	* method. This is best done at creation time, to prevent accidental
58	>	* unsynchronized access to the list:<pre>
59	>	* List list = Collections.synchronizedList(new LinkedList(...));</pre>
60	>	*
61	>	* <p>The iterators returned by this class's <tt>iterator</tt> and
62		* <tt>listIterator</tt> methods are <i>fail-fast</i>: if the list is
63	<	* structurally modified at any time after the iterator is created, in any way
64	<	* except through the Iterator's own <tt>remove</tt> or <tt>add</tt> methods,
65	<	* the iterator will throw a <tt>ConcurrentModificationException</tt>. Thus,
66	<	* in the face of concurrent modification, the iterator fails quickly and
67	<	* cleanly, rather than risking arbitrary, non-deterministic behavior at an
68	<	* undetermined time in the future.
63	>	* structurally modified at any time after the iterator is created, in
64	>	* any way except through the Iterator's own <tt>remove</tt> or
65	>	* <tt>add</tt> methods, the iterator will throw a {@link
66	>	* ConcurrentModificationException}. Thus, in the face of concurrent
67	>	* modification, the iterator fails quickly and cleanly, rather than
68	>	* risking arbitrary, non-deterministic behavior at an undetermined
69	>	* time in the future.
70		*
71		* <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
72		* as it is, generally speaking, impossible to make any hard guarantees in the
73		* presence of unsynchronized concurrent modification. Fail-fast iterators
74	<	* throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
74	>	* throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
75		* Therefore, it would be wrong to write a program that depended on this
76		* exception for its correctness: <i>the fail-fast behavior of iterators
77		* should be used only to detect bugs.</i>
78		*
79	+	* <p>This class is a member of the
80	+	* <a href="{@docRoot}/../technotes/guides/collections/index.html">
81	+	* Java Collections Framework</a>.
82	+	*
83		* @author Josh Bloch
84	<	* @version 1.43, 12/03/01
85	<	* @see java.util.List
86	<	* @see java.util.ArrayList
63	<	* @see java.util.Vector
64	<	* @see java.util.Collections#synchronizedList(java.util.List)
84	>	* @see List
85	>	* @see ArrayList
86	>	* @see Vector
87		* @since 1.2
88	+	* @param <E> the type of elements held in this collection
89		*/
90
91	<	public class LinkedList extends AbstractSequentialList
92	<	implements List, Queue, Cloneable, java.io.Serializable
91	>	public class LinkedList<E>
92	>	extends AbstractSequentialList<E>
93	>	implements List<E>, Deque<E>, Cloneable, java.io.Serializable
94		{
95	<	private transient Entry header = new Entry(null, null, null);
95	>	private transient Entry<E> header = new Entry<E>(null, null, null);
96		private transient int size = 0;
97
98		/**
#	Line 83 \| Line 107 \| public class LinkedList extends Abstract
107		* collection, in the order they are returned by the collection's
108		* iterator.
109		*
110	<	* @param c the collection whose elements are to be placed into this list.
111	<	* @throws NullPointerException if the specified collection is null.
110	>	* @param c the collection whose elements are to be placed into this list
111	>	* @throws NullPointerException if the specified collection is null
112		*/
113	<	public LinkedList(Collection c) {
114	<	this();
115	<	addAll(c);
116	<	}
113	>	public LinkedList(Collection<? extends E> c) {
114	>	this();
115	>	addAll(c);
116	>	}
117
118		/**
119		* Returns the first element in this list.
120		*
121	<	* @return the first element in this list.
122	<	* @throws NoSuchElementException if this list is empty.
121	>	* @return the first element in this list
122	>	* @throws NoSuchElementException if this list is empty
123		*/
124	<	public Object getFirst() {
124	>	public E getFirst() {
125		if (size==0)
126		throw new NoSuchElementException();
127
#	Line 107 \| Line 131 \| public class LinkedList extends Abstract
131		/**
132		* Returns the last element in this list.
133		*
134	<	* @return the last element in this list.
135	<	* @throws NoSuchElementException if this list is empty.
134	>	* @return the last element in this list
135	>	* @throws NoSuchElementException if this list is empty
136		*/
137	<	public Object getLast() {
137	>	public E getLast() {
138		if (size==0)
139		throw new NoSuchElementException();
140
#	Line 120 \| Line 144 \| public class LinkedList extends Abstract
144		/**
145		* Removes and returns the first element from this list.
146		*
147	<	* @return the first element from this list.
148	<	* @throws NoSuchElementException if this list is empty.
147	>	* @return the first element from this list
148	>	* @throws NoSuchElementException if this list is empty
149		*/
150	<	public Object removeFirst() {
151	<	Object first = header.next.element;
128	<	remove(header.next);
129	<	return first;
150	>	public E removeFirst() {
151	>	return remove(header.next);
152		}
153
154		/**
155		* Removes and returns the last element from this list.
156		*
157	<	* @return the last element from this list.
158	<	* @throws NoSuchElementException if this list is empty.
157	>	* @return the last element from this list
158	>	* @throws NoSuchElementException if this list is empty
159		*/
160	<	public Object removeLast() {
161	<	Object last = header.previous.element;
140	<	remove(header.previous);
141	<	return last;
160	>	public E removeLast() {
161	>	return remove(header.previous);
162		}
163
164		/**
165	<	* Inserts the given element at the beginning of this list.
166	<	*
167	<	* @param o the element to be inserted at the beginning of this list.
165	>	* Inserts the specified element at the beginning of this list.
166	>	*
167	>	* @param e the element to add
168		*/
169	<	public void addFirst(Object o) {
170	<	addBefore(o, header.next);
169	>	public void addFirst(E e) {
170	>	addBefore(e, header.next);
171		}
172
173		/**
174	<	* Appends the given element to the end of this list. (Identical in
175	<	* function to the <tt>add</tt> method; included only for consistency.)
176	<	*
177	<	* @param o the element to be inserted at the end of this list.
174	>	* Appends the specified element to the end of this list.
175	>	*
176	>	* <p>This method is equivalent to {@link #add}.
177	>	*
178	>	* @param e the element to add
179		*/
180	<	public void addLast(Object o) {
181	<	addBefore(o, header);
180	>	public void addLast(E e) {
181	>	addBefore(e, header);
182		}
183
184		/**
185		* Returns <tt>true</tt> if this list contains the specified element.
186		* More formally, returns <tt>true</tt> if and only if this list contains
187	<	* at least one element <tt>e</tt> such that <tt>(o==null ? e==null
188	<	* : o.equals(e))</tt>.
187	>	* at least one element <tt>e</tt> such that
188	>	* <tt>(o==null ? e==null : o.equals(e))</tt>.
189		*
190	<	* @param o element whose presence in this list is to be tested.
191	<	* @return <tt>true</tt> if this list contains the specified element.
190	>	* @param o element whose presence in this list is to be tested
191	>	* @return <tt>true</tt> if this list contains the specified element
192		*/
193		public boolean contains(Object o) {
194		return indexOf(o) != -1;
#	Line 176 \| Line 197 \| public class LinkedList extends Abstract
197		/**
198		* Returns the number of elements in this list.
199		*
200	<	* @return the number of elements in this list.
200	>	* @return the number of elements in this list
201		*/
202		public int size() {
203		return size;
#	Line 185 \| Line 206 \| public class LinkedList extends Abstract
206		/**
207		* Appends the specified element to the end of this list.
208		*
209	<	* @param o element to be appended to this list.
210	<	* @return <tt>true</tt> (as per the general contract of
211	<	* <tt>Collection.add</tt>).
209	>	* <p>This method is equivalent to {@link #addLast}.
210	>	*
211	>	* @param e element to be appended to this list
212	>	* @return <tt>true</tt> (as specified by {@link Collection#add})
213		*/
214	<	public boolean add(Object o) {
215	<	addBefore(o, header);
214	>	public boolean add(E e) {
215	>	addBefore(e, header);
216		return true;
217		}
218
219		/**
220	<	* Removes the first occurrence of the specified element in this list. If
221	<	* the list does not contain the element, it is unchanged. More formally,
222	<	* removes the element with the lowest index <tt>i</tt> such that
223	<	* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt> (if such an
224	<	* element exists).
220	>	* Removes the first occurrence of the specified element from this list,
221	>	* if it is present. If this list does not contain the element, it is
222	>	* unchanged. More formally, removes the element with the lowest index
223	>	* <tt>i</tt> such that
224	>	* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>
225	>	* (if such an element exists). Returns <tt>true</tt> if this list
226	>	* contained the specified element (or equivalently, if this list
227	>	* changed as a result of the call).
228		*
229	<	* @param o element to be removed from this list, if present.
230	<	* @return <tt>true</tt> if the list contained the specified element.
229	>	* @param o element to be removed from this list, if present
230	>	* @return <tt>true</tt> if this list contained the specified element
231		*/
232		public boolean remove(Object o) {
233		if (o==null) {
234	<	for (Entry e = header.next; e != header; e = e.next) {
234	>	for (Entry<E> e = header.next; e != header; e = e.next) {
235		if (e.element==null) {
236		remove(e);
237		return true;
238		}
239		}
240		} else {
241	<	for (Entry e = header.next; e != header; e = e.next) {
241	>	for (Entry<E> e = header.next; e != header; e = e.next) {
242		if (o.equals(e.element)) {
243		remove(e);
244		return true;
#	Line 228 \| Line 253 \| public class LinkedList extends Abstract
253		* this list, in the order that they are returned by the specified
254		* collection's iterator. The behavior of this operation is undefined if
255		* the specified collection is modified while the operation is in
256	<	* progress. (This implies that the behavior of this call is undefined if
257	<	* the specified Collection is this list, and this list is nonempty.)
256	>	* progress. (Note that this will occur if the specified collection is
257	>	* this list, and it's nonempty.)
258		*
259	<	* @param c the elements to be inserted into this list.
260	<	* @return <tt>true</tt> if this list changed as a result of the call.
261	<	* @throws NullPointerException if the specified collection is null.
259	>	* @param c collection containing elements to be added to this list
260	>	* @return <tt>true</tt> if this list changed as a result of the call
261	>	* @throws NullPointerException if the specified collection is null
262		*/
263	<	public boolean addAll(Collection c) {
263	>	public boolean addAll(Collection<? extends E> c) {
264		return addAll(size, c);
265		}
266
#	Line 247 \| Line 272 \| public class LinkedList extends Abstract
272		* in the list in the order that they are returned by the
273		* specified collection's iterator.
274		*
275	<	* @param index index at which to insert first element
276	<	* from the specified collection.
277	<	* @param c elements to be inserted into this list.
278	<	* @return <tt>true</tt> if this list changed as a result of the call.
279	<	* @throws IndexOutOfBoundsException if the specified index is out of
280	<	* range (<tt>index < 0 \|\| index > size()</tt>).
256	<	* @throws NullPointerException if the specified collection is null.
275	>	* @param index index at which to insert the first element
276	>	* from the specified collection
277	>	* @param c collection containing elements to be added to this list
278	>	* @return <tt>true</tt> if this list changed as a result of the call
279	>	* @throws IndexOutOfBoundsException {@inheritDoc}
280	>	* @throws NullPointerException if the specified collection is null
281		*/
282	<	public boolean addAll(int index, Collection c) {
283	<	int numNew = c.size();
282	>	public boolean addAll(int index, Collection<? extends E> c) {
283	>	if (index < 0 \|\| index > size)
284	>	throw new IndexOutOfBoundsException("Index: "+index+
285	>	", Size: "+size);
286	>	Object[] a = c.toArray();
287	>	int numNew = a.length;
288		if (numNew==0)
289		return false;
290		modCount++;
291
292	<	Entry successor = (index==size ? header : entry(index));
293	<	Entry predecessor = successor.previous;
266	<	Iterator it = c.iterator();
292	>	Entry<E> successor = (index==size ? header : entry(index));
293	>	Entry<E> predecessor = successor.previous;
294		for (int i=0; i<numNew; i++) {
295	<	Entry e = new Entry(it.next(), successor, predecessor);
295	>	Entry<E> e = new Entry<E>((E)a[i], successor, predecessor);
296		predecessor.next = e;
297		predecessor = e;
298		}
#	Line 279 \| Line 306 \| public class LinkedList extends Abstract
306		* Removes all of the elements from this list.
307		*/
308		public void clear() {
309	<	modCount++;
309	>	Entry<E> e = header.next;
310	>	while (e != header) {
311	>	Entry<E> next = e.next;
312	>	e.next = e.previous = null;
313	>	e.element = null;
314	>	e = next;
315	>	}
316		header.next = header.previous = header;
317		size = 0;
318	+	modCount++;
319		}
320
321
#	Line 290 \| Line 324 \| public class LinkedList extends Abstract
324		/**
325		* Returns the element at the specified position in this list.
326		*
327	<	* @param index index of element to return.
328	<	* @return the element at the specified position in this list.
329	<	*
296	<	* @throws IndexOutOfBoundsException if the specified index is is out of
297	<	* range (<tt>index < 0 \|\| index >= size()</tt>).
327	>	* @param index index of the element to return
328	>	* @return the element at the specified position in this list
329	>	* @throws IndexOutOfBoundsException {@inheritDoc}
330		*/
331	<	public Object get(int index) {
331	>	public E get(int index) {
332		return entry(index).element;
333		}
334
#	Line 304 \| Line 336 \| public class LinkedList extends Abstract
336		* Replaces the element at the specified position in this list with the
337		* specified element.
338		*
339	<	* @param index index of element to replace.
340	<	* @param element element to be stored at the specified position.
341	<	* @return the element previously at the specified position.
342	<	* @throws IndexOutOfBoundsException if the specified index is out of
343	<	* range (<tt>index < 0 \|\| index >= size()</tt>).
344	<	*/
345	<	public Object set(int index, Object element) {
346	<	Entry e = entry(index);
315	<	Object oldVal = e.element;
339	>	* @param index index of the element to replace
340	>	* @param element element to be stored at the specified position
341	>	* @return the element previously at the specified position
342	>	* @throws IndexOutOfBoundsException {@inheritDoc}
343	>	*/
344	>	public E set(int index, E element) {
345	>	Entry<E> e = entry(index);
346	>	E oldVal = e.element;
347		e.element = element;
348		return oldVal;
349		}
#	Line 322 \| Line 353 \| public class LinkedList extends Abstract
353		* Shifts the element currently at that position (if any) and any
354		* subsequent elements to the right (adds one to their indices).
355		*
356	<	* @param index index at which the specified element is to be inserted.
357	<	* @param element element to be inserted.
358	<	*
328	<	* @throws IndexOutOfBoundsException if the specified index is out of
329	<	* range (<tt>index < 0 \|\| index > size()</tt>).
356	>	* @param index index at which the specified element is to be inserted
357	>	* @param element element to be inserted
358	>	* @throws IndexOutOfBoundsException {@inheritDoc}
359		*/
360	<	public void add(int index, Object element) {
360	>	public void add(int index, E element) {
361		addBefore(element, (index==size ? header : entry(index)));
362		}
363
#	Line 337 \| Line 366 \| public class LinkedList extends Abstract
366		* subsequent elements to the left (subtracts one from their indices).
367		* Returns the element that was removed from the list.
368		*
369	<	* @param index the index of the element to removed.
370	<	* @return the element previously at the specified position.
371	<	*
343	<	* @throws IndexOutOfBoundsException if the specified index is out of
344	<	* range (<tt>index < 0 \|\| index >= size()</tt>).
369	>	* @param index the index of the element to be removed
370	>	* @return the element previously at the specified position
371	>	* @throws IndexOutOfBoundsException {@inheritDoc}
372		*/
373	<	public Object remove(int index) {
374	<	Entry e = entry(index);
348	<	remove(e);
349	<	return e.element;
373	>	public E remove(int index) {
374	>	return remove(entry(index));
375		}
376
377		/**
378	<	* Return the indexed entry.
378	>	* Returns the indexed entry.
379		*/
380	<	private Entry entry(int index) {
380	>	private Entry<E> entry(int index) {
381		if (index < 0 \|\| index >= size)
382		throw new IndexOutOfBoundsException("Index: "+index+
383		", Size: "+size);
384	<	Entry e = header;
384	>	Entry<E> e = header;
385		if (index < (size >> 1)) {
386		for (int i = 0; i <= index; i++)
387		e = e.next;
#	Line 371 \| Line 396 \| public class LinkedList extends Abstract
396		// Search Operations
397
398		/**
399	<	* Returns the index in this list of the first occurrence of the
400	<	* specified element, or -1 if the List does not contain this
401	<	* element. More formally, returns the lowest index i such that
402	<	* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>, or -1 if
403	<	* there is no such index.
404	<	*
405	<	* @param o element to search for.
406	<	* @return the index in this list of the first occurrence of the
407	<	* specified element, or -1 if the list does not contain this
383	<	* element.
399	>	* Returns the index of the first occurrence of the specified element
400	>	* in this list, or -1 if this list does not contain the element.
401	>	* More formally, returns the lowest index <tt>i</tt> such that
402	>	* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>,
403	>	* or -1 if there is no such index.
404	>	*
405	>	* @param o element to search for
406	>	* @return the index of the first occurrence of the specified element in
407	>	* this list, or -1 if this list does not contain the element
408		*/
409		public int indexOf(Object o) {
410		int index = 0;
#	Line 401 \| Line 425 \| public class LinkedList extends Abstract
425		}
426
427		/**
428	<	* Returns the index in this list of the last occurrence of the
429	<	* specified element, or -1 if the list does not contain this
430	<	* element. More formally, returns the highest index i such that
431	<	* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>, or -1 if
432	<	* there is no such index.
433	<	*
434	<	* @param o element to search for.
435	<	* @return the index in this list of the last occurrence of the
436	<	* specified element, or -1 if the list does not contain this
413	<	* element.
428	>	* Returns the index of the last occurrence of the specified element
429	>	* in this list, or -1 if this list does not contain the element.
430	>	* More formally, returns the highest index <tt>i</tt> such that
431	>	* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>,
432	>	* or -1 if there is no such index.
433	>	*
434	>	* @param o element to search for
435	>	* @return the index of the last occurrence of the specified element in
436	>	* this list, or -1 if this list does not contain the element
437		*/
438		public int lastIndexOf(Object o) {
439		int index = size;
#	Line 430 \| Line 453 \| public class LinkedList extends Abstract
453		return -1;
454		}
455
456	+	// Queue operations.
457	+
458	+	/**
459	+	* Retrieves, but does not remove, the head (first element) of this list.
460	+	* @return the head of this list, or <tt>null</tt> if this list is empty
461	+	* @since 1.5
462	+	*/
463	+	public E peek() {
464	+	if (size==0)
465	+	return null;
466	+	return getFirst();
467	+	}
468	+
469	+	/**
470	+	* Retrieves, but does not remove, the head (first element) of this list.
471	+	* @return the head of this list
472	+	* @throws NoSuchElementException if this list is empty
473	+	* @since 1.5
474	+	*/
475	+	public E element() {
476	+	return getFirst();
477	+	}
478	+
479	+	/**
480	+	* Retrieves and removes the head (first element) of this list
481	+	* @return the head of this list, or <tt>null</tt> if this list is empty
482	+	* @since 1.5
483	+	*/
484	+	public E poll() {
485	+	if (size==0)
486	+	return null;
487	+	return removeFirst();
488	+	}
489	+
490	+	/**
491	+	* Retrieves and removes the head (first element) of this list.
492	+	*
493	+	* @return the head of this list
494	+	* @throws NoSuchElementException if this list is empty
495	+	* @since 1.5
496	+	*/
497	+	public E remove() {
498	+	return removeFirst();
499	+	}
500	+
501	+	/**
502	+	* Adds the specified element as the tail (last element) of this list.
503	+	*
504	+	* @param e the element to add
505	+	* @return <tt>true</tt> (as specified by {@link Queue#offer})
506	+	* @since 1.5
507	+	*/
508	+	public boolean offer(E e) {
509	+	return add(e);
510	+	}
511	+
512	+	// Deque operations
513	+	/**
514	+	* Inserts the specified element at the front of this list.
515	+	*
516	+	* @param e the element to insert
517	+	* @return <tt>true</tt> (as specified by {@link Deque#offerFirst})
518	+	* @since 1.6
519	+	*/
520	+	public boolean offerFirst(E e) {
521	+	addFirst(e);
522	+	return true;
523	+	}
524	+
525	+	/**
526	+	* Inserts the specified element at the end of this list.
527	+	*
528	+	* @param e the element to insert
529	+	* @return <tt>true</tt> (as specified by {@link Deque#offerLast})
530	+	* @since 1.6
531	+	*/
532	+	public boolean offerLast(E e) {
533	+	addLast(e);
534	+	return true;
535	+	}
536	+
537	+	/**
538	+	* Retrieves, but does not remove, the first element of this list,
539	+	* or returns <tt>null</tt> if this list is empty.
540	+	*
541	+	* @return the first element of this list, or <tt>null</tt>
542	+	* if this list is empty
543	+	* @since 1.6
544	+	*/
545	+	public E peekFirst() {
546	+	if (size==0)
547	+	return null;
548	+	return getFirst();
549	+	}
550	+
551	+	/**
552	+	* Retrieves, but does not remove, the last element of this list,
553	+	* or returns <tt>null</tt> if this list is empty.
554	+	*
555	+	* @return the last element of this list, or <tt>null</tt>
556	+	* if this list is empty
557	+	* @since 1.6
558	+	*/
559	+	public E peekLast() {
560	+	if (size==0)
561	+	return null;
562	+	return getLast();
563	+	}
564	+
565	+	/**
566	+	* Retrieves and removes the first element of this list,
567	+	* or returns <tt>null</tt> if this list is empty.
568	+	*
569	+	* @return the first element of this list, or <tt>null</tt> if
570	+	* this list is empty
571	+	* @since 1.6
572	+	*/
573	+	public E pollFirst() {
574	+	if (size==0)
575	+	return null;
576	+	return removeFirst();
577	+	}
578	+
579	+	/**
580	+	* Retrieves and removes the last element of this list,
581	+	* or returns <tt>null</tt> if this list is empty.
582	+	*
583	+	* @return the last element of this list, or <tt>null</tt> if
584	+	* this list is empty
585	+	* @since 1.6
586	+	*/
587	+	public E pollLast() {
588	+	if (size==0)
589	+	return null;
590	+	return removeLast();
591	+	}
592	+
593	+	/**
594	+	* Pushes an element onto the stack represented by this list. In other
595	+	* words, inserts the element at the front of this list.
596	+	*
597	+	* <p>This method is equivalent to {@link #addFirst}.
598	+	*
599	+	* @param e the element to push
600	+	* @since 1.6
601	+	*/
602	+	public void push(E e) {
603	+	addFirst(e);
604	+	}
605	+
606	+	/**
607	+	* Pops an element from the stack represented by this list. In other
608	+	* words, removes and returns the first element of this list.
609	+	*
610	+	* <p>This method is equivalent to {@link #removeFirst()}.
611	+	*
612	+	* @return the element at the front of this list (which is the top
613	+	* of the stack represented by this list)
614	+	* @throws NoSuchElementException if this list is empty
615	+	* @since 1.6
616	+	*/
617	+	public E pop() {
618	+	return removeFirst();
619	+	}
620	+
621	+	/**
622	+	* Removes the first occurrence of the specified element in this
623	+	* list (when traversing the list from head to tail). If the list
624	+	* does not contain the element, it is unchanged.
625	+	*
626	+	* @param o element to be removed from this list, if present
627	+	* @return <tt>true</tt> if the list contained the specified element
628	+	* @since 1.6
629	+	*/
630	+	public boolean removeFirstOccurrence(Object o) {
631	+	return remove(o);
632	+	}
633	+
634	+	/**
635	+	* Removes the last occurrence of the specified element in this
636	+	* list (when traversing the list from head to tail). If the list
637	+	* does not contain the element, it is unchanged.
638	+	*
639	+	* @param o element to be removed from this list, if present
640	+	* @return <tt>true</tt> if the list contained the specified element
641	+	* @since 1.6
642	+	*/
643	+	public boolean removeLastOccurrence(Object o) {
644	+	if (o==null) {
645	+	for (Entry<E> e = header.previous; e != header; e = e.previous) {
646	+	if (e.element==null) {
647	+	remove(e);
648	+	return true;
649	+	}
650	+	}
651	+	} else {
652	+	for (Entry<E> e = header.previous; e != header; e = e.previous) {
653	+	if (o.equals(e.element)) {
654	+	remove(e);
655	+	return true;
656	+	}
657	+	}
658	+	}
659	+	return false;
660	+	}
661	+
662		/**
663		* Returns a list-iterator of the elements in this list (in proper
664		* sequence), starting at the specified position in the list.
#	Line 444 \| Line 673 \| public class LinkedList extends Abstract
673		* than risking arbitrary, non-deterministic behavior at an undetermined
674		* time in the future.
675		*
676	<	* @param index index of first element to be returned from the
677	<	* list-iterator (by a call to <tt>next</tt>).
676	>	* @param index index of the first element to be returned from the
677	>	* list-iterator (by a call to <tt>next</tt>)
678		* @return a ListIterator of the elements in this list (in proper
679	<	* sequence), starting at the specified position in the list.
680	<	* @throws IndexOutOfBoundsException if index is out of range
681	<	* (<tt>index < 0 \|\| index > size()</tt>).
453	<	* @see java.util.List#listIterator(int)
679	>	* sequence), starting at the specified position in the list
680	>	* @throws IndexOutOfBoundsException {@inheritDoc}
681	>	* @see List#listIterator(int)
682		*/
683	<	public ListIterator listIterator(int index) {
683	>	public ListIterator<E> listIterator(int index) {
684		return new ListItr(index);
685		}
686
687	<	private class ListItr implements ListIterator {
688	<	private Entry lastReturned = header;
689	<	private Entry next;
687	>	private class ListItr implements ListIterator<E> {
688	>	private Entry<E> lastReturned = header;
689	>	private Entry<E> next;
690		private int nextIndex;
691		private int expectedModCount = modCount;
692
#	Line 481 \| Line 709 \| public class LinkedList extends Abstract
709		return nextIndex != size;
710		}
711
712	<	public Object next() {
712	>	public E next() {
713		checkForComodification();
714		if (nextIndex == size)
715		throw new NoSuchElementException();
#	Line 496 \| Line 724 \| public class LinkedList extends Abstract
724		return nextIndex != 0;
725		}
726
727	<	public Object previous() {
727	>	public E previous() {
728		if (nextIndex == 0)
729		throw new NoSuchElementException();
730
#	Line 516 \| Line 744 \| public class LinkedList extends Abstract
744
745		public void remove() {
746		checkForComodification();
747	+	Entry<E> lastNext = lastReturned.next;
748		try {
749		LinkedList.this.remove(lastReturned);
750		} catch (NoSuchElementException e) {
751		throw new IllegalStateException();
752		}
753		if (next==lastReturned)
754	<	next = lastReturned.next;
754	>	next = lastNext;
755		else
756		nextIndex--;
757		lastReturned = header;
758		expectedModCount++;
759		}
760
761	<	public void set(Object o) {
761	>	public void set(E e) {
762		if (lastReturned == header)
763		throw new IllegalStateException();
764		checkForComodification();
765	<	lastReturned.element = o;
765	>	lastReturned.element = e;
766		}
767
768	<	public void add(Object o) {
768	>	public void add(E e) {
769		checkForComodification();
770		lastReturned = header;
771	<	addBefore(o, next);
771	>	addBefore(e, next);
772		nextIndex++;
773		expectedModCount++;
774		}
#	Line 550 \| Line 779 \| public class LinkedList extends Abstract
779		}
780		}
781
782	<	private static class Entry {
783	<	Object element;
784	<	Entry next;
785	<	Entry previous;
782	>	private static class Entry<E> {
783	>	E element;
784	>	Entry<E> next;
785	>	Entry<E> previous;
786
787	<	Entry(Object element, Entry next, Entry previous) {
787	>	Entry(E element, Entry<E> next, Entry<E> previous) {
788		this.element = element;
789		this.next = next;
790		this.previous = previous;
791		}
792		}
793
794	<	private Entry addBefore(Object o, Entry e) {
795	<	Entry newEntry = new Entry(o, e, e.previous);
794	>	private Entry<E> addBefore(E e, Entry<E> entry) {
795	>	Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);
796		newEntry.previous.next = newEntry;
797		newEntry.next.previous = newEntry;
798		size++;
#	Line 571 \| Line 800 \| public class LinkedList extends Abstract
800		return newEntry;
801		}
802
803	<	private void remove(Entry e) {
803	>	private E remove(Entry<E> e) {
804		if (e == header)
805		throw new NoSuchElementException();
806
807	+	E result = e.element;
808		e.previous.next = e.next;
809		e.next.previous = e.previous;
810	+	e.next = e.previous = null;
811	+	e.element = null;
812		size--;
813		modCount++;
814	+	return result;
815	+	}
816	+
817	+	/**
818	+	* @since 1.6
819	+	*/
820	+	public Iterator<E> descendingIterator() {
821	+	return new DescendingIterator();
822	+	}
823	+
824	+	/** Adapter to provide descending iterators via ListItr.previous */
825	+	private class DescendingIterator implements Iterator {
826	+	final ListItr itr = new ListItr(size());
827	+	public boolean hasNext() {
828	+	return itr.hasPrevious();
829	+	}
830	+	public E next() {
831	+	return itr.previous();
832	+	}
833	+	public void remove() {
834	+	itr.remove();
835	+	}
836		}
837
838		/**
839		* Returns a shallow copy of this <tt>LinkedList</tt>. (The elements
840		* themselves are not cloned.)
841		*
842	<	* @return a shallow copy of this <tt>LinkedList</tt> instance.
842	>	* @return a shallow copy of this <tt>LinkedList</tt> instance
843		*/
844		public Object clone() {
845	<	LinkedList clone = null;
846	<	try {
847	<	clone = (LinkedList)super.clone();
848	<	} catch (CloneNotSupportedException e) {
845	>	LinkedList<E> clone = null;
846	>	try {
847	>	clone = (LinkedList<E>) super.clone();
848	>	} catch (CloneNotSupportedException e) {
849		throw new InternalError();
850		}
851
852		// Put clone into "virgin" state
853	<	clone.header = new Entry(null, null, null);
853	>	clone.header = new Entry<E>(null, null, null);
854		clone.header.next = clone.header.previous = clone.header;
855		clone.size = 0;
856		clone.modCount = 0;
857
858		// Initialize clone with our elements
859	<	for (Entry e = header.next; e != header; e = e.next)
859	>	for (Entry<E> e = header.next; e != header; e = e.next)
860		clone.add(e.element);
861
862		return clone;
#	Line 610 \| Line 864 \| public class LinkedList extends Abstract
864
865		/**
866		* Returns an array containing all of the elements in this list
867	<	* in the correct order.
867	>	* in proper sequence (from first to last element).
868	>	*
869	>	* <p>The returned array will be "safe" in that no references to it are
870	>	* maintained by this list. (In other words, this method must allocate
871	>	* a new array). The caller is thus free to modify the returned array.
872	>	*
873	>	* <p>This method acts as bridge between array-based and collection-based
874	>	* APIs.
875		*
876		* @return an array containing all of the elements in this list
877	<	* in the correct order.
877	>	* in proper sequence
878		*/
879		public Object[] toArray() {
880		Object[] result = new Object[size];
881		int i = 0;
882	<	for (Entry e = header.next; e != header; e = e.next)
882	>	for (Entry<E> e = header.next; e != header; e = e.next)
883		result[i++] = e.element;
884		return result;
885		}
886
887		/**
888		* Returns an array containing all of the elements in this list in
889	<	* the correct order; the runtime type of the returned array is that of
890	<	* the specified array. If the list fits in the specified array, it
891	<	* is returned therein. Otherwise, a new array is allocated with the
892	<	* runtime type of the specified array and the size of this list.<p>
893	<	*
894	<	* If the list fits in the specified array with room to spare
895	<	* (i.e., the array has more elements than the list),
896	<	* the element in the array immediately following the end of the
897	<	* collection is set to null. This is useful in determining the length
898	<	* of the list <i>only</i> if the caller knows that the list
899	<	* does not contain any null elements.
889	>	* proper sequence (from first to last element); the runtime type of
890	>	* the returned array is that of the specified array. If the list fits
891	>	* in the specified array, it is returned therein. Otherwise, a new
892	>	* array is allocated with the runtime type of the specified array and
893	>	* the size of this list.
894	>	*
895	>	* <p>If the list fits in the specified array with room to spare (i.e.,
896	>	* the array has more elements than the list), the element in the array
897	>	* immediately following the end of the list is set to <tt>null</tt>.
898	>	* (This is useful in determining the length of the list <i>only</i> if
899	>	* the caller knows that the list does not contain any null elements.)
900	>	*
901	>	* <p>Like the {@link #toArray()} method, this method acts as bridge between
902	>	* array-based and collection-based APIs. Further, this method allows
903	>	* precise control over the runtime type of the output array, and may,
904	>	* under certain circumstances, be used to save allocation costs.
905	>	*
906	>	* <p>Suppose <tt>x</tt> is a list known to contain only strings.
907	>	* The following code can be used to dump the list into a newly
908	>	* allocated array of <tt>String</tt>:
909	>	*
910	>	* <pre>
911	>	* String[] y = x.toArray(new String[0]);</pre>
912	>	*
913	>	* Note that <tt>toArray(new Object[0])</tt> is identical in function to
914	>	* <tt>toArray()</tt>.
915		*
916		* @param a the array into which the elements of the list are to
917		* be stored, if it is big enough; otherwise, a new array of the
918		* same runtime type is allocated for this purpose.
919	<	* @return an array containing the elements of the list.
920	<	* @throws ArrayStoreException if the runtime type of a is not a
921	<	* supertype of the runtime type of every element in this list.
922	<	* @throws NullPointerException if the specified array is null.
919	>	* @return an array containing the elements of the list
920	>	* @throws ArrayStoreException if the runtime type of the specified array
921	>	* is not a supertype of the runtime type of every element in
922	>	* this list
923	>	* @throws NullPointerException if the specified array is null
924		*/
925	<	public Object[] toArray(Object a[]) {
925	>	public <T> T[] toArray(T[] a) {
926		if (a.length < size)
927	<	a = (Object[])java.lang.reflect.Array.newInstance(
927	>	a = (T[])java.lang.reflect.Array.newInstance(
928		a.getClass().getComponentType(), size);
929		int i = 0;
930	<	for (Entry e = header.next; e != header; e = e.next)
931	<	a[i++] = e.element;
930	>	Object[] result = a;
931	>	for (Entry<E> e = header.next; e != header; e = e.next)
932	>	result[i++] = e.element;
933
934		if (a.length > size)
935		a[size] = null;
#	Line 667 \| Line 945 \| public class LinkedList extends Abstract
945		*
946		* @serialData The size of the list (the number of elements it
947		* contains) is emitted (int), followed by all of its
948	<	* elements (each an Object) in the proper order.
948	>	* elements (each an Object) in the proper order.
949		*/
950	<	private synchronized void writeObject(java.io.ObjectOutputStream s)
950	>	private void writeObject(java.io.ObjectOutputStream s)
951		throws java.io.IOException {
952		// Write out any hidden serialization magic
953		s.defaultWriteObject();
#	Line 686 \| Line 964 \| public class LinkedList extends Abstract
964		* Reconstitute this <tt>LinkedList</tt> instance from a stream (that is
965		* deserialize it).
966		*/
967	<	private synchronized void readObject(java.io.ObjectInputStream s)
967	>	private void readObject(java.io.ObjectInputStream s)
968		throws java.io.IOException, ClassNotFoundException {
969		// Read in any hidden serialization magic
970		s.defaultReadObject();
#	Line 695 \| Line 973 \| public class LinkedList extends Abstract
973		int size = s.readInt();
974
975		// Initialize header
976	<	header = new Entry(null, null, null);
976	>	header = new Entry<E>(null, null, null);
977		header.next = header.previous = header;
978
979		// Read in all elements in the proper order.
980		for (int i=0; i<size; i++)
981	<	add(s.readObject());
704	<	}
705	<
706	<	public Object peek() {
707	<	if (size==0)
708	<	return null;
709	<	return header.previous.element;
710	<	}
711	<
712	<	public Object element() {
713	<	if (size==0)
714	<	throw new NoSuchElementException();
715	<	return header.previous.element;
716	<	}
717	<
718	<	public Object poll() {
719	<	if (size==0)
720	<	return null;
721	<	Object last = header.previous.element;
722	<	remove(header.previous);
723	<	return last;
724	<	}
725	<
726	<	public Object remove() {
727	<	if (size==0)
728	<	throw new NoSuchElementException();
729	<	Object last = header.previous.element;
730	<	remove(header.previous);
731	<	return last;
981	>	addBefore((E)s.readObject(), header);
982		}
733	–
734	–	public boolean offer(Object x) {
735	–	return add(x);
736	–	}
737	–
983		}

Diff Legend

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

Comparing jsr166/src/main/java/util/LinkedList.java (file contents): Revision 1.1 by tim, Wed May 14 21:30:44 2003 UTC vs. Revision 1.49 by jsr166, Sun May 18 23:59:57 2008 UTC

Diff Legend

Comparing jsr166/src/main/java/util/LinkedList.java (file contents):
Revision 1.1 by tim, Wed May 14 21:30:44 2003 UTC vs.
Revision 1.49 by jsr166, Sun May 18 23:59:57 2008 UTC