[ViewVC] Diff of: 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.37 by jsr166, Mon Jul 18 01:14:34 2005 UTC

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

Diff Legend

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

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.37 by jsr166, Mon Jul 18 01:14:34 2005 UTC

Diff Legend

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.37 by jsr166, Mon Jul 18 01:14:34 2005 UTC