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

Comparing jsr166/src/main/java/util/LinkedList.java (file contents):
Revision 1.9 by dl, Sat Oct 18 12:29:27 2003 UTC vs.
Revision 1.45 by jsr166, Sun May 28 23:36:29 2006 UTC

#	Line 1 \| Line 1
1		/*
2		* %W% %E%
3		*
4	<	* Copyright 2003 Sun Microsystems, Inc. All rights reserved.
4	>	* Copyright 2006 Sun Microsystems, Inc. All rights reserved.
5		* SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
6		*/
7
#	Line 14 \| Line 14 \| package java.util;
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	<	* The class implements the <tt>Queue</tt> interface, providing
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>, etc. Other stack and deque operations could be
22	<	* easily recast in terms of the standard list operations. They're
23	<	* included here primarily for convenience, though they may run
24	<	* slightly faster than the equivalent List operations.<p>
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 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
30	<	* modifies the list structurally, it <i>must</i> be synchronized
31	<	* externally. (A structural modification is any operation that adds or
32	<	* deletes one or more elements; merely setting the value of an element is not
33	<	* a structural modification.) This is typically accomplished by
34	<	* synchronizing on some object that naturally encapsulates the list. If no
35	<	* such object exists, the list should be "wrapped" using the
38	<	* Collections.synchronizedList method. This is best done at creation time,
39	<	* to prevent accidental unsynchronized access to the list: <pre>
40	<	* List list = Collections.synchronizedList(new LinkedList(...));
41	<	* </pre><p>
28	>	* <p><strong>Note that this implementation is not synchronized.</strong>
29	>	* If multiple threads access a linked list concurrently, and at least
30	>	* one of the threads modifies the list structurally, it <i>must</i> be
31	>	* synchronized externally. (A structural modification is any operation
32	>	* that adds or deletes one or more elements; merely setting the value of
33	>	* an element is not a structural modification.) This is typically
34	>	* accomplished by synchronizing on some object that naturally
35	>	* encapsulates the list.
36		*
37	<	* The iterators returned by the this class's <tt>iterator</tt> and
37	>	* If no such object exists, the list should be "wrapped" using the
38	>	* {@link Collections#synchronizedList Collections.synchronizedList}
39	>	* method. This is best done at creation time, to prevent accidental
40	>	* unsynchronized access to the list:<pre>
41	>	* List list = Collections.synchronizedList(new LinkedList(...));</pre>
42	>	*
43	>	* <p>The iterators returned by this class's <tt>iterator</tt> and
44		* <tt>listIterator</tt> methods are <i>fail-fast</i>: if the list is
45	<	* structurally modified at any time after the iterator is created, in any way
46	<	* except through the Iterator's own <tt>remove</tt> or <tt>add</tt> methods,
47	<	* the iterator will throw a <tt>ConcurrentModificationException</tt>. Thus,
48	<	* in the face of concurrent modification, the iterator fails quickly and
49	<	* cleanly, rather than risking arbitrary, non-deterministic behavior at an
50	<	* undetermined time in the future.
45	>	* structurally modified at any time after the iterator is created, in
46	>	* any way except through the Iterator's own <tt>remove</tt> or
47	>	* <tt>add</tt> methods, the iterator will throw a {@link
48	>	* ConcurrentModificationException}. Thus, in the face of concurrent
49	>	* modification, the iterator fails quickly and cleanly, rather than
50	>	* risking arbitrary, non-deterministic behavior at an undetermined
51	>	* time in the future.
52		*
53		* <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
54		* as it is, generally speaking, impossible to make any hard guarantees in the
#	Line 55 \| Line 56 \| package java.util;
56		* throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
57		* Therefore, it would be wrong to write a program that depended on this
58		* exception for its correctness: <i>the fail-fast behavior of iterators
59	<	* should be used only to detect bugs.</i><p>
59	>	* should be used only to detect bugs.</i>
60		*
61	<	* This class is a member of the
62	<	* <a href="{@docRoot}/../guide/collections/index.html">
61	>	* <p>This class is a member of the
62	>	* <a href="{@docRoot}/../technotes/guides/collections/index.html">
63		* Java Collections Framework</a>.
64		*
65		* @author Josh Bloch
#	Line 66 \| Line 67 \| package java.util;
67		* @see List
68		* @see ArrayList
69		* @see Vector
69	–	* @see Collections#synchronizedList(List)
70		* @since 1.2
71	<	* @param <E> the base class of all elements held in this collection
71	>	* @param <E> the type of elements held in this collection
72		*/
73
74		public class LinkedList<E>
75		extends AbstractSequentialList<E>
76	<	implements List<E>, Queue<E>, Cloneable, java.io.Serializable
76	>	implements List<E>, Deque<E>, Cloneable, java.io.Serializable
77		{
78		private transient Entry<E> header = new Entry<E>(null, null, null);
79		private transient int size = 0;
#	Line 90 \| Line 90 \| public class LinkedList<E>
90		* collection, in the order they are returned by the collection's
91		* iterator.
92		*
93	<	* @param c the collection whose elements are to be placed into this list.
94	<	* @throws NullPointerException if the specified collection is null.
93	>	* @param c the collection whose elements are to be placed into this list
94	>	* @throws NullPointerException if the specified collection is null
95		*/
96	<	public LinkedList(Collection<? extends E> c) {
97	<	this();
98	<	addAll(c);
99	<	}
96	>	public LinkedList(Collection<? extends E> c) {
97	>	this();
98	>	addAll(c);
99	>	}
100
101		/**
102		* Returns the first element in this list.
103		*
104	<	* @return the first element in this list.
105	<	* @throws NoSuchElementException if this list is empty.
104	>	* @return the first element in this list
105	>	* @throws NoSuchElementException if this list is empty
106		*/
107		public E getFirst() {
108		if (size==0)
#	Line 114 \| Line 114 \| public class LinkedList<E>
114		/**
115		* Returns the last element in this list.
116		*
117	<	* @return the last element in this list.
118	<	* @throws NoSuchElementException if this list is empty.
117	>	* @return the last element in this list
118	>	* @throws NoSuchElementException if this list is empty
119		*/
120		public E getLast() {
121		if (size==0)
#	Line 127 \| Line 127 \| public class LinkedList<E>
127		/**
128		* Removes and returns the first element from this list.
129		*
130	<	* @return the first element from this list.
131	<	* @throws NoSuchElementException if this list is empty.
130	>	* @return the first element from this list
131	>	* @throws NoSuchElementException if this list is empty
132		*/
133		public E removeFirst() {
134	<	E first = header.next.element;
135	<	remove(header.next);
136	<	return first;
134	>	return remove(header.next);
135		}
136
137		/**
138		* Removes and returns the last element from this list.
139		*
140	<	* @return the last element from this list.
141	<	* @throws NoSuchElementException if this list is empty.
140	>	* @return the last element from this list
141	>	* @throws NoSuchElementException if this list is empty
142		*/
143		public E removeLast() {
144	<	E last = header.previous.element;
147	<	remove(header.previous);
148	<	return last;
144	>	return remove(header.previous);
145		}
146
147		/**
148	<	* Inserts the given element at the beginning of this list.
148	>	* Inserts the specified element at the beginning of this list.
149		*
150	<	* @param o the element to be inserted at the beginning of this list.
150	>	* @param e the element to add
151		*/
152	<	public void addFirst(E o) {
153	<	addBefore(o, header.next);
152	>	public void addFirst(E e) {
153	>	addBefore(e, header.next);
154		}
155
156		/**
157	<	* Appends the given element to the end of this list. (Identical in
158	<	* function to the <tt>add</tt> method; included only for consistency.)
157	>	* Appends the specified element to the end of this list.
158	>	*
159	>	* <p>This method is equivalent to {@link #add}.
160		*
161	<	* @param o the element to be inserted at the end of this list.
161	>	* @param e the element to add
162		*/
163	<	public void addLast(E o) {
164	<	addBefore(o, header);
163	>	public void addLast(E e) {
164	>	addBefore(e, header);
165		}
166
167		/**
168		* Returns <tt>true</tt> if this list contains the specified element.
169		* More formally, returns <tt>true</tt> if and only if this list contains
170	<	* at least one element <tt>e</tt> such that <tt>(o==null ? e==null
171	<	* : o.equals(e))</tt>.
170	>	* at least one element <tt>e</tt> such that
171	>	* <tt>(o==null ? e==null : o.equals(e))</tt>.
172		*
173	<	* @param o element whose presence in this list is to be tested.
174	<	* @return <tt>true</tt> if this list contains the specified element.
173	>	* @param o element whose presence in this list is to be tested
174	>	* @return <tt>true</tt> if this list contains the specified element
175		*/
176		public boolean contains(Object o) {
177		return indexOf(o) != -1;
#	Line 183 \| Line 180 \| public class LinkedList<E>
180		/**
181		* Returns the number of elements in this list.
182		*
183	<	* @return the number of elements in this list.
183	>	* @return the number of elements in this list
184		*/
185		public int size() {
186		return size;
#	Line 192 \| Line 189 \| public class LinkedList<E>
189		/**
190		* Appends the specified element to the end of this list.
191		*
192	<	* @param o element to be appended to this list.
193	<	* @return <tt>true</tt> (as per the general contract of
194	<	* <tt>Collection.add</tt>).
192	>	* <p>This method is equivalent to {@link #addLast}.
193	>	*
194	>	* @param e element to be appended to this list
195	>	* @return <tt>true</tt> (as specified by {@link Collection#add})
196		*/
197	<	public boolean add(E o) {
198	<	addBefore(o, header);
197	>	public boolean add(E e) {
198	>	addBefore(e, header);
199		return true;
200		}
201
202		/**
203	<	* Removes the first occurrence of the specified element in this list. If
204	<	* the list does not contain the element, it is unchanged. More formally,
205	<	* removes the element with the lowest index <tt>i</tt> such that
206	<	* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt> (if such an
207	<	* element exists).
203	>	* Removes the first occurrence of the specified element from this list,
204	>	* if it is present. If this list does not contain the element, it is
205	>	* unchanged. More formally, removes the element with the lowest index
206	>	* <tt>i</tt> such that
207	>	* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>
208	>	* (if such an element exists). Returns <tt>true</tt> if this list
209	>	* contained the specified element (or equivalently, if this list
210	>	* changed as a result of the call).
211		*
212	<	* @param o element to be removed from this list, if present.
213	<	* @return <tt>true</tt> if the list contained the specified element.
212	>	* @param o element to be removed from this list, if present
213	>	* @return <tt>true</tt> if this list contained the specified element
214		*/
215		public boolean remove(Object o) {
216		if (o==null) {
#	Line 235 \| Line 236 \| public class LinkedList<E>
236		* this list, in the order that they are returned by the specified
237		* collection's iterator. The behavior of this operation is undefined if
238		* the specified collection is modified while the operation is in
239	<	* progress. (This implies that the behavior of this call is undefined if
240	<	* the specified Collection is this list, and this list is nonempty.)
239	>	* progress. (Note that this will occur if the specified collection is
240	>	* this list, and it's nonempty.)
241		*
242	<	* @param c the elements to be inserted into this list.
243	<	* @return <tt>true</tt> if this list changed as a result of the call.
244	<	* @throws NullPointerException if the specified collection is null.
242	>	* @param c collection containing elements to be added to this list
243	>	* @return <tt>true</tt> if this list changed as a result of the call
244	>	* @throws NullPointerException if the specified collection is null
245		*/
246		public boolean addAll(Collection<? extends E> c) {
247		return addAll(size, c);
#	Line 254 \| Line 255 \| public class LinkedList<E>
255		* in the list in the order that they are returned by the
256		* specified collection's iterator.
257		*
258	<	* @param index index at which to insert first element
259	<	* from the specified collection.
260	<	* @param c elements to be inserted into this list.
261	<	* @return <tt>true</tt> if this list changed as a result of the call.
262	<	* @throws IndexOutOfBoundsException if the specified index is out of
263	<	* range (<tt>index < 0 \|\| index > size()</tt>).
263	<	* @throws NullPointerException if the specified collection is null.
258	>	* @param index index at which to insert the first element
259	>	* from the specified collection
260	>	* @param c collection containing elements to be added to this list
261	>	* @return <tt>true</tt> if this list changed as a result of the call
262	>	* @throws IndexOutOfBoundsException {@inheritDoc}
263	>	* @throws NullPointerException if the specified collection is null
264		*/
265		public boolean addAll(int index, Collection<? extends E> c) {
266		if (index < 0 \|\| index > size)
#	Line 289 \| Line 289 \| public class LinkedList<E>
289		* Removes all of the elements from this list.
290		*/
291		public void clear() {
292	<	modCount++;
292	>	Entry<E> e = header.next;
293	>	while (e != header) {
294	>	Entry<E> next = e.next;
295	>	e.next = e.previous = null;
296	>	e.element = null;
297	>	e = next;
298	>	}
299		header.next = header.previous = header;
300	<	size = 0;
300	>	size = 0;
301	>	modCount++;
302		}
303
304
#	Line 300 \| Line 307 \| public class LinkedList<E>
307		/**
308		* Returns the element at the specified position in this list.
309		*
310	<	* @param index index of element to return.
311	<	* @return the element at the specified position in this list.
312	<	*
306	<	* @throws IndexOutOfBoundsException if the specified index is is out of
307	<	* range (<tt>index < 0 \|\| index >= size()</tt>).
310	>	* @param index index of the element to return
311	>	* @return the element at the specified position in this list
312	>	* @throws IndexOutOfBoundsException {@inheritDoc}
313		*/
314		public E get(int index) {
315		return entry(index).element;
#	Line 314 \| Line 319 \| public class LinkedList<E>
319		* Replaces the element at the specified position in this list with the
320		* specified element.
321		*
322	<	* @param index index of element to replace.
323	<	* @param element element to be stored at the specified position.
324	<	* @return the element previously at the specified position.
325	<	* @throws IndexOutOfBoundsException if the specified index is out of
321	<	* range (<tt>index < 0 \|\| index >= size()</tt>).
322	>	* @param index index of the element to replace
323	>	* @param element element to be stored at the specified position
324	>	* @return the element previously at the specified position
325	>	* @throws IndexOutOfBoundsException {@inheritDoc}
326		*/
327		public E set(int index, E element) {
328		Entry<E> e = entry(index);
#	Line 332 \| Line 336 \| public class LinkedList<E>
336		* Shifts the element currently at that position (if any) and any
337		* subsequent elements to the right (adds one to their indices).
338		*
339	<	* @param index index at which the specified element is to be inserted.
340	<	* @param element element to be inserted.
341	<	*
338	<	* @throws IndexOutOfBoundsException if the specified index is out of
339	<	* range (<tt>index < 0 \|\| index > size()</tt>).
339	>	* @param index index at which the specified element is to be inserted
340	>	* @param element element to be inserted
341	>	* @throws IndexOutOfBoundsException {@inheritDoc}
342		*/
343		public void add(int index, E element) {
344		addBefore(element, (index==size ? header : entry(index)));
#	Line 347 \| Line 349 \| public class LinkedList<E>
349		* subsequent elements to the left (subtracts one from their indices).
350		* Returns the element that was removed from the list.
351		*
352	<	* @param index the index of the element to removed.
353	<	* @return the element previously at the specified position.
354	<	*
353	<	* @throws IndexOutOfBoundsException if the specified index is out of
354	<	* range (<tt>index < 0 \|\| index >= size()</tt>).
352	>	* @param index the index of the element to be removed
353	>	* @return the element previously at the specified position
354	>	* @throws IndexOutOfBoundsException {@inheritDoc}
355		*/
356		public E remove(int index) {
357	<	Entry<E> e = entry(index);
358	<	remove(e);
359	<	return e.element;
357	>	return remove(entry(index));
358		}
359
360		/**
361	<	* Return the indexed entry.
361	>	* Returns the indexed entry.
362		*/
363		private Entry<E> entry(int index) {
364		if (index < 0 \|\| index >= size)
#	Line 381 \| Line 379 \| public class LinkedList<E>
379		// Search Operations
380
381		/**
382	<	* Returns the index in this list of the first occurrence of the
383	<	* specified element, or -1 if the List does not contain this
384	<	* element. More formally, returns the lowest index i such that
385	<	* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>, or -1 if
386	<	* there is no such index.
387	<	*
388	<	* @param o element to search for.
389	<	* @return the index in this list of the first occurrence of the
390	<	* specified element, or -1 if the list does not contain this
393	<	* element.
382	>	* Returns the index of the first occurrence of the specified element
383	>	* in this list, or -1 if this list does not contain the element.
384	>	* More formally, returns the lowest index <tt>i</tt> such that
385	>	* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>,
386	>	* or -1 if there is no such index.
387	>	*
388	>	* @param o element to search for
389	>	* @return the index of the first occurrence of the specified element in
390	>	* this list, or -1 if this list does not contain the element
391		*/
392		public int indexOf(Object o) {
393		int index = 0;
#	Line 411 \| Line 408 \| public class LinkedList<E>
408		}
409
410		/**
411	<	* Returns the index in this list of the last occurrence of the
412	<	* specified element, or -1 if the list does not contain this
413	<	* element. More formally, returns the highest index i such that
414	<	* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>, or -1 if
415	<	* there is no such index.
416	<	*
417	<	* @param o element to search for.
418	<	* @return the index in this list of the last occurrence of the
419	<	* specified element, or -1 if the list does not contain this
423	<	* element.
411	>	* Returns the index of the last occurrence of the specified element
412	>	* in this list, or -1 if this list does not contain the element.
413	>	* More formally, returns the highest index <tt>i</tt> such that
414	>	* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>,
415	>	* or -1 if there is no such index.
416	>	*
417	>	* @param o element to search for
418	>	* @return the index of the last occurrence of the specified element in
419	>	* this list, or -1 if this list does not contain the element
420		*/
421		public int lastIndexOf(Object o) {
422		int index = size;
#	Line 444 \| Line 440 \| public class LinkedList<E>
440
441		/**
442		* Retrieves, but does not remove, the head (first element) of this list.
443	<	* @return the head of this queue, or <tt>null</tt> if this queue is empty.
443	>	* @return the head of this list, or <tt>null</tt> if this list is empty
444		* @since 1.5
445		*/
446		public E peek() {
#	Line 455 \| Line 451 \| public class LinkedList<E>
451
452		/**
453		* Retrieves, but does not remove, the head (first element) of this list.
454	<	* @return the head of this queue.
455	<	* @throws NoSuchElementException if this queue is empty.
454	>	* @return the head of this list
455	>	* @throws NoSuchElementException if this list is empty
456		* @since 1.5
457		*/
458		public E element() {
#	Line 464 \| Line 460 \| public class LinkedList<E>
460		}
461
462		/**
463	<	* Retrieves and removes the head (first element) of this list.
464	<	* @return the head of this queue, or <tt>null</tt> if this queue is empty.
463	>	* Retrieves and removes the head (first element) of this list
464	>	* @return the head of this list, or <tt>null</tt> if this list is empty
465		* @since 1.5
466		*/
467		public E poll() {
#	Line 476 \| Line 472 \| public class LinkedList<E>
472
473		/**
474		* Retrieves and removes the head (first element) of this list.
475	<	* @return the head of this queue.
476	<	* @throws NoSuchElementException if this queue is empty.
475	>	*
476	>	* @return the head of this list
477	>	* @throws NoSuchElementException if this list is empty
478		* @since 1.5
479		*/
480		public E remove() {
#	Line 487 \| Line 484 \| public class LinkedList<E>
484		/**
485		* Adds the specified element as the tail (last element) of this list.
486		*
487	<	* @param x the element to add.
488	<	* @return <tt>true</tt> (as per the general contract of
492	<	* <tt>Queue.offer</tt>)
487	>	* @param e the element to add
488	>	* @return <tt>true</tt> (as specified by {@link Queue#offer})
489		* @since 1.5
490		*/
491	<	public boolean offer(E x) {
492	<	return add(x);
491	>	public boolean offer(E e) {
492	>	return add(e);
493	>	}
494	>
495	>	// Deque operations
496	>	/**
497	>	* Inserts the specified element at the front of this list.
498	>	*
499	>	* @param e the element to insert
500	>	* @return <tt>true</tt> (as specified by {@link Deque#offerFirst})
501	>	* @since 1.6
502	>	*/
503	>	public boolean offerFirst(E e) {
504	>	addFirst(e);
505	>	return true;
506	>	}
507	>
508	>	/**
509	>	* Inserts the specified element at the end of this list.
510	>	*
511	>	* @param e the element to insert
512	>	* @return <tt>true</tt> (as specified by {@link Deque#offerLast})
513	>	* @since 1.6
514	>	*/
515	>	public boolean offerLast(E e) {
516	>	addLast(e);
517	>	return true;
518	>	}
519	>
520	>	/**
521	>	* Retrieves, but does not remove, the first element of this list,
522	>	* or returns <tt>null</tt> if this list is empty.
523	>	*
524	>	* @return the first element of this list, or <tt>null</tt>
525	>	* if this list is empty
526	>	* @since 1.6
527	>	*/
528	>	public E peekFirst() {
529	>	if (size==0)
530	>	return null;
531	>	return getFirst();
532	>	}
533	>
534	>	/**
535	>	* Retrieves, but does not remove, the last element of this list,
536	>	* or returns <tt>null</tt> if this list is empty.
537	>	*
538	>	* @return the last element of this list, or <tt>null</tt>
539	>	* if this list is empty
540	>	* @since 1.6
541	>	*/
542	>	public E peekLast() {
543	>	if (size==0)
544	>	return null;
545	>	return getLast();
546	>	}
547	>
548	>	/**
549	>	* Retrieves and removes the first element of this list,
550	>	* or returns <tt>null</tt> if this list is empty.
551	>	*
552	>	* @return the first element of this list, or <tt>null</tt> if
553	>	* this list is empty
554	>	* @since 1.6
555	>	*/
556	>	public E pollFirst() {
557	>	if (size==0)
558	>	return null;
559	>	return removeFirst();
560	>	}
561	>
562	>	/**
563	>	* Retrieves and removes the last element of this list,
564	>	* or returns <tt>null</tt> if this list is empty.
565	>	*
566	>	* @return the last element of this list, or <tt>null</tt> if
567	>	* this list is empty
568	>	* @since 1.6
569	>	*/
570	>	public E pollLast() {
571	>	if (size==0)
572	>	return null;
573	>	return removeLast();
574	>	}
575	>
576	>	/**
577	>	* Pushes an element onto the stack represented by this list. In other
578	>	* words, inserts the element at the front of this list.
579	>	*
580	>	* <p>This method is equivalent to {@link #addFirst}.
581	>	*
582	>	* @param e the element to push
583	>	* @since 1.6
584	>	*/
585	>	public void push(E e) {
586	>	addFirst(e);
587	>	}
588	>
589	>	/**
590	>	* Pops an element from the stack represented by this list. In other
591	>	* words, removes and returns the first element of this list.
592	>	*
593	>	* <p>This method is equivalent to {@link #removeFirst()}.
594	>	*
595	>	* @return the element at the front of this list (which is the top
596	>	* of the stack represented by this list)
597	>	* @throws NoSuchElementException if this list is empty
598	>	* @since 1.6
599	>	*/
600	>	public E pop() {
601	>	return removeFirst();
602	>	}
603	>
604	>	/**
605	>	* Removes the first occurrence of the specified element in this
606	>	* list (when traversing the list from head to tail). If the list
607	>	* does not contain the element, it is unchanged.
608	>	*
609	>	* @param o element to be removed from this list, if present
610	>	* @return <tt>true</tt> if the list contained the specified element
611	>	* @since 1.6
612	>	*/
613	>	public boolean removeFirstOccurrence(Object o) {
614	>	return remove(o);
615	>	}
616	>
617	>	/**
618	>	* Removes the last occurrence of the specified element in this
619	>	* list (when traversing the list from head to tail). If the list
620	>	* does not contain the element, it is unchanged.
621	>	*
622	>	* @param o element to be removed from this list, if present
623	>	* @return <tt>true</tt> if the list contained the specified element
624	>	* @since 1.6
625	>	*/
626	>	public boolean removeLastOccurrence(Object o) {
627	>	if (o==null) {
628	>	for (Entry<E> e = header.previous; e != header; e = e.previous) {
629	>	if (e.element==null) {
630	>	remove(e);
631	>	return true;
632	>	}
633	>	}
634	>	} else {
635	>	for (Entry<E> e = header.previous; e != header; e = e.previous) {
636	>	if (o.equals(e.element)) {
637	>	remove(e);
638	>	return true;
639	>	}
640	>	}
641	>	}
642	>	return false;
643		}
644
645		/**
#	Line 510 \| Line 656 \| public class LinkedList<E>
656		* than risking arbitrary, non-deterministic behavior at an undetermined
657		* time in the future.
658		*
659	<	* @param index index of first element to be returned from the
660	<	* list-iterator (by a call to <tt>next</tt>).
659	>	* @param index index of the first element to be returned from the
660	>	* list-iterator (by a call to <tt>next</tt>)
661		* @return a ListIterator of the elements in this list (in proper
662	<	* sequence), starting at the specified position in the list.
663	<	* @throws IndexOutOfBoundsException if index is out of range
518	<	* (<tt>index < 0 \|\| index > size()</tt>).
662	>	* sequence), starting at the specified position in the list
663	>	* @throws IndexOutOfBoundsException {@inheritDoc}
664		* @see List#listIterator(int)
665		*/
666		public ListIterator<E> listIterator(int index) {
#	Line 582 \| Line 727 \| public class LinkedList<E>
727
728		public void remove() {
729		checkForComodification();
730	+	Entry<E> lastNext = lastReturned.next;
731		try {
732		LinkedList.this.remove(lastReturned);
733		} catch (NoSuchElementException e) {
734		throw new IllegalStateException();
735		}
736		if (next==lastReturned)
737	<	next = lastReturned.next;
737	>	next = lastNext;
738		else
739		nextIndex--;
740		lastReturned = header;
741		expectedModCount++;
742		}
743
744	<	public void set(E o) {
744	>	public void set(E e) {
745		if (lastReturned == header)
746		throw new IllegalStateException();
747		checkForComodification();
748	<	lastReturned.element = o;
748	>	lastReturned.element = e;
749		}
750
751	<	public void add(E o) {
751	>	public void add(E e) {
752		checkForComodification();
753		lastReturned = header;
754	<	addBefore(o, next);
754	>	addBefore(e, next);
755		nextIndex++;
756		expectedModCount++;
757		}
#	Line 628 \| Line 774 \| public class LinkedList<E>
774		}
775		}
776
777	<	private Entry<E> addBefore(E o, Entry<E> e) {
778	<	Entry<E> newEntry = new Entry<E>(o, e, e.previous);
777	>	private Entry<E> addBefore(E e, Entry<E> entry) {
778	>	Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);
779		newEntry.previous.next = newEntry;
780		newEntry.next.previous = newEntry;
781		size++;
#	Line 637 \| Line 783 \| public class LinkedList<E>
783		return newEntry;
784		}
785
786	<	private void remove(Entry<E> e) {
786	>	private E remove(Entry<E> e) {
787		if (e == header)
788		throw new NoSuchElementException();
789
790	+	E result = e.element;
791		e.previous.next = e.next;
792		e.next.previous = e.previous;
793	+	e.next = e.previous = null;
794	+	e.element = null;
795		size--;
796		modCount++;
797	+	return result;
798	+	}
799	+
800	+	/**
801	+	* @since 1.6
802	+	*/
803	+	public Iterator<E> descendingIterator() {
804	+	return new DescendingIterator();
805	+	}
806	+
807	+	/** Adapter to provide descending iterators via ListItr.previous */
808	+	private class DescendingIterator implements Iterator {
809	+	final ListItr itr = new ListItr(size());
810	+	public boolean hasNext() {
811	+	return itr.hasPrevious();
812	+	}
813	+	public E next() {
814	+	return itr.previous();
815	+	}
816	+	public void remove() {
817	+	itr.remove();
818	+	}
819		}
820
821		/**
822		* Returns a shallow copy of this <tt>LinkedList</tt>. (The elements
823		* themselves are not cloned.)
824		*
825	<	* @return a shallow copy of this <tt>LinkedList</tt> instance.
825	>	* @return a shallow copy of this <tt>LinkedList</tt> instance
826		*/
827		public Object clone() {
828		LinkedList<E> clone = null;
#	Line 676 \| Line 847 \| public class LinkedList<E>
847
848		/**
849		* Returns an array containing all of the elements in this list
850	<	* in the correct order.
850	>	* in proper sequence (from first to last element).
851	>	*
852	>	* <p>The returned array will be "safe" in that no references to it are
853	>	* maintained by this list. (In other words, this method must allocate
854	>	* a new array). The caller is thus free to modify the returned array.
855	>	*
856	>	* <p>This method acts as bridge between array-based and collection-based
857	>	* APIs.
858		*
859		* @return an array containing all of the elements in this list
860	<	* in the correct order.
860	>	* in proper sequence
861		*/
862		public Object[] toArray() {
863		Object[] result = new Object[size];
#	Line 691 \| Line 869 \| public class LinkedList<E>
869
870		/**
871		* Returns an array containing all of the elements in this list in
872	<	* the correct order; the runtime type of the returned array is that of
873	<	* the specified array. If the list fits in the specified array, it
874	<	* is returned therein. Otherwise, a new array is allocated with the
875	<	* runtime type of the specified array and the size of this list.<p>
876	<	*
877	<	* If the list fits in the specified array with room to spare
878	<	* (i.e., the array has more elements than the list),
879	<	* the element in the array immediately following the end of the
880	<	* collection is set to null. This is useful in determining the length
881	<	* of the list <i>only</i> if the caller knows that the list
882	<	* does not contain any null elements.
872	>	* proper sequence (from first to last element); the runtime type of
873	>	* the returned array is that of the specified array. If the list fits
874	>	* in the specified array, it is returned therein. Otherwise, a new
875	>	* array is allocated with the runtime type of the specified array and
876	>	* the size of this list.
877	>	*
878	>	* <p>If the list fits in the specified array with room to spare (i.e.,
879	>	* the array has more elements than the list), the element in the array
880	>	* immediately following the end of the list is set to <tt>null</tt>.
881	>	* (This is useful in determining the length of the list <i>only</i> if
882	>	* the caller knows that the list does not contain any null elements.)
883	>	*
884	>	* <p>Like the {@link #toArray()} method, this method acts as bridge between
885	>	* array-based and collection-based APIs. Further, this method allows
886	>	* precise control over the runtime type of the output array, and may,
887	>	* under certain circumstances, be used to save allocation costs.
888	>	*
889	>	* <p>Suppose <tt>x</tt> is a list known to contain only strings.
890	>	* The following code can be used to dump the list into a newly
891	>	* allocated array of <tt>String</tt>:
892	>	*
893	>	* <pre>
894	>	* String[] y = x.toArray(new String[0]);</pre>
895	>	*
896	>	* Note that <tt>toArray(new Object[0])</tt> is identical in function to
897	>	* <tt>toArray()</tt>.
898		*
899		* @param a the array into which the elements of the list are to
900	<	* be stored, if it is big enough; otherwise, a new array of the
901	<	* same runtime type is allocated for this purpose.
902	<	* @return an array containing the elements of the list.
903	<	* @throws ArrayStoreException if the runtime type of a is not a
904	<	* supertype of the runtime type of every element in this list.
905	<	* @throws NullPointerException if the specified array is null.
900	>	* be stored, if it is big enough; otherwise, a new array of the
901	>	* same runtime type is allocated for this purpose.
902	>	* @return an array containing the elements of the list
903	>	* @throws ArrayStoreException if the runtime type of the specified array
904	>	* is not a supertype of the runtime type of every element in
905	>	* this list
906	>	* @throws NullPointerException if the specified array is null
907		*/
908		public <T> T[] toArray(T[] a) {
909		if (a.length < size)
#	Line 733 \| Line 927 \| public class LinkedList<E>
927		* is, serialize it).
928		*
929		* @serialData The size of the list (the number of elements it
930	<	* contains) is emitted (int), followed by all of its
931	<	* elements (each an Object) in the proper order.
930	>	* contains) is emitted (int), followed by all of its
931	>	* elements (each an Object) in the proper order.
932		*/
933		private void writeObject(java.io.ObjectOutputStream s)
934		throws java.io.IOException {

Diff Legend

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

Comparing jsr166/src/main/java/util/LinkedList.java (file contents): Revision 1.9 by dl, Sat Oct 18 12:29:27 2003 UTC vs. Revision 1.45 by jsr166, Sun May 28 23:36:29 2006 UTC

Diff Legend

Comparing jsr166/src/main/java/util/LinkedList.java (file contents):
Revision 1.9 by dl, Sat Oct 18 12:29:27 2003 UTC vs.
Revision 1.45 by jsr166, Sun May 28 23:36:29 2006 UTC