[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.28 by jsr166, Mon May 16 05:17:07 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 381 \| Line 381 \| public class LinkedList extends Abstract
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.
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.
387	>	* element
388		*/
389		public int indexOf(Object o) {
390		int index = 0;
#	Line 411 \| Line 411 \| public class LinkedList extends Abstract
411		* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>, or -1 if
412		* there is no such index.
413		*
414	<	* @param o element to search for.
414	>	* @param o element to search for
415		* @return the index in this list of the last occurrence of the
416		* specified element, or -1 if the list does not contain this
417	<	* element.
417	>	* element
418		*/
419		public int lastIndexOf(Object o) {
420		int index = size;
#	Line 434 \| Line 434 \| public class LinkedList extends Abstract
434		return -1;
435		}
436
437	+	// Queue operations.
438	+
439	+	/**
440	+	* Retrieves, but does not remove, the head (first element) of this list.
441	+	* @return the head of this list, or <tt>null</tt> if this list is empty
442	+	* @since 1.5
443	+	*/
444	+	public E peek() {
445	+	if (size==0)
446	+	return null;
447	+	return getFirst();
448	+	}
449	+
450	+	/**
451	+	* Retrieves, but does not remove, the head (first element) of this list.
452	+	* @return the head of this list
453	+	* @throws NoSuchElementException if this list is empty
454	+	* @since 1.5
455	+	*/
456	+	public E element() {
457	+	return getFirst();
458	+	}
459	+
460	+	/**
461	+	* Retrieves and removes the head (first element) of this list
462	+	* @return the head of this list, or <tt>null</tt> if this list is empty
463	+	* @since 1.5
464	+	*/
465	+	public E poll() {
466	+	if (size==0)
467	+	return null;
468	+	return removeFirst();
469	+	}
470	+
471	+	/**
472	+	* Retrieves and removes the head (first element) of this list.
473	+	*
474	+	* @return the head of this list
475	+	* @throws NoSuchElementException if this list is empty
476	+	* @since 1.5
477	+	*/
478	+	public E remove() {
479	+	return removeFirst();
480	+	}
481	+
482	+	/**
483	+	* Adds the specified element as the tail (last element) of this list.
484	+	*
485	+	* @param e the element to add
486	+	* @return <tt>true</tt> (as per the spec for {@link Queue#offer})
487	+	* @since 1.5
488	+	*/
489	+	public boolean offer(E e) {
490	+	return add(e);
491	+	}
492	+
493	+	// Deque operations
494	+	/**
495	+	* Inserts the specified element at the front of this list.
496	+	*
497	+	* @param e the element to insert
498	+	* @return <tt>true</tt> (as per the spec for {@link Deque#offerFirst})
499	+	* @since 1.6
500	+	*/
501	+	public boolean offerFirst(E e) {
502	+	addFirst(e);
503	+	return true;
504	+	}
505	+
506	+	/**
507	+	* Inserts the specified element at the end of this list.
508	+	*
509	+	* @param e the element to insert
510	+	* @return <tt>true</tt> (as per the spec for {@link Deque#offerLast})
511	+	* @since 1.6
512	+	*/
513	+	public boolean offerLast(E e) {
514	+	addLast(e);
515	+	return true;
516	+	}
517	+
518	+	/**
519	+	* Retrieves, but does not remove, the first element of this list,
520	+	* or returns <tt>null</tt> if this list is empty.
521	+	*
522	+	* @return the first element of this list, or <tt>null</tt>
523	+	* if this list is empty
524	+	* @since 1.6
525	+	*/
526	+	public E peekFirst() {
527	+	if (size==0)
528	+	return null;
529	+	return getFirst();
530	+	}
531	+
532	+	/**
533	+	* Retrieves, but does not remove, the last element of this list,
534	+	* or returns <tt>null</tt> if this list is empty.
535	+	*
536	+	* @return the last element of this list, or <tt>null</tt>
537	+	* if this list is empty
538	+	* @since 1.6
539	+	*/
540	+	public E peekLast() {
541	+	if (size==0)
542	+	return null;
543	+	return getLast();
544	+	}
545	+
546	+	/**
547	+	* Retrieves and removes the first element of this list, or
548	+	* <tt>null</tt> if this list is empty.
549	+	*
550	+	* @return the first element of this list, or <tt>null</tt> if
551	+	* this list is empty
552	+	* @since 1.6
553	+	*/
554	+	public E pollFirst() {
555	+	if (size==0)
556	+	return null;
557	+	return removeFirst();
558	+	}
559	+
560	+	/**
561	+	* Retrieves and removes the last element of this list, or
562	+	* <tt>null</tt> if this list is empty.
563	+	*
564	+	* @return the last element of this list, or <tt>null</tt> if
565	+	* this list is empty
566	+	* @since 1.6
567	+	*/
568	+	public E pollLast() {
569	+	if (size==0)
570	+	return null;
571	+	return removeLast();
572	+	}
573	+
574	+	/**
575	+	* Pushes an element onto the stack represented by this list. In other
576	+	* words, inserts the element at the front of this list.
577	+	*
578	+	* <p>This method is equivalent to {@link #addFirst}.
579	+	*
580	+	* @param e the element to push
581	+	* @since 1.6
582	+	*/
583	+	public void push(E e) {
584	+	addFirst(e);
585	+	}
586	+
587	+	/**
588	+	* Pops an element from the stack represented by this list. In other
589	+	* words, removes and returns the first element of this list.
590	+	*
591	+	* <p>This method is equivalent to {@link #removeFirst()}.
592	+	*
593	+	* @return the element at the front of this list (which is the top
594	+	* of the stack represented by this list)
595	+	* @throws NoSuchElementException if this list is empty
596	+	* @since 1.6
597	+	*/
598	+	public E pop() {
599	+	return removeFirst();
600	+	}
601	+
602	+	/**
603	+	* Removes the first occurrence of the specified element in this
604	+	* list (when traversing the list from head to tail). If the list
605	+	* does not contain the element, it is unchanged.
606	+	*
607	+	* @param o element to be removed from this list, if present
608	+	* @return <tt>true</tt> if the list contained the specified element
609	+	* @since 1.6
610	+	*/
611	+	public boolean removeFirstOccurrence(Object o) {
612	+	return remove(o);
613	+	}
614	+
615	+	/**
616	+	* Removes the last occurrence of the specified element in this
617	+	* list (when traversing the list from head to tail). If the list
618	+	* does not contain the element, it is unchanged.
619	+	*
620	+	* @param o element to be removed from this list, if present
621	+	* @return <tt>true</tt> if the list contained the specified element
622	+	* @since 1.6
623	+	*/
624	+	public boolean removeLastOccurrence(Object o) {
625	+	if (o==null) {
626	+	for (Entry e = header.previous; e != header; e = e.previous) {
627	+	if (e.element==null) {
628	+	remove(e);
629	+	return true;
630	+	}
631	+	}
632	+	} else {
633	+	for (Entry e = header.previous; e != header; e = e.previous) {
634	+	if (o.equals(e.element)) {
635	+	remove(e);
636	+	return true;
637	+	}
638	+	}
639	+	}
640	+	return false;
641	+	}
642	+
643		/**
644		* Returns a list-iterator of the elements in this list (in proper
645		* sequence), starting at the specified position in the list.
#	Line 448 \| Line 654 \| public class LinkedList extends Abstract
654		* than risking arbitrary, non-deterministic behavior at an undetermined
655		* time in the future.
656		*
657	<	* @param index index of first element to be returned from the
658	<	* list-iterator (by a call to <tt>next</tt>).
657	>	* @param index index of the first element to be returned from the
658	>	* list-iterator (by a call to <tt>next</tt>)
659		* @return a ListIterator of the elements in this list (in proper
660	<	* sequence), starting at the specified position in the list.
661	<	* @throws IndexOutOfBoundsException if index is out of range
662	<	* (<tt>index < 0 \|\| index > size()</tt>).
663	<	* @see java.util.List#listIterator(int)
664	<	*/
665	<	public ListIterator listIterator(int index) {
666	<	return new ListItr(index);
667	<	}
668	<
669	<	private class ListItr implements ListIterator {
670	<	private Entry lastReturned = header;
671	<	private Entry next;
672	<	private int nextIndex;
673	<	private int expectedModCount = modCount;
674	<
675	<	ListItr(int index) {
676	<	if (index < 0 \|\| index > size)
677	<	throw new IndexOutOfBoundsException("Index: "+index+
678	<	", Size: "+size);
679	<	if (index < (size >> 1)) {
680	<	next = header.next;
681	<	for (nextIndex=0; nextIndex<index; nextIndex++)
682	<	next = next.next;
683	<	} else {
684	<	next = header;
685	<	for (nextIndex=size; nextIndex>index; nextIndex--)
686	<	next = next.previous;
687	<	}
688	<	}
689	<
690	<	public boolean hasNext() {
691	<	return nextIndex != size;
692	<	}
693	<
694	<	public Object next() {
695	<	checkForComodification();
696	<	if (nextIndex == size)
697	<	throw new NoSuchElementException();
698	<
699	<	lastReturned = next;
700	<	next = next.next;
701	<	nextIndex++;
702	<	return lastReturned.element;
703	<	}
704	<
705	<	public boolean hasPrevious() {
706	<	return nextIndex != 0;
707	<	}
708	<
709	<	public Object previous() {
710	<	if (nextIndex == 0)
711	<	throw new NoSuchElementException();
712	<
713	<	lastReturned = next = next.previous;
714	<	nextIndex--;
715	<	checkForComodification();
716	<	return lastReturned.element;
717	<	}
718	<
719	<	public int nextIndex() {
720	<	return nextIndex;
721	<	}
660	>	* sequence), starting at the specified position in the list
661	>	* @throws IndexOutOfBoundsException {@inheritDoc}
662	>	* @see List#listIterator(int)
663	>	*/
664	>	public ListIterator<E> listIterator(int index) {
665	>	return new ListItr(index);
666	>	}
667	>
668	>	private class ListItr implements ListIterator<E> {
669	>	private Entry<E> lastReturned = header;
670	>	private Entry<E> next;
671	>	private int nextIndex;
672	>	private int expectedModCount = modCount;
673	>
674	>	ListItr(int index) {
675	>	if (index < 0 \|\| index > size)
676	>	throw new IndexOutOfBoundsException("Index: "+index+
677	>	", Size: "+size);
678	>	if (index < (size >> 1)) {
679	>	next = header.next;
680	>	for (nextIndex=0; nextIndex<index; nextIndex++)
681	>	next = next.next;
682	>	} else {
683	>	next = header;
684	>	for (nextIndex=size; nextIndex>index; nextIndex--)
685	>	next = next.previous;
686	>	}
687	>	}
688	>
689	>	public boolean hasNext() {
690	>	return nextIndex != size;
691	>	}
692	>
693	>	public E next() {
694	>	checkForComodification();
695	>	if (nextIndex == size)
696	>	throw new NoSuchElementException();
697	>
698	>	lastReturned = next;
699	>	next = next.next;
700	>	nextIndex++;
701	>	return lastReturned.element;
702	>	}
703	>
704	>	public boolean hasPrevious() {
705	>	return nextIndex != 0;
706	>	}
707	>
708	>	public E previous() {
709	>	if (nextIndex == 0)
710	>	throw new NoSuchElementException();
711	>
712	>	lastReturned = next = next.previous;
713	>	nextIndex--;
714	>	checkForComodification();
715	>	return lastReturned.element;
716	>	}
717	>
718	>	public int nextIndex() {
719	>	return nextIndex;
720	>	}
721	>
722	>	public int previousIndex() {
723	>	return nextIndex-1;
724	>	}
725
726	<	public int previousIndex() {
518	<	return nextIndex-1;
519	<	}
520	<
521	<	public void remove() {
726	>	public void remove() {
727		checkForComodification();
728	+	Entry<E> lastNext = lastReturned.next;
729		try {
730		LinkedList.this.remove(lastReturned);
731		} catch (NoSuchElementException e) {
732		throw new IllegalStateException();
733		}
734	<	if (next==lastReturned)
735	<	next = lastReturned.next;
734	>	if (next==lastReturned)
735	>	next = lastNext;
736		else
737	<	nextIndex--;
738	<	lastReturned = header;
739	<	expectedModCount++;
740	<	}
741	<
742	<	public void set(Object o) {
743	<	if (lastReturned == header)
744	<	throw new IllegalStateException();
745	<	checkForComodification();
746	<	lastReturned.element = o;
747	<	}
748	<
749	<	public void add(Object o) {
750	<	checkForComodification();
751	<	lastReturned = header;
752	<	addBefore(o, next);
753	<	nextIndex++;
754	<	expectedModCount++;
755	<	}
756	<
757	<	final void checkForComodification() {
758	<	if (modCount != expectedModCount)
759	<	throw new ConcurrentModificationException();
760	<	}
761	<	}
762	<
763	<	private static class Entry {
764	<	Object element;
765	<	Entry next;
766	<	Entry previous;
767	<
768	<	Entry(Object element, Entry next, Entry previous) {
769	<	this.element = element;
770	<	this.next = next;
771	<	this.previous = previous;
772	<	}
773	<	}
774	<
775	<	private Entry addBefore(Object o, Entry e) {
776	<	Entry newEntry = new Entry(o, e, e.previous);
777	<	newEntry.previous.next = newEntry;
778	<	newEntry.next.previous = newEntry;
779	<	size++;
780	<	modCount++;
781	<	return newEntry;
782	<	}
783	<
784	<	private void remove(Entry e) {
785	<	if (e == header)
786	<	throw new NoSuchElementException();
787	<
788	<	e.previous.next = e.next;
789	<	e.next.previous = e.previous;
790	<	size--;
791	<	modCount++;
737	>	nextIndex--;
738	>	lastReturned = header;
739	>	expectedModCount++;
740	>	}
741	>
742	>	public void set(E e) {
743	>	if (lastReturned == header)
744	>	throw new IllegalStateException();
745	>	checkForComodification();
746	>	lastReturned.element = e;
747	>	}
748	>
749	>	public void add(E e) {
750	>	checkForComodification();
751	>	lastReturned = header;
752	>	addBefore(e, next);
753	>	nextIndex++;
754	>	expectedModCount++;
755	>	}
756	>
757	>	final void checkForComodification() {
758	>	if (modCount != expectedModCount)
759	>	throw new ConcurrentModificationException();
760	>	}
761	>	}
762	>
763	>	private static class Entry<E> {
764	>	E element;
765	>	Entry<E> next;
766	>	Entry<E> previous;
767	>
768	>	Entry(E element, Entry<E> next, Entry<E> previous) {
769	>	this.element = element;
770	>	this.next = next;
771	>	this.previous = previous;
772	>	}
773	>	}
774	>
775	>	private Entry<E> addBefore(E e, Entry<E> entry) {
776	>	Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);
777	>	newEntry.previous.next = newEntry;
778	>	newEntry.next.previous = newEntry;
779	>	size++;
780	>	modCount++;
781	>	return newEntry;
782	>	}
783	>
784	>	private E remove(Entry<E> e) {
785	>	if (e == header)
786	>	throw new NoSuchElementException();
787	>
788	>	E result = e.element;
789	>	e.previous.next = e.next;
790	>	e.next.previous = e.previous;
791	>	e.next = e.previous = null;
792	>	e.element = null;
793	>	size--;
794	>	modCount++;
795	>	return result;
796		}
797
798		/**
799		* Returns a shallow copy of this <tt>LinkedList</tt>. (The elements
800		* themselves are not cloned.)
801		*
802	<	* @return a shallow copy of this <tt>LinkedList</tt> instance.
802	>	* @return a shallow copy of this <tt>LinkedList</tt> instance
803		*/
804		public Object clone() {
805	<	LinkedList clone = null;
806	<	try {
807	<	clone = (LinkedList)super.clone();
808	<	} catch (CloneNotSupportedException e) {
809	<	throw new InternalError();
810	<	}
805	>	LinkedList<E> clone = null;
806	>	try {
807	>	clone = (LinkedList<E>) super.clone();
808	>	} catch (CloneNotSupportedException e) {
809	>	throw new InternalError();
810	>	}
811
812		// Put clone into "virgin" state
813	<	clone.header = new Entry(null, null, null);
813	>	clone.header = new Entry<E>(null, null, null);
814		clone.header.next = clone.header.previous = clone.header;
815		clone.size = 0;
816		clone.modCount = 0;
817
818		// Initialize clone with our elements
819	<	for (Entry e = header.next; e != header; e = e.next)
819	>	for (Entry<E> e = header.next; e != header; e = e.next)
820		clone.add(e.element);
821
822		return clone;
#	Line 617 \| Line 827 \| public class LinkedList extends Abstract
827		* in the correct order.
828		*
829		* @return an array containing all of the elements in this list
830	<	* in the correct order.
830	>	* in the correct order
831		*/
832		public Object[] toArray() {
833	<	Object[] result = new Object[size];
833	>	Object[] result = new Object[size];
834		int i = 0;
835	<	for (Entry e = header.next; e != header; e = e.next)
835	>	for (Entry<E> e = header.next; e != header; e = e.next)
836		result[i++] = e.element;
837	<	return result;
837	>	return result;
838		}
839
840		/**
#	Line 644 \| Line 854 \| public class LinkedList extends Abstract
854		* @param a the array into which the elements of the list are to
855		* be stored, if it is big enough; otherwise, a new array of the
856		* same runtime type is allocated for this purpose.
857	<	* @return an array containing the elements of the list.
857	>	* @return an array containing the elements of the list
858		* @throws ArrayStoreException if the runtime type of a is not a
859	<	* supertype of the runtime type of every element in this list.
860	<	* @throws NullPointerException if the specified array is null.
859	>	* supertype of the runtime type of every element in this list
860	>	* @throws NullPointerException if the specified array is null
861		*/
862	<	public Object[] toArray(Object a[]) {
862	>	public <T> T[] toArray(T[] a) {
863		if (a.length < size)
864	<	a = (Object[])java.lang.reflect.Array.newInstance(
864	>	a = (T[])java.lang.reflect.Array.newInstance(
865		a.getClass().getComponentType(), size);
866		int i = 0;
867	<	for (Entry e = header.next; e != header; e = e.next)
868	<	a[i++] = e.element;
867	>	Object[] result = a;
868	>	for (Entry<E> e = header.next; e != header; e = e.next)
869	>	result[i++] = e.element;
870
871		if (a.length > size)
872		a[size] = null;
#	Line 671 \| Line 882 \| public class LinkedList extends Abstract
882		*
883		* @serialData The size of the list (the number of elements it
884		* contains) is emitted (int), followed by all of its
885	<	* elements (each an Object) in the proper order.
885	>	* elements (each an Object) in the proper order.
886		*/
887	<	private synchronized void writeObject(java.io.ObjectOutputStream s)
887	>	private void writeObject(java.io.ObjectOutputStream s)
888		throws java.io.IOException {
889	<	// Write out any hidden serialization magic
890	<	s.defaultWriteObject();
889	>	// Write out any hidden serialization magic
890	>	s.defaultWriteObject();
891
892		// Write out size
893		s.writeInt(size);
894
895	<	// Write out all elements in the proper order.
895	>	// Write out all elements in the proper order.
896		for (Entry e = header.next; e != header; e = e.next)
897		s.writeObject(e.element);
898		}
#	Line 690 \| Line 901 \| public class LinkedList extends Abstract
901		* Reconstitute this <tt>LinkedList</tt> instance from a stream (that is
902		* deserialize it).
903		*/
904	<	private synchronized void readObject(java.io.ObjectInputStream s)
904	>	private void readObject(java.io.ObjectInputStream s)
905		throws java.io.IOException, ClassNotFoundException {
906	<	// Read in any hidden serialization magic
907	<	s.defaultReadObject();
906	>	// Read in any hidden serialization magic
907	>	s.defaultReadObject();
908
909		// Read in size
910		int size = s.readInt();
911
912		// Initialize header
913	<	header = new Entry(null, null, null);
913	>	header = new Entry<E>(null, null, null);
914		header.next = header.previous = header;
915
916	<	// Read in all elements in the proper order.
917	<	for (int i=0; i<size; i++)
918	<	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();
916	>	// Read in all elements in the proper order.
917	>	for (int i=0; i<size; i++)
918	>	addBefore((E)s.readObject(), header);
919		}
719	–
720	–	public Object poll() {
721	–	if (size==0)
722	–	return null;
723	–	return removeFirst();
724	–	}
725	–
726	–	public Object remove() {
727	–	return removeFirst();
728	–	}
729	–
730	–	public boolean offer(Object x) {
731	–	return add(x);
732	–	}
733	–
920		}

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.28 by jsr166, Mon May 16 05:17:07 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.28 by jsr166, Mon May 16 05:17:07 2005 UTC