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

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.29 by jsr166, Tue May 17 04:09:23 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.29 by jsr166, Tue May 17 04:09:23 2005 UTC