ViewVC Help

View File | Revision Log | Show Annotations | Download File | Root Listing

root/jsr166/jsr166/src/main/java/util/LinkedList.java

Comparing jsr166/src/main/java/util/LinkedList.java (file contents):
Revision 1.24 by jsr166, Tue Apr 26 19:54:03 2005 UTC vs.
Revision 1.48 by jsr166, Sun May 18 23:47:56 2008 UTC

#	Line 1 | Line 1
1		/*
2	<	* %W% %E%
2	>	* Copyright 1997-2006 Sun Microsystems, Inc.  All Rights Reserved.
3	>	* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4		*
5	<	* Copyright 2005 Sun Microsystems, Inc. All rights reserved.
6	<	* SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
5	>	* This code is free software; you can redistribute it and/or modify it
6	>	* under the terms of the GNU General Public License version 2 only, as
7	>	* published by the Free Software Foundation.  Sun designates this
8	>	* particular file as subject to the "Classpath" exception as provided
9	>	* by Sun in the LICENSE file that accompanied this code.
10	>	*
11	>	* This code is distributed in the hope that it will be useful, but WITHOUT
12	>	* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13	>	* FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
14	>	* version 2 for more details (a copy is included in the LICENSE file that
15	>	* accompanied this code).
16	>	*
17	>	* You should have received a copy of the GNU General Public License version
18	>	* 2 along with this work; if not, write to the Free Software Foundation,
19	>	* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20	>	*
21	>	* Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
22	>	* CA 95054 USA or visit www.sun.com if you need additional information or
23	>	* have any questions.
24		*/
25
26		package java.util;
#	Line 25 | Line 43 | package java.util;
43		* list.  Operations that index into the list will traverse the list from
44		* the beginning or the end, whichever is closer to the specified index.<p>
45		*
46	<	* <b>Note that this implementation is not synchronized.</b> If multiple
47	<	* threads access a list concurrently, and at least one of the threads
48	<	* modifies the list structurally, it <i>must</i> be synchronized
49	<	* externally.  (A structural modification is any operation that adds or
50	<	* deletes one or more elements; merely setting the value of an element is not
51	<	* a structural modification.)  This is typically accomplished by
52	<	* synchronizing on some object that naturally encapsulates the list.  If no
53	<	* such object exists, the list should be "wrapped" using the
54	<	* Collections.synchronizedList method.  This is best done at creation time,
55	<	* to prevent accidental unsynchronized access to the list: <pre>
56	<	*     List list = Collections.synchronizedList(new LinkedList(...));
57	<	* </pre>
46	>	* <p><strong>Note that this implementation is not synchronized.</strong>
47	>	* If multiple threads access a linked list concurrently, and at least
48	>	* one of the threads modifies the list structurally, it <i>must</i> be
49	>	* synchronized externally.  (A structural modification is any operation
50	>	* that adds or deletes one or more elements; merely setting the value of
51	>	* an element is not a structural modification.)  This is typically
52	>	* accomplished by synchronizing on some object that naturally
53	>	* encapsulates the list.
54	>	*
55	>	* If no such object exists, the list should be "wrapped" using the
56	>	* {@link Collections#synchronizedList Collections.synchronizedList}
57	>	* method.  This is best done at creation time, to prevent accidental
58	>	* unsynchronized access to the list:<pre>
59	>	*   List list = Collections.synchronizedList(new LinkedList(...));</pre>
60		*
61		* <p>The iterators returned by this class's <tt>iterator</tt> and
62		* <tt>listIterator</tt> methods are <i>fail-fast</i>: if the list is
#	Line 57 | Line 77 | package java.util;
77		* should be used only to detect bugs.</i>
78		*
79		* <p>This class is a member of the
80	<	* <a href="{@docRoot}/../guide/collections/index.html">
80	>	* <a href="{@docRoot}/../technotes/guides/collections/index.html">
81		* Java Collections Framework</a>.
82		*
83		* @author  Josh Bloch
84		* @version %I%, %G%
85	<	* @see     List
86	<	* @see     ArrayList
87	<	* @see     Vector
68	<	* @see     Collections#synchronizedList(List)
85	>	* @see     List
86	>	* @see     ArrayList
87	>	* @see     Vector
88		* @since 1.2
89		* @param <E> the type of elements held in this collection
90		*/
#	Line 89 | Line 108 | public class LinkedList<E>
108		* collection, in the order they are returned by the collection's
109		* iterator.
110		*
111	<	* @param  c the collection whose elements are to be placed into this list.
112	<	* @throws NullPointerException if the specified collection is null.
111	>	* @param  c the collection whose elements are to be placed into this list
112	>	* @throws NullPointerException if the specified collection is null
113		*/
114	<	public LinkedList(Collection<? extends E> c) {
115	<	this();
116	<	addAll(c);
117	<	}
114	>	public LinkedList(Collection<? extends E> c) {
115	>	this();
116	>	addAll(c);
117	>	}
118
119		/**
120		* Returns the first element in this list.
121		*
122	<	* @return the first element in this list.
123	<	* @throws    NoSuchElementException if this list is empty.
122	>	* @return the first element in this list
123	>	* @throws NoSuchElementException if this list is empty
124		*/
125		public E getFirst() {
126	<	if (size==0)
127	<	throw new NoSuchElementException();
126	>	if (size==0)
127	>	throw new NoSuchElementException();
128
129	<	return header.next.element;
129	>	return header.next.element;
130		}
131
132		/**
133		* Returns the last element in this list.
134		*
135	<	* @return the last element in this list.
136	<	* @throws    NoSuchElementException if this list is empty.
135	>	* @return the last element in this list
136	>	* @throws NoSuchElementException if this list is empty
137		*/
138		public E getLast()  {
139	<	if (size==0)
140	<	throw new NoSuchElementException();
139	>	if (size==0)
140	>	throw new NoSuchElementException();
141
142	<	return header.previous.element;
142	>	return header.previous.element;
143		}
144
145		/**
146		* Removes and returns the first element from this list.
147		*
148	<	* @return the first element from this list.
149	<	* @throws    NoSuchElementException if this list is empty.
148	>	* @return the first element from this list
149	>	* @throws NoSuchElementException if this list is empty
150		*/
151		public E removeFirst() {
152	<	return remove(header.next);
152	>	return remove(header.next);
153		}
154
155		/**
156		* Removes and returns the last element from this list.
157		*
158	<	* @return the last element from this list.
159	<	* @throws    NoSuchElementException if this list is empty.
158	>	* @return the last element from this list
159	>	* @throws NoSuchElementException if this list is empty
160		*/
161		public E removeLast() {
162	<	return remove(header.previous);
162	>	return remove(header.previous);
163		}
164
165		/**
166	<	* Inserts the given element at the beginning of this list.
166	>	* Inserts the specified element at the beginning of this list.
167		*
168	<	* @param o the element to be inserted at the beginning of this list.
168	>	* @param e the element to add
169		*/
170	<	public void addFirst(E o) {
171	<	addBefore(o, header.next);
170	>	public void addFirst(E e) {
171	>	addBefore(e, header.next);
172		}
173
174		/**
175	<	* Appends the given element to the end of this list.  (Identical in
176	<	* function to the <tt>add</tt> method; included only for consistency.)
175	>	* Appends the specified element to the end of this list.
176	>	*
177	>	* <p>This method is equivalent to {@link #add}.
178		*
179	<	* @param o the element to be inserted at the end of this list.
179	>	* @param e the element to add
180		*/
181	<	public void addLast(E o) {
182	<	addBefore(o, header);
181	>	public void addLast(E e) {
182	>	addBefore(e, header);
183		}
184
185		/**
186		* Returns <tt>true</tt> if this list contains the specified element.
187		* More formally, returns <tt>true</tt> if and only if this list contains
188	<	* at least one element <tt>e</tt> such that <tt>(o==null ? e==null
189	<	* : o.equals(e))</tt>.
188	>	* at least one element <tt>e</tt> such that
189	>	* <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>.
190		*
191	<	* @param o element whose presence in this list is to be tested.
192	<	* @return <tt>true</tt> if this list contains the specified element.
191	>	* @param o element whose presence in this list is to be tested
192	>	* @return <tt>true</tt> if this list contains the specified element
193		*/
194		public boolean contains(Object o) {
195		return indexOf(o) != -1;
#	Line 178 | Line 198 | public class LinkedList<E>
198		/**
199		* Returns the number of elements in this list.
200		*
201	<	* @return the number of elements in this list.
201	>	* @return the number of elements in this list
202		*/
203		public int size() {
204	<	return size;
204	>	return size;
205		}
206
207		/**
208		* Appends the specified element to the end of this list.
209		*
210	<	* @param o element to be appended to this list.
211	<	* @return <tt>true</tt> (as per the general contract of
212	<	* <tt>Collection.add</tt>).
210	>	* <p>This method is equivalent to {@link #addLast}.
211	>	*
212	>	* @param e element to be appended to this list
213	>	* @return <tt>true</tt> (as specified by {@link Collection#add})
214		*/
215	<	public boolean add(E o) {
216	<	addBefore(o, header);
215	>	public boolean add(E e) {
216	>	addBefore(e, header);
217		return true;
218		}
219
220		/**
221	<	* Removes the first occurrence of the specified element in this list.  If
222	<	* the list does not contain the element, it is unchanged.  More formally,
223	<	* removes the element with the lowest index <tt>i</tt> such that
224	<	* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt> (if such an
225	<	* element exists).
221	>	* Removes the first occurrence of the specified element from this list,
222	>	* if it is present.  If this list does not contain the element, it is
223	>	* unchanged.  More formally, removes the element with the lowest index
224	>	* <tt>i</tt> such that
225	>	* <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>
226	>	* (if such an element exists).  Returns <tt>true</tt> if this list
227	>	* contained the specified element (or equivalently, if this list
228	>	* changed as a result of the call).
229		*
230	<	* @param o element to be removed from this list, if present.
231	<	* @return <tt>true</tt> if the list contained the specified element.
230	>	* @param o element to be removed from this list, if present
231	>	* @return <tt>true</tt> if this list contained the specified element
232		*/
233		public boolean remove(Object o) {
234		if (o==null) {
#	Line 230 | Line 254 | public class LinkedList<E>
254		* this list, in the order that they are returned by the specified
255		* collection's iterator.  The behavior of this operation is undefined if
256		* the specified collection is modified while the operation is in
257	<	* progress.  (This implies that the behavior of this call is undefined if
258	<	* the specified Collection is this list, and this list is nonempty.)
257	>	* progress.  (Note that this will occur if the specified collection is
258	>	* this list, and it's nonempty.)
259		*
260	<	* @param c the elements to be inserted into this list.
261	<	* @return <tt>true</tt> if this list changed as a result of the call.
262	<	* @throws NullPointerException if the specified collection is null.
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 NullPointerException if the specified collection is null
263		*/
264		public boolean addAll(Collection<? extends E> c) {
265		return addAll(size, c);
#	Line 249 | Line 273 | public class LinkedList<E>
273		* in the list in the order that they are returned by the
274		* specified collection's iterator.
275		*
276	<	* @param index index at which to insert first element
277	<	*              from the specified collection.
278	<	* @param c elements to be inserted into this list.
279	<	* @return <tt>true</tt> if this list changed as a result of the call.
280	<	* @throws IndexOutOfBoundsException if the index is out of range
281	<	*         (<tt>index &lt; 0 || index &gt; size()</tt>).
258	<	* @throws NullPointerException if the specified collection is null.
276	>	* @param index index at which to insert the first element
277	>	*              from the specified collection
278	>	* @param c collection containing elements to be added to this list
279	>	* @return <tt>true</tt> if this list changed as a result of the call
280	>	* @throws IndexOutOfBoundsException {@inheritDoc}
281	>	* @throws NullPointerException if the specified collection is null
282		*/
283		public boolean addAll(int index, Collection<? extends E> c) {
284		if (index < 0 || index > size)
#	Line 265 | Line 288 | public class LinkedList<E>
288		int numNew = a.length;
289		if (numNew==0)
290		return false;
291	<	modCount++;
291	>	modCount++;
292
293		Entry<E> successor = (index==size ? header : entry(index));
294		Entry<E> predecessor = successor.previous;
295	<	for (int i=0; i<numNew; i++) {
295	>	for (int i=0; i<numNew; i++) {
296		Entry<E> e = new Entry<E>((E)a[i], successor, predecessor);
297		predecessor.next = e;
298		predecessor = e;
#	Line 293 | Line 316 | public class LinkedList<E>
316		}
317		header.next = header.previous = header;
318		size = 0;
319	<	modCount++;
319	>	modCount++;
320		}
321
322
#	Line 302 | Line 325 | public class LinkedList<E>
325		/**
326		* Returns the element at the specified position in this list.
327		*
328	<	* @param index index of element to return.
329	<	* @return the element at the specified position in this list.
330	<	*
308	<	* @throws IndexOutOfBoundsException if the index is out of range
309	<	*         (<tt>index &lt; 0 || index &gt; size()</tt>).
328	>	* @param index index of the element to return
329	>	* @return the element at the specified position in this list
330	>	* @throws IndexOutOfBoundsException {@inheritDoc}
331		*/
332		public E get(int index) {
333		return entry(index).element;
#	Line 316 | Line 337 | public class LinkedList<E>
337		* Replaces the element at the specified position in this list with the
338		* specified element.
339		*
340	<	* @param index index of element to replace.
341	<	* @param element element to be stored at the specified position.
342	<	* @return the element previously at the specified position.
343	<	* @throws IndexOutOfBoundsException if the index is out of range
323	<	*         (<tt>index &lt; 0 || index &gt; size()</tt>).
340	>	* @param index index of the element to replace
341	>	* @param element element to be stored at the specified position
342	>	* @return the element previously at the specified position
343	>	* @throws IndexOutOfBoundsException {@inheritDoc}
344		*/
345		public E set(int index, E element) {
346		Entry<E> e = entry(index);
#	Line 334 | Line 354 | public class LinkedList<E>
354		* Shifts the element currently at that position (if any) and any
355		* subsequent elements to the right (adds one to their indices).
356		*
357	<	* @param index index at which the specified element is to be inserted.
358	<	* @param element element to be inserted.
359	<	*
340	<	* @throws IndexOutOfBoundsException if the index is out of range
341	<	*         (<tt>index &lt; 0 || index &gt; size()</tt>).
357	>	* @param index index at which the specified element is to be inserted
358	>	* @param element element to be inserted
359	>	* @throws IndexOutOfBoundsException {@inheritDoc}
360		*/
361		public void add(int index, E element) {
362		addBefore(element, (index==size ? header : entry(index)));
#	Line 349 | Line 367 | public class LinkedList<E>
367		* subsequent elements to the left (subtracts one from their indices).
368		* Returns the element that was removed from the list.
369		*
370	<	* @param index the index of the element to removed.
371	<	* @return the element previously at the specified position.
372	<	*
355	<	* @throws IndexOutOfBoundsException if the index is out of range
356	<	*         (<tt>index &lt; 0 || index &gt; size()</tt>).
370	>	* @param index the index of the element to be removed
371	>	* @return the element previously at the specified position
372	>	* @throws IndexOutOfBoundsException {@inheritDoc}
373		*/
374		public E remove(int index) {
375		return remove(entry(index));
#	Line 381 | Line 397 | public class LinkedList<E>
397		// Search Operations
398
399		/**
400	<	* Returns the index in this list of the first occurrence of the
401	<	* specified element, or -1 if the List does not contain this
402	<	* element.  More formally, returns the lowest index i such that
403	<	* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>, or -1 if
404	<	* there is no such index.
405	<	*
406	<	* @param o element to search for.
407	<	* @return the index in this list of the first occurrence of the
408	<	*         specified element, or -1 if the list does not contain this
393	<	*         element.
400	>	* Returns the index of the first occurrence of the specified element
401	>	* in this list, or -1 if this list does not contain the element.
402	>	* More formally, returns the lowest index <tt>i</tt> such that
403	>	* <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>,
404	>	* or -1 if there is no such index.
405	>	*
406	>	* @param o element to search for
407	>	* @return the index of the first occurrence of the specified element in
408	>	*         this list, or -1 if this list does not contain the element
409		*/
410		public int indexOf(Object o) {
411		int index = 0;
#	Line 411 | Line 426 | public class LinkedList<E>
426		}
427
428		/**
429	<	* Returns the index in this list of the last occurrence of the
430	<	* specified element, or -1 if the list does not contain this
431	<	* element.  More formally, returns the highest index i such that
432	<	* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>, or -1 if
433	<	* there is no such index.
434	<	*
435	<	* @param o element to search for.
436	<	* @return the index in this list of the last occurrence of the
437	<	*         specified element, or -1 if the list does not contain this
423	<	*         element.
429	>	* Returns the index of the last occurrence of the specified element
430	>	* in this list, or -1 if this list does not contain the element.
431	>	* More formally, returns the highest index <tt>i</tt> such that
432	>	* <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>,
433	>	* or -1 if there is no such index.
434	>	*
435	>	* @param o element to search for
436	>	* @return the index of the last occurrence of the specified element in
437	>	*         this list, or -1 if this list does not contain the element
438		*/
439		public int lastIndexOf(Object o) {
440		int index = size;
#	Line 444 | Line 458 | public class LinkedList<E>
458
459		/**
460		* Retrieves, but does not remove, the head (first element) of this list.
461	<	* @return the head of this list, or <tt>null</tt> if this list is empty.
461	>	* @return the head of this list, or <tt>null</tt> if this list is empty
462		* @since 1.5
463		*/
464		public E peek() {
#	Line 455 | Line 469 | public class LinkedList<E>
469
470		/**
471		* Retrieves, but does not remove, the head (first element) of this list.
472	<	* @return the head of this list.
473	<	* @throws NoSuchElementException if this list is empty.
472	>	* @return the head of this list
473	>	* @throws NoSuchElementException if this list is empty
474		* @since 1.5
475		*/
476		public E element() {
#	Line 464 | Line 478 | public class LinkedList<E>
478		}
479
480		/**
481	<	* Retrieves and removes the head (first element) of this list.
482	<	* @return the head of this list, or <tt>null</tt> if this list is empty.
481	>	* Retrieves and removes the head (first element) of this list
482	>	* @return the head of this list, or <tt>null</tt> if this list is empty
483		* @since 1.5
484		*/
485		public E poll() {
#	Line 476 | Line 490 | public class LinkedList<E>
490
491		/**
492		* Retrieves and removes the head (first element) of this list.
493	<	* @return the head of this list.
494	<	* @throws NoSuchElementException if this list is empty.
493	>	*
494	>	* @return the head of this list
495	>	* @throws NoSuchElementException if this list is empty
496		* @since 1.5
497		*/
498		public E remove() {
#	Line 487 | Line 502 | public class LinkedList<E>
502		/**
503		* Adds the specified element as the tail (last element) of this list.
504		*
505	<	* @param o the element to add.
506	<	* @return <tt>true</tt> (as per the general contract of
492	<	* <tt>Queue.offer</tt>)
505	>	* @param e the element to add
506	>	* @return <tt>true</tt> (as specified by {@link Queue#offer})
507		* @since 1.5
508		*/
509	<	public boolean offer(E o) {
510	<	return add(o);
509	>	public boolean offer(E e) {
510	>	return add(e);
511		}
512
513		// Deque operations
#	Line 501 | Line 515 | public class LinkedList<E>
515		* Inserts the specified element at the front of this list.
516		*
517		* @param e the element to insert
518	<	* @return <tt>true</tt> (as per the spec for {@link Deque#offerFirst})
518	>	* @return <tt>true</tt> (as specified by {@link Deque#offerFirst})
519		* @since 1.6
520		*/
521		public boolean offerFirst(E e) {
#	Line 513 | Line 527 | public class LinkedList<E>
527		* Inserts the specified element at the end of this list.
528		*
529		* @param e the element to insert
530	<	* @return <tt>true</tt> (as per the spec for {@link Deque#offerLast})
530	>	* @return <tt>true</tt> (as specified by {@link Deque#offerLast})
531		* @since 1.6
532		*/
533		public boolean offerLast(E e) {
#	Line 523 | Line 537 | public class LinkedList<E>
537
538		/**
539		* Retrieves, but does not remove, the first element of this list,
540	<	* returning <tt>null</tt> if this list is empty.
540	>	* or returns <tt>null</tt> if this list is empty.
541		*
542	<	* @return the first element of this list, or <tt>null</tt> if
543	<	*     this list is empty
542	>	* @return the first element of this list, or <tt>null</tt>
543	>	*         if this list is empty
544		* @since 1.6
545		*/
546		public E peekFirst() {
#	Line 537 | Line 551 | public class LinkedList<E>
551
552		/**
553		* Retrieves, but does not remove, the last element of this list,
554	<	* returning <tt>null</tt> if this list is empty.
554	>	* or returns <tt>null</tt> if this list is empty.
555		*
556	<	* @return the last element of this list, or <tt>null</tt> if this list
557	<	*     is empty
556	>	* @return the last element of this list, or <tt>null</tt>
557	>	*         if this list is empty
558		* @since 1.6
559		*/
560		public E peekLast() {
#	Line 550 | Line 564 | public class LinkedList<E>
564		}
565
566		/**
567	<	* Retrieves and removes the first element of this list, or
568	<	* <tt>null</tt> if this list is empty.
567	>	* Retrieves and removes the first element of this list,
568	>	* or returns <tt>null</tt> if this list is empty.
569		*
570		* @return the first element of this list, or <tt>null</tt> if
571		*     this list is empty
#	Line 564 | Line 578 | public class LinkedList<E>
578		}
579
580		/**
581	<	* Retrieves and removes the last element of this list, or
582	<	* <tt>null</tt> if this list is empty.
581	>	* Retrieves and removes the last element of this list,
582	>	* or returns <tt>null</tt> if this list is empty.
583		*
584		* @return the last element of this list, or <tt>null</tt> if
585		*     this list is empty
#	Line 597 | Line 611 | public class LinkedList<E>
611		* <p>This method is equivalent to {@link #removeFirst()}.
612		*
613		* @return the element at the front of this list (which is the top
614	<	*     of the stack represented by this list)
615	<	* @throws NoSuchElementException if this list is empty.
614	>	*         of the stack represented by this list)
615	>	* @throws NoSuchElementException if this list is empty
616		* @since 1.6
617		*/
618		public E pop() {
#	Line 629 | Line 643 | public class LinkedList<E>
643		*/
644		public boolean removeLastOccurrence(Object o) {
645		if (o==null) {
646	<	for (Entry e = header.previous; e != header; e = e.previous) {
646	>	for (Entry<E> e = header.previous; e != header; e = e.previous) {
647		if (e.element==null) {
648		remove(e);
649		return true;
650		}
651		}
652		} else {
653	<	for (Entry e = header.previous; e != header; e = e.previous) {
653	>	for (Entry<E> e = header.previous; e != header; e = e.previous) {
654		if (o.equals(e.element)) {
655		remove(e);
656		return true;
#	Line 660 | Line 674 | public class LinkedList<E>
674		* than risking arbitrary, non-deterministic behavior at an undetermined
675		* time in the future.
676		*
677	<	* @param index index of first element to be returned from the
678	<	*              list-iterator (by a call to <tt>next</tt>).
677	>	* @param index index of the first element to be returned from the
678	>	*              list-iterator (by a call to <tt>next</tt>)
679		* @return a ListIterator of the elements in this list (in proper
680	<	*         sequence), starting at the specified position in the list.
681	<	* @throws IndexOutOfBoundsException if the index is out of range
668	<	*         (<tt>index &lt; 0 || index &gt; size()</tt>).
680	>	*         sequence), starting at the specified position in the list
681	>	* @throws IndexOutOfBoundsException {@inheritDoc}
682		* @see List#listIterator(int)
683		*/
684		public ListIterator<E> listIterator(int index) {
685	<	return new ListItr(index);
685	>	return new ListItr(index);
686		}
687
688		private class ListItr implements ListIterator<E> {
689	<	private Entry<E> lastReturned = header;
690	<	private Entry<E> next;
691	<	private int nextIndex;
692	<	private int expectedModCount = modCount;
693	<
694	<	ListItr(int index) {
695	<	if (index < 0 || index > size)
696	<	throw new IndexOutOfBoundsException("Index: "+index+
697	<	", Size: "+size);
698	<	if (index < (size >> 1)) {
699	<	next = header.next;
700	<	for (nextIndex=0; nextIndex<index; nextIndex++)
701	<	next = next.next;
702	<	} else {
703	<	next = header;
704	<	for (nextIndex=size; nextIndex>index; nextIndex--)
705	<	next = next.previous;
706	<	}
707	<	}
695	<
696	<	public boolean hasNext() {
697	<	return nextIndex != size;
698	<	}
699	<
700	<	public E next() {
701	<	checkForComodification();
702	<	if (nextIndex == size)
703	<	throw new NoSuchElementException();
704	<
705	<	lastReturned = next;
706	<	next = next.next;
707	<	nextIndex++;
708	<	return lastReturned.element;
709	<	}
710	<
711	<	public boolean hasPrevious() {
712	<	return nextIndex != 0;
713	<	}
714	<
715	<	public E previous() {
716	<	if (nextIndex == 0)
717	<	throw new NoSuchElementException();
718	<
719	<	lastReturned = next = next.previous;
720	<	nextIndex--;
721	<	checkForComodification();
722	<	return lastReturned.element;
723	<	}
724	<
725	<	public int nextIndex() {
726	<	return nextIndex;
727	<	}
728	<
729	<	public int previousIndex() {
730	<	return nextIndex-1;
731	<	}
689	>	private Entry<E> lastReturned = header;
690	>	private Entry<E> next;
691	>	private int nextIndex;
692	>	private int expectedModCount = modCount;
693	>
694	>	ListItr(int index) {
695	>	if (index < 0 || index > size)
696	>	throw new IndexOutOfBoundsException("Index: "+index+
697	>	", Size: "+size);
698	>	if (index < (size >> 1)) {
699	>	next = header.next;
700	>	for (nextIndex=0; nextIndex<index; nextIndex++)
701	>	next = next.next;
702	>	} else {
703	>	next = header;
704	>	for (nextIndex=size; nextIndex>index; nextIndex--)
705	>	next = next.previous;
706	>	}
707	>	}
708
709	<	public void remove() {
709	>	public boolean hasNext() {
710	>	return nextIndex != size;
711	>	}
712	>
713	>	public E next() {
714	>	checkForComodification();
715	>	if (nextIndex == size)
716	>	throw new NoSuchElementException();
717	>
718	>	lastReturned = next;
719	>	next = next.next;
720	>	nextIndex++;
721	>	return lastReturned.element;
722	>	}
723	>
724	>	public boolean hasPrevious() {
725	>	return nextIndex != 0;
726	>	}
727	>
728	>	public E previous() {
729	>	if (nextIndex == 0)
730	>	throw new NoSuchElementException();
731	>
732	>	lastReturned = next = next.previous;
733	>	nextIndex--;
734	>	checkForComodification();
735	>	return lastReturned.element;
736	>	}
737	>
738	>	public int nextIndex() {
739	>	return nextIndex;
740	>	}
741	>
742	>	public int previousIndex() {
743	>	return nextIndex-1;
744	>	}
745	>
746	>	public void remove() {
747		checkForComodification();
748		Entry<E> lastNext = lastReturned.next;
749		try {
#	Line 738 | Line 751 | public class LinkedList<E>
751		} catch (NoSuchElementException e) {
752		throw new IllegalStateException();
753		}
754	<	if (next==lastReturned)
754	>	if (next==lastReturned)
755		next = lastNext;
756		else
757	<	nextIndex--;
758	<	lastReturned = header;
759	<	expectedModCount++;
760	<	}
761	<
762	<	public void set(E o) {
763	<	if (lastReturned == header)
764	<	throw new IllegalStateException();
765	<	checkForComodification();
766	<	lastReturned.element = o;
767	<	}
768	<
769	<	public void add(E o) {
770	<	checkForComodification();
771	<	lastReturned = header;
772	<	addBefore(o, next);
773	<	nextIndex++;
774	<	expectedModCount++;
775	<	}
776	<
777	<	final void checkForComodification() {
778	<	if (modCount != expectedModCount)
779	<	throw new ConcurrentModificationException();
780	<	}
757	>	nextIndex--;
758	>	lastReturned = header;
759	>	expectedModCount++;
760	>	}
761	>
762	>	public void set(E e) {
763	>	if (lastReturned == header)
764	>	throw new IllegalStateException();
765	>	checkForComodification();
766	>	lastReturned.element = e;
767	>	}
768	>
769	>	public void add(E e) {
770	>	checkForComodification();
771	>	lastReturned = header;
772	>	addBefore(e, next);
773	>	nextIndex++;
774	>	expectedModCount++;
775	>	}
776	>
777	>	final void checkForComodification() {
778	>	if (modCount != expectedModCount)
779	>	throw new ConcurrentModificationException();
780	>	}
781		}
782
783		private static class Entry<E> {
784	<	E element;
785	<	Entry<E> next;
786	<	Entry<E> previous;
787	<
788	<	Entry(E element, Entry<E> next, Entry<E> previous) {
789	<	this.element = element;
790	<	this.next = next;
791	<	this.previous = previous;
792	<	}
793	<	}
794	<
795	<	private Entry<E> addBefore(E o, Entry<E> e) {
796	<	Entry<E> newEntry = new Entry<E>(o, e, e.previous);
797	<	newEntry.previous.next = newEntry;
798	<	newEntry.next.previous = newEntry;
799	<	size++;
800	<	modCount++;
801	<	return newEntry;
784	>	E element;
785	>	Entry<E> next;
786	>	Entry<E> previous;
787	>
788	>	Entry(E element, Entry<E> next, Entry<E> previous) {
789	>	this.element = element;
790	>	this.next = next;
791	>	this.previous = previous;
792	>	}
793	>	}
794	>
795	>	private Entry<E> addBefore(E e, Entry<E> entry) {
796	>	Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);
797	>	newEntry.previous.next = newEntry;
798	>	newEntry.next.previous = newEntry;
799	>	size++;
800	>	modCount++;
801	>	return newEntry;
802		}
803
804		private E remove(Entry<E> e) {
805	<	if (e == header)
806	<	throw new NoSuchElementException();
805	>	if (e == header)
806	>	throw new NoSuchElementException();
807
808		E result = e.element;
809	<	e.previous.next = e.next;
810	<	e.next.previous = e.previous;
809	>	e.previous.next = e.next;
810	>	e.next.previous = e.previous;
811		e.next = e.previous = null;
812		e.element = null;
813	<	size--;
814	<	modCount++;
813	>	size--;
814	>	modCount++;
815		return result;
816		}
817
818		/**
819	+	* @since 1.6
820	+	*/
821	+	public Iterator<E> descendingIterator() {
822	+	return new DescendingIterator();
823	+	}
824	+
825	+	/** Adapter to provide descending iterators via ListItr.previous */
826	+	private class DescendingIterator implements Iterator {
827	+	final ListItr itr = new ListItr(size());
828	+	public boolean hasNext() {
829	+	return itr.hasPrevious();
830	+	}
831	+	public E next() {
832	+	return itr.previous();
833	+	}
834	+	public void remove() {
835	+	itr.remove();
836	+	}
837	+	}
838	+
839	+	/**
840		* Returns a shallow copy of this <tt>LinkedList</tt>. (The elements
841		* themselves are not cloned.)
842		*
843	<	* @return a shallow copy of this <tt>LinkedList</tt> instance.
843	>	* @return a shallow copy of this <tt>LinkedList</tt> instance
844		*/
845		public Object clone() {
846		LinkedList<E> clone = null;
847	<	try {
848	<	clone = (LinkedList<E>) super.clone();
849	<	} catch (CloneNotSupportedException e) {
850	<	throw new InternalError();
851	<	}
847	>	try {
848	>	clone = (LinkedList<E>) super.clone();
849	>	} catch (CloneNotSupportedException e) {
850	>	throw new InternalError();
851	>	}
852
853		// Put clone into "virgin" state
854		clone.header = new Entry<E>(null, null, null);
#	Line 831 | Line 865 | public class LinkedList<E>
865
866		/**
867		* Returns an array containing all of the elements in this list
868	<	* in the correct order.
868	>	* in proper sequence (from first to last element).
869	>	*
870	>	* <p>The returned array will be "safe" in that no references to it are
871	>	* maintained by this list.  (In other words, this method must allocate
872	>	* a new array).  The caller is thus free to modify the returned array.
873	>	*
874	>	* <p>This method acts as bridge between array-based and collection-based
875	>	* APIs.
876		*
877		* @return an array containing all of the elements in this list
878	<	*         in the correct order.
878	>	*         in proper sequence
879		*/
880		public Object[] toArray() {
881	<	Object[] result = new Object[size];
881	>	Object[] result = new Object[size];
882		int i = 0;
883		for (Entry<E> e = header.next; e != header; e = e.next)
884		result[i++] = e.element;
885	<	return result;
885	>	return result;
886		}
887
888		/**
889		* Returns an array containing all of the elements in this list in
890	<	* the correct order; the runtime type of the returned array is that of
891	<	* the specified array.  If the list fits in the specified array, it
892	<	* is returned therein.  Otherwise, a new array is allocated with the
893	<	* runtime type of the specified array and the size of this list.<p>
894	<	*
895	<	* If the list fits in the specified array with room to spare
896	<	* (i.e., the array has more elements than the list),
897	<	* the element in the array immediately following the end of the
898	<	* collection is set to null.  This is useful in determining the length
899	<	* of the list <i>only</i> if the caller knows that the list
900	<	* does not contain any null elements.
890	>	* proper sequence (from first to last element); the runtime type of
891	>	* the returned array is that of the specified array.  If the list fits
892	>	* in the specified array, it is returned therein.  Otherwise, a new
893	>	* array is allocated with the runtime type of the specified array and
894	>	* the size of this list.
895	>	*
896	>	* <p>If the list fits in the specified array with room to spare (i.e.,
897	>	* the array has more elements than the list), the element in the array
898	>	* immediately following the end of the list is set to <tt>null</tt>.
899	>	* (This is useful in determining the length of the list <i>only</i> if
900	>	* the caller knows that the list does not contain any null elements.)
901	>	*
902	>	* <p>Like the {@link #toArray()} method, this method acts as bridge between
903	>	* array-based and collection-based APIs.  Further, this method allows
904	>	* precise control over the runtime type of the output array, and may,
905	>	* under certain circumstances, be used to save allocation costs.
906	>	*
907	>	* <p>Suppose <tt>x</tt> is a list known to contain only strings.
908	>	* The following code can be used to dump the list into a newly
909	>	* allocated array of <tt>String</tt>:
910	>	*
911	>	* <pre>
912	>	*     String[] y = x.toArray(new String[0]);</pre>
913	>	*
914	>	* Note that <tt>toArray(new Object[0])</tt> is identical in function to
915	>	* <tt>toArray()</tt>.
916		*
917		* @param a the array into which the elements of the list are to
918	<	*          be stored, if it is big enough; otherwise, a new array of the
919	<	*          same runtime type is allocated for this purpose.
920	<	* @return an array containing the elements of the list.
921	<	* @throws ArrayStoreException if the runtime type of a is not a
922	<	*         supertype of the runtime type of every element in this list.
923	<	* @throws NullPointerException if the specified array is null.
918	>	*          be stored, if it is big enough; otherwise, a new array of the
919	>	*          same runtime type is allocated for this purpose.
920	>	* @return an array containing the elements of the list
921	>	* @throws ArrayStoreException if the runtime type of the specified array
922	>	*         is not a supertype of the runtime type of every element in
923	>	*         this list
924	>	* @throws NullPointerException if the specified array is null
925		*/
926		public <T> T[] toArray(T[] a) {
927		if (a.length < size)
928		a = (T[])java.lang.reflect.Array.newInstance(
929		a.getClass().getComponentType(), size);
930		int i = 0;
931	<	Object[] result = a;
931	>	Object[] result = a;
932		for (Entry<E> e = header.next; e != header; e = e.next)
933		result[i++] = e.element;
934
#	Line 888 | Line 945 | public class LinkedList<E>
945		* is, serialize it).
946		*
947		* @serialData The size of the list (the number of elements it
948	<	*             contains) is emitted (int), followed by all of its
949	<	* elements (each an Object) in the proper order.
948	>	*             contains) is emitted (int), followed by all of its
949	>	*             elements (each an Object) in the proper order.
950		*/
951		private void writeObject(java.io.ObjectOutputStream s)
952		throws java.io.IOException {
953	<	// Write out any hidden serialization magic
954	<	s.defaultWriteObject();
953	>	// Write out any hidden serialization magic
954	>	s.defaultWriteObject();
955
956		// Write out size
957		s.writeInt(size);
958
959	<	// Write out all elements in the proper order.
959	>	// Write out all elements in the proper order.
960		for (Entry e = header.next; e != header; e = e.next)
961		s.writeObject(e.element);
962		}
#	Line 910 | Line 967 | public class LinkedList<E>
967		*/
968		private void readObject(java.io.ObjectInputStream s)
969		throws java.io.IOException, ClassNotFoundException {
970	<	// Read in any hidden serialization magic
971	<	s.defaultReadObject();
970	>	// Read in any hidden serialization magic
971	>	s.defaultReadObject();
972
973		// Read in size
974		int size = s.readInt();
#	Line 920 | Line 977 | public class LinkedList<E>
977		header = new Entry<E>(null, null, null);
978		header.next = header.previous = header;
979
980	<	// Read in all elements in the proper order.
981	<	for (int i=0; i<size; i++)
980	>	// Read in all elements in the proper order.
981	>	for (int i=0; i<size; i++)
982		addBefore((E)s.readObject(), header);
983		}
984		}

Diff Legend

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