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.26 by jsr166, Mon May 2 08:35:49 2005 UTC vs.
Revision 1.49 by jsr166, Sun May 18 23:59:57 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
67	<	* @see     Vector
68	<	* @see     Collections#synchronizedList(List)
84	>	* @see     List
85	>	* @see     ArrayList
86	>	* @see     Vector
87		* @since 1.2
88		* @param <E> the type of elements held in this collection
89		*/
#	Line 89 | Line 107 | public class LinkedList<E>
107		* collection, in the order they are returned by the collection's
108		* iterator.
109		*
110	<	* @param  c the collection whose elements are to be placed into this list.
111	<	* @throws NullPointerException if the specified collection is null.
110	>	* @param  c the collection whose elements are to be placed into this list
111	>	* @throws NullPointerException if the specified collection is null
112		*/
113	<	public LinkedList(Collection<? extends E> c) {
114	<	this();
115	<	addAll(c);
116	<	}
113	>	public LinkedList(Collection<? extends E> c) {
114	>	this();
115	>	addAll(c);
116	>	}
117
118		/**
119		* Returns the first element in this list.
120		*
121	<	* @return the first element in this list.
122	<	* @throws    NoSuchElementException if this list is empty.
121	>	* @return the first element in this list
122	>	* @throws NoSuchElementException if this list is empty
123		*/
124		public E getFirst() {
125	<	if (size==0)
126	<	throw new NoSuchElementException();
125	>	if (size==0)
126	>	throw new NoSuchElementException();
127
128	<	return header.next.element;
128	>	return header.next.element;
129		}
130
131		/**
132		* Returns the last element in this list.
133		*
134	<	* @return the last element in this list.
135	<	* @throws    NoSuchElementException if this list is empty.
134	>	* @return the last element in this list
135	>	* @throws NoSuchElementException if this list is empty
136		*/
137		public E getLast()  {
138	<	if (size==0)
139	<	throw new NoSuchElementException();
138	>	if (size==0)
139	>	throw new NoSuchElementException();
140
141	<	return header.previous.element;
141	>	return header.previous.element;
142		}
143
144		/**
145		* Removes and returns the first element from this list.
146		*
147	<	* @return the first element from this list.
148	<	* @throws    NoSuchElementException if this list is empty.
147	>	* @return the first element from this list
148	>	* @throws NoSuchElementException if this list is empty
149		*/
150		public E removeFirst() {
151	<	return remove(header.next);
151	>	return remove(header.next);
152		}
153
154		/**
155		* Removes and returns the last element from this list.
156		*
157	<	* @return the last element from this list.
158	<	* @throws    NoSuchElementException if this list is empty.
157	>	* @return the last element from this list
158	>	* @throws NoSuchElementException if this list is empty
159		*/
160		public E removeLast() {
161	<	return remove(header.previous);
161	>	return remove(header.previous);
162		}
163
164		/**
165	<	* Inserts the given element at the beginning of this list.
165	>	* Inserts the specified element at the beginning of this list.
166		*
167	<	* @param e the element to be inserted at the beginning of this list.
167	>	* @param e the element to add
168		*/
169		public void addFirst(E e) {
170	<	addBefore(e, header.next);
170	>	addBefore(e, header.next);
171		}
172
173		/**
174	<	* Appends the given element to the end of this list.  (Identical in
175	<	* function to the <tt>add</tt> method; included only for consistency.)
174	>	* Appends the specified element to the end of this list.
175	>	*
176	>	* <p>This method is equivalent to {@link #add}.
177		*
178	<	* @param e the element to be inserted at the end of this list.
178	>	* @param e the element to add
179		*/
180		public void addLast(E e) {
181	<	addBefore(e, header);
181	>	addBefore(e, header);
182		}
183
184		/**
185		* Returns <tt>true</tt> if this list contains the specified element.
186		* More formally, returns <tt>true</tt> if and only if this list contains
187	<	* at least one element <tt>e</tt> such that <tt>(o==null ? e==null
188	<	* : o.equals(e))</tt>.
187	>	* at least one element <tt>e</tt> such that
188	>	* <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>.
189		*
190	<	* @param o element whose presence in this list is to be tested.
191	<	* @return <tt>true</tt> if this list contains the specified element.
190	>	* @param o element whose presence in this list is to be tested
191	>	* @return <tt>true</tt> if this list contains the specified element
192		*/
193		public boolean contains(Object o) {
194		return indexOf(o) != -1;
#	Line 178 | Line 197 | public class LinkedList<E>
197		/**
198		* Returns the number of elements in this list.
199		*
200	<	* @return the number of elements in this list.
200	>	* @return the number of elements in this list
201		*/
202		public int size() {
203	<	return size;
203	>	return size;
204		}
205
206		/**
207		* Appends the specified element to the end of this list.
208		*
209	<	* @param e element to be appended to this list.
210	<	* @return <tt>true</tt> (as per the general contract of
211	<	* <tt>Collection.add</tt>).
209	>	* <p>This method is equivalent to {@link #addLast}.
210	>	*
211	>	* @param e element to be appended to this list
212	>	* @return <tt>true</tt> (as specified by {@link Collection#add})
213		*/
214		public boolean add(E e) {
215	<	addBefore(e, header);
215	>	addBefore(e, header);
216		return true;
217		}
218
219		/**
220	<	* Removes the first occurrence of the specified element in this list.  If
221	<	* the list does not contain the element, it is unchanged.  More formally,
222	<	* removes the element with the lowest index <tt>i</tt> such that
223	<	* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt> (if such an
224	<	* element exists).
220	>	* Removes the first occurrence of the specified element from this list,
221	>	* if it is present.  If this list does not contain the element, it is
222	>	* unchanged.  More formally, removes the element with the lowest index
223	>	* <tt>i</tt> such that
224	>	* <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>
225	>	* (if such an element exists).  Returns <tt>true</tt> if this list
226	>	* contained the specified element (or equivalently, if this list
227	>	* changed as a result of the call).
228		*
229	<	* @param o element to be removed from this list, if present.
230	<	* @return <tt>true</tt> if the list contained the specified element.
229	>	* @param o element to be removed from this list, if present
230	>	* @return <tt>true</tt> if this list contained the specified element
231		*/
232		public boolean remove(Object o) {
233		if (o==null) {
#	Line 230 | Line 253 | public class LinkedList<E>
253		* this list, in the order that they are returned by the specified
254		* collection's iterator.  The behavior of this operation is undefined if
255		* the specified collection is modified while the operation is in
256	<	* progress.  (This implies that the behavior of this call is undefined if
257	<	* the specified Collection is this list, and this list is nonempty.)
256	>	* progress.  (Note that this will occur if the specified collection is
257	>	* this list, and it's nonempty.)
258		*
259	<	* @param c the elements to be inserted into this list.
260	<	* @return <tt>true</tt> if this list changed as a result of the call.
261	<	* @throws NullPointerException if the specified collection is null.
259	>	* @param c collection containing elements to be added to this list
260	>	* @return <tt>true</tt> if this list changed as a result of the call
261	>	* @throws NullPointerException if the specified collection is null
262		*/
263		public boolean addAll(Collection<? extends E> c) {
264		return addAll(size, c);
#	Line 249 | Line 272 | public class LinkedList<E>
272		* in the list in the order that they are returned by the
273		* specified collection's iterator.
274		*
275	<	* @param index index at which to insert first element
276	<	*              from the specified collection.
277	<	* @param c elements to be inserted into this list.
278	<	* @return <tt>true</tt> if this list changed as a result of the call.
279	<	* @throws IndexOutOfBoundsException if the index is out of range
280	<	*         (<tt>index &lt; 0 || index &gt; size()</tt>).
258	<	* @throws NullPointerException if the specified collection is null.
275	>	* @param index index at which to insert the first element
276	>	*              from the specified collection
277	>	* @param c collection containing elements to be added to this list
278	>	* @return <tt>true</tt> if this list changed as a result of the call
279	>	* @throws IndexOutOfBoundsException {@inheritDoc}
280	>	* @throws NullPointerException if the specified collection is null
281		*/
282		public boolean addAll(int index, Collection<? extends E> c) {
283		if (index < 0 || index > size)
#	Line 265 | Line 287 | public class LinkedList<E>
287		int numNew = a.length;
288		if (numNew==0)
289		return false;
290	<	modCount++;
290	>	modCount++;
291
292		Entry<E> successor = (index==size ? header : entry(index));
293		Entry<E> predecessor = successor.previous;
294	<	for (int i=0; i<numNew; i++) {
294	>	for (int i=0; i<numNew; i++) {
295		Entry<E> e = new Entry<E>((E)a[i], successor, predecessor);
296		predecessor.next = e;
297		predecessor = e;
#	Line 293 | Line 315 | public class LinkedList<E>
315		}
316		header.next = header.previous = header;
317		size = 0;
318	<	modCount++;
318	>	modCount++;
319		}
320
321
#	Line 302 | Line 324 | public class LinkedList<E>
324		/**
325		* Returns the element at the specified position in this list.
326		*
327	<	* @param index index of element to return.
328	<	* @return the element at the specified position in this list.
329	<	*
308	<	* @throws IndexOutOfBoundsException if the index is out of range
309	<	*         (<tt>index &lt; 0 || index &gt; size()</tt>).
327	>	* @param index index of the element to return
328	>	* @return the element at the specified position in this list
329	>	* @throws IndexOutOfBoundsException {@inheritDoc}
330		*/
331		public E get(int index) {
332		return entry(index).element;
#	Line 316 | Line 336 | public class LinkedList<E>
336		* Replaces the element at the specified position in this list with the
337		* specified element.
338		*
339	<	* @param index index of element to replace.
340	<	* @param element element to be stored at the specified position.
341	<	* @return the element previously at the specified position.
342	<	* @throws IndexOutOfBoundsException if the index is out of range
323	<	*         (<tt>index &lt; 0 || index &gt; size()</tt>).
339	>	* @param index index of the element to replace
340	>	* @param element element to be stored at the specified position
341	>	* @return the element previously at the specified position
342	>	* @throws IndexOutOfBoundsException {@inheritDoc}
343		*/
344		public E set(int index, E element) {
345		Entry<E> e = entry(index);
#	Line 334 | Line 353 | public class LinkedList<E>
353		* Shifts the element currently at that position (if any) and any
354		* subsequent elements to the right (adds one to their indices).
355		*
356	<	* @param index index at which the specified element is to be inserted.
357	<	* @param element element to be inserted.
358	<	*
340	<	* @throws IndexOutOfBoundsException if the index is out of range
341	<	*         (<tt>index &lt; 0 || index &gt; size()</tt>).
356	>	* @param index index at which the specified element is to be inserted
357	>	* @param element element to be inserted
358	>	* @throws IndexOutOfBoundsException {@inheritDoc}
359		*/
360		public void add(int index, E element) {
361		addBefore(element, (index==size ? header : entry(index)));
#	Line 349 | Line 366 | public class LinkedList<E>
366		* subsequent elements to the left (subtracts one from their indices).
367		* Returns the element that was removed from the list.
368		*
369	<	* @param index the index of the element to removed.
370	<	* @return the element previously at the specified position.
371	<	*
355	<	* @throws IndexOutOfBoundsException if the index is out of range
356	<	*         (<tt>index &lt; 0 || index &gt; size()</tt>).
369	>	* @param index the index of the element to be removed
370	>	* @return the element previously at the specified position
371	>	* @throws IndexOutOfBoundsException {@inheritDoc}
372		*/
373		public E remove(int index) {
374		return remove(entry(index));
#	Line 381 | Line 396 | public class LinkedList<E>
396		// Search Operations
397
398		/**
399	<	* Returns the index in this list of the first occurrence of the
400	<	* specified element, or -1 if the List does not contain this
401	<	* element.  More formally, returns the lowest index i such that
402	<	* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>, or -1 if
403	<	* there is no such index.
404	<	*
405	<	* @param o element to search for.
406	<	* @return the index in this list of the first occurrence of the
407	<	*         specified element, or -1 if the list does not contain this
393	<	*         element.
399	>	* Returns the index of the first occurrence of the specified element
400	>	* in this list, or -1 if this list does not contain the element.
401	>	* More formally, returns the lowest index <tt>i</tt> such that
402	>	* <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>,
403	>	* or -1 if there is no such index.
404	>	*
405	>	* @param o element to search for
406	>	* @return the index of the first occurrence of the specified element in
407	>	*         this list, or -1 if this list does not contain the element
408		*/
409		public int indexOf(Object o) {
410		int index = 0;
#	Line 411 | Line 425 | public class LinkedList<E>
425		}
426
427		/**
428	<	* Returns the index in this list of the last occurrence of the
429	<	* specified element, or -1 if the list does not contain this
430	<	* element.  More formally, returns the highest index i such that
431	<	* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>, or -1 if
432	<	* there is no such index.
433	<	*
434	<	* @param o element to search for.
435	<	* @return the index in this list of the last occurrence of the
436	<	*         specified element, or -1 if the list does not contain this
423	<	*         element.
428	>	* Returns the index of the last occurrence of the specified element
429	>	* in this list, or -1 if this list does not contain the element.
430	>	* More formally, returns the highest index <tt>i</tt> such that
431	>	* <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>,
432	>	* or -1 if there is no such index.
433	>	*
434	>	* @param o element to search for
435	>	* @return the index of the last occurrence of the specified element in
436	>	*         this list, or -1 if this list does not contain the element
437		*/
438		public int lastIndexOf(Object o) {
439		int index = size;
#	Line 444 | Line 457 | public class LinkedList<E>
457
458		/**
459		* Retrieves, but does not remove, the head (first element) of this list.
460	<	* @return the head of this list, or <tt>null</tt> if this list is empty.
460	>	* @return the head of this list, or <tt>null</tt> if this list is empty
461		* @since 1.5
462		*/
463		public E peek() {
#	Line 455 | Line 468 | public class LinkedList<E>
468
469		/**
470		* Retrieves, but does not remove, the head (first element) of this list.
471	<	* @return the head of this list.
472	<	* @throws NoSuchElementException if this list is empty.
471	>	* @return the head of this list
472	>	* @throws NoSuchElementException if this list is empty
473		* @since 1.5
474		*/
475		public E element() {
#	Line 464 | Line 477 | public class LinkedList<E>
477		}
478
479		/**
480	<	* Retrieves and removes the head (first element) of this list.
481	<	* @return the head of this list, or <tt>null</tt> if this list is empty.
480	>	* Retrieves and removes the head (first element) of this list
481	>	* @return the head of this list, or <tt>null</tt> if this list is empty
482		* @since 1.5
483		*/
484		public E poll() {
#	Line 476 | Line 489 | public class LinkedList<E>
489
490		/**
491		* Retrieves and removes the head (first element) of this list.
492	<	* @return the head of this list.
493	<	* @throws NoSuchElementException if this list is empty.
492	>	*
493	>	* @return the head of this list
494	>	* @throws NoSuchElementException if this list is empty
495		* @since 1.5
496		*/
497		public E remove() {
#	Line 487 | Line 501 | public class LinkedList<E>
501		/**
502		* Adds the specified element as the tail (last element) of this list.
503		*
504	<	* @param e the element to add.
505	<	* @return <tt>true</tt> (as per the general contract of
492	<	* <tt>Queue.offer</tt>)
504	>	* @param e the element to add
505	>	* @return <tt>true</tt> (as specified by {@link Queue#offer})
506		* @since 1.5
507		*/
508		public boolean offer(E e) {
#	Line 501 | Line 514 | public class LinkedList<E>
514		* Inserts the specified element at the front of this list.
515		*
516		* @param e the element to insert
517	<	* @return <tt>true</tt> (as per the spec for {@link Deque#offerFirst})
517	>	* @return <tt>true</tt> (as specified by {@link Deque#offerFirst})
518		* @since 1.6
519		*/
520		public boolean offerFirst(E e) {
#	Line 513 | Line 526 | public class LinkedList<E>
526		* Inserts the specified element at the end of this list.
527		*
528		* @param e the element to insert
529	<	* @return <tt>true</tt> (as per the spec for {@link Deque#offerLast})
529	>	* @return <tt>true</tt> (as specified by {@link Deque#offerLast})
530		* @since 1.6
531		*/
532		public boolean offerLast(E e) {
#	Line 523 | Line 536 | public class LinkedList<E>
536
537		/**
538		* Retrieves, but does not remove, the first element of this list,
539	<	* returning <tt>null</tt> if this list is empty.
539	>	* or returns <tt>null</tt> if this list is empty.
540		*
541	<	* @return the first element of this list, or <tt>null</tt> if
542	<	*     this list is empty
541	>	* @return the first element of this list, or <tt>null</tt>
542	>	*         if this list is empty
543		* @since 1.6
544		*/
545		public E peekFirst() {
#	Line 537 | Line 550 | public class LinkedList<E>
550
551		/**
552		* Retrieves, but does not remove, the last element of this list,
553	<	* returning <tt>null</tt> if this list is empty.
553	>	* or returns <tt>null</tt> if this list is empty.
554		*
555	<	* @return the last element of this list, or <tt>null</tt> if this list
556	<	*     is empty
555	>	* @return the last element of this list, or <tt>null</tt>
556	>	*         if this list is empty
557		* @since 1.6
558		*/
559		public E peekLast() {
#	Line 550 | Line 563 | public class LinkedList<E>
563		}
564
565		/**
566	<	* Retrieves and removes the first element of this list, or
567	<	* <tt>null</tt> if this list is empty.
566	>	* Retrieves and removes the first element of this list,
567	>	* or returns <tt>null</tt> if this list is empty.
568		*
569		* @return the first element of this list, or <tt>null</tt> if
570		*     this list is empty
#	Line 564 | Line 577 | public class LinkedList<E>
577		}
578
579		/**
580	<	* Retrieves and removes the last element of this list, or
581	<	* <tt>null</tt> if this list is empty.
580	>	* Retrieves and removes the last element of this list,
581	>	* or returns <tt>null</tt> if this list is empty.
582		*
583		* @return the last element of this list, or <tt>null</tt> if
584		*     this list is empty
#	Line 597 | Line 610 | public class LinkedList<E>
610		* <p>This method is equivalent to {@link #removeFirst()}.
611		*
612		* @return the element at the front of this list (which is the top
613	<	*     of the stack represented by this list)
614	<	* @throws NoSuchElementException if this list is empty.
613	>	*         of the stack represented by this list)
614	>	* @throws NoSuchElementException if this list is empty
615		* @since 1.6
616		*/
617		public E pop() {
#	Line 629 | Line 642 | public class LinkedList<E>
642		*/
643		public boolean removeLastOccurrence(Object o) {
644		if (o==null) {
645	<	for (Entry e = header.previous; e != header; e = e.previous) {
645	>	for (Entry<E> e = header.previous; e != header; e = e.previous) {
646		if (e.element==null) {
647		remove(e);
648		return true;
649		}
650		}
651		} else {
652	<	for (Entry e = header.previous; e != header; e = e.previous) {
652	>	for (Entry<E> e = header.previous; e != header; e = e.previous) {
653		if (o.equals(e.element)) {
654		remove(e);
655		return true;
#	Line 660 | Line 673 | public class LinkedList<E>
673		* than risking arbitrary, non-deterministic behavior at an undetermined
674		* time in the future.
675		*
676	<	* @param index index of first element to be returned from the
677	<	*              list-iterator (by a call to <tt>next</tt>).
676	>	* @param index index of the first element to be returned from the
677	>	*              list-iterator (by a call to <tt>next</tt>)
678		* @return a ListIterator of the elements in this list (in proper
679	<	*         sequence), starting at the specified position in the list.
680	<	* @throws IndexOutOfBoundsException if the index is out of range
668	<	*         (<tt>index &lt; 0 || index &gt; size()</tt>).
679	>	*         sequence), starting at the specified position in the list
680	>	* @throws IndexOutOfBoundsException {@inheritDoc}
681		* @see List#listIterator(int)
682		*/
683		public ListIterator<E> listIterator(int index) {
684	<	return new ListItr(index);
684	>	return new ListItr(index);
685		}
686
687		private class ListItr implements ListIterator<E> {
688	<	private Entry<E> lastReturned = header;
689	<	private Entry<E> next;
690	<	private int nextIndex;
691	<	private int expectedModCount = modCount;
692	<
693	<	ListItr(int index) {
694	<	if (index < 0 || index > size)
695	<	throw new IndexOutOfBoundsException("Index: "+index+
696	<	", Size: "+size);
697	<	if (index < (size >> 1)) {
698	<	next = header.next;
699	<	for (nextIndex=0; nextIndex<index; nextIndex++)
700	<	next = next.next;
701	<	} else {
702	<	next = header;
703	<	for (nextIndex=size; nextIndex>index; nextIndex--)
704	<	next = next.previous;
705	<	}
706	<	}
707	<
708	<	public boolean hasNext() {
709	<	return nextIndex != size;
710	<	}
711	<
712	<	public E next() {
713	<	checkForComodification();
714	<	if (nextIndex == size)
715	<	throw new NoSuchElementException();
716	<
717	<	lastReturned = next;
718	<	next = next.next;
719	<	nextIndex++;
720	<	return lastReturned.element;
721	<	}
722	<
723	<	public boolean hasPrevious() {
724	<	return nextIndex != 0;
725	<	}
726	<
727	<	public E previous() {
728	<	if (nextIndex == 0)
729	<	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	<	}
688	>	private Entry<E> lastReturned = header;
689	>	private Entry<E> next;
690	>	private int nextIndex;
691	>	private int expectedModCount = modCount;
692	>
693	>	ListItr(int index) {
694	>	if (index < 0 || index > size)
695	>	throw new IndexOutOfBoundsException("Index: "+index+
696	>	", Size: "+size);
697	>	if (index < (size >> 1)) {
698	>	next = header.next;
699	>	for (nextIndex=0; nextIndex<index; nextIndex++)
700	>	next = next.next;
701	>	} else {
702	>	next = header;
703	>	for (nextIndex=size; nextIndex>index; nextIndex--)
704	>	next = next.previous;
705	>	}
706	>	}
707	>
708	>	public boolean hasNext() {
709	>	return nextIndex != size;
710	>	}
711	>
712	>	public E next() {
713	>	checkForComodification();
714	>	if (nextIndex == size)
715	>	throw new NoSuchElementException();
716	>
717	>	lastReturned = next;
718	>	next = next.next;
719	>	nextIndex++;
720	>	return lastReturned.element;
721	>	}
722	>
723	>	public boolean hasPrevious() {
724	>	return nextIndex != 0;
725	>	}
726	>
727	>	public E previous() {
728	>	if (nextIndex == 0)
729	>	throw new NoSuchElementException();
730
731	<	public void remove() {
731	>	lastReturned = next = next.previous;
732	>	nextIndex--;
733	>	checkForComodification();
734	>	return lastReturned.element;
735	>	}
736	>
737	>	public int nextIndex() {
738	>	return nextIndex;
739	>	}
740	>
741	>	public int previousIndex() {
742	>	return nextIndex-1;
743	>	}
744	>
745	>	public void remove() {
746		checkForComodification();
747		Entry<E> lastNext = lastReturned.next;
748		try {
#	Line 738 | Line 750 | public class LinkedList<E>
750		} catch (NoSuchElementException e) {
751		throw new IllegalStateException();
752		}
753	<	if (next==lastReturned)
753	>	if (next==lastReturned)
754		next = lastNext;
755		else
756	<	nextIndex--;
757	<	lastReturned = header;
758	<	expectedModCount++;
759	<	}
760	<
761	<	public void set(E e) {
762	<	if (lastReturned == header)
763	<	throw new IllegalStateException();
764	<	checkForComodification();
765	<	lastReturned.element = e;
766	<	}
767	<
768	<	public void add(E e) {
769	<	checkForComodification();
770	<	lastReturned = header;
771	<	addBefore(e, next);
772	<	nextIndex++;
773	<	expectedModCount++;
774	<	}
775	<
776	<	final void checkForComodification() {
777	<	if (modCount != expectedModCount)
778	<	throw new ConcurrentModificationException();
779	<	}
756	>	nextIndex--;
757	>	lastReturned = header;
758	>	expectedModCount++;
759	>	}
760	>
761	>	public void set(E e) {
762	>	if (lastReturned == header)
763	>	throw new IllegalStateException();
764	>	checkForComodification();
765	>	lastReturned.element = e;
766	>	}
767	>
768	>	public void add(E e) {
769	>	checkForComodification();
770	>	lastReturned = header;
771	>	addBefore(e, next);
772	>	nextIndex++;
773	>	expectedModCount++;
774	>	}
775	>
776	>	final void checkForComodification() {
777	>	if (modCount != expectedModCount)
778	>	throw new ConcurrentModificationException();
779	>	}
780		}
781
782		private static class Entry<E> {
783	<	E element;
784	<	Entry<E> next;
785	<	Entry<E> previous;
786	<
787	<	Entry(E element, Entry<E> next, Entry<E> previous) {
788	<	this.element = element;
789	<	this.next = next;
790	<	this.previous = previous;
791	<	}
783	>	E element;
784	>	Entry<E> next;
785	>	Entry<E> previous;
786	>
787	>	Entry(E element, Entry<E> next, Entry<E> previous) {
788	>	this.element = element;
789	>	this.next = next;
790	>	this.previous = previous;
791	>	}
792		}
793
794		private Entry<E> addBefore(E e, Entry<E> entry) {
795	<	Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);
796	<	newEntry.previous.next = newEntry;
797	<	newEntry.next.previous = newEntry;
798	<	size++;
799	<	modCount++;
800	<	return newEntry;
795	>	Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);
796	>	newEntry.previous.next = newEntry;
797	>	newEntry.next.previous = newEntry;
798	>	size++;
799	>	modCount++;
800	>	return newEntry;
801		}
802
803		private E remove(Entry<E> e) {
804	<	if (e == header)
805	<	throw new NoSuchElementException();
804	>	if (e == header)
805	>	throw new NoSuchElementException();
806
807		E result = e.element;
808	<	e.previous.next = e.next;
809	<	e.next.previous = e.previous;
808	>	e.previous.next = e.next;
809	>	e.next.previous = e.previous;
810		e.next = e.previous = null;
811		e.element = null;
812	<	size--;
813	<	modCount++;
812	>	size--;
813	>	modCount++;
814		return result;
815		}
816
817		/**
818	+	* @since 1.6
819	+	*/
820	+	public Iterator<E> descendingIterator() {
821	+	return new DescendingIterator();
822	+	}
823	+
824	+	/** Adapter to provide descending iterators via ListItr.previous */
825	+	private class DescendingIterator implements Iterator {
826	+	final ListItr itr = new ListItr(size());
827	+	public boolean hasNext() {
828	+	return itr.hasPrevious();
829	+	}
830	+	public E next() {
831	+	return itr.previous();
832	+	}
833	+	public void remove() {
834	+	itr.remove();
835	+	}
836	+	}
837	+
838	+	/**
839		* Returns a shallow copy of this <tt>LinkedList</tt>. (The elements
840		* themselves are not cloned.)
841		*
842	<	* @return a shallow copy of this <tt>LinkedList</tt> instance.
842	>	* @return a shallow copy of this <tt>LinkedList</tt> instance
843		*/
844		public Object clone() {
845		LinkedList<E> clone = null;
846	<	try {
847	<	clone = (LinkedList<E>) super.clone();
848	<	} catch (CloneNotSupportedException e) {
849	<	throw new InternalError();
850	<	}
846	>	try {
847	>	clone = (LinkedList<E>) super.clone();
848	>	} catch (CloneNotSupportedException e) {
849	>	throw new InternalError();
850	>	}
851
852		// Put clone into "virgin" state
853		clone.header = new Entry<E>(null, null, null);
#	Line 831 | Line 864 | public class LinkedList<E>
864
865		/**
866		* Returns an array containing all of the elements in this list
867	<	* in the correct order.
867	>	* in proper sequence (from first to last element).
868	>	*
869	>	* <p>The returned array will be "safe" in that no references to it are
870	>	* maintained by this list.  (In other words, this method must allocate
871	>	* a new array).  The caller is thus free to modify the returned array.
872	>	*
873	>	* <p>This method acts as bridge between array-based and collection-based
874	>	* APIs.
875		*
876		* @return an array containing all of the elements in this list
877	<	*         in the correct order.
877	>	*         in proper sequence
878		*/
879		public Object[] toArray() {
880	<	Object[] result = new Object[size];
880	>	Object[] result = new Object[size];
881		int i = 0;
882		for (Entry<E> e = header.next; e != header; e = e.next)
883		result[i++] = e.element;
884	<	return result;
884	>	return result;
885		}
886
887		/**
888		* Returns an array containing all of the elements in this list in
889	<	* the correct order; the runtime type of the returned array is that of
890	<	* the specified array.  If the list fits in the specified array, it
891	<	* is returned therein.  Otherwise, a new array is allocated with the
892	<	* runtime type of the specified array and the size of this list.<p>
893	<	*
894	<	* If the list fits in the specified array with room to spare
895	<	* (i.e., the array has more elements than the list),
896	<	* the element in the array immediately following the end of the
897	<	* collection is set to null.  This is useful in determining the length
898	<	* of the list <i>only</i> if the caller knows that the list
899	<	* does not contain any null elements.
889	>	* proper sequence (from first to last element); the runtime type of
890	>	* the returned array is that of the specified array.  If the list fits
891	>	* in the specified array, it is returned therein.  Otherwise, a new
892	>	* array is allocated with the runtime type of the specified array and
893	>	* the size of this list.
894	>	*
895	>	* <p>If the list fits in the specified array with room to spare (i.e.,
896	>	* the array has more elements than the list), the element in the array
897	>	* immediately following the end of the list is set to <tt>null</tt>.
898	>	* (This is useful in determining the length of the list <i>only</i> if
899	>	* the caller knows that the list does not contain any null elements.)
900	>	*
901	>	* <p>Like the {@link #toArray()} method, this method acts as bridge between
902	>	* array-based and collection-based APIs.  Further, this method allows
903	>	* precise control over the runtime type of the output array, and may,
904	>	* under certain circumstances, be used to save allocation costs.
905	>	*
906	>	* <p>Suppose <tt>x</tt> is a list known to contain only strings.
907	>	* The following code can be used to dump the list into a newly
908	>	* allocated array of <tt>String</tt>:
909	>	*
910	>	* <pre>
911	>	*     String[] y = x.toArray(new String[0]);</pre>
912	>	*
913	>	* Note that <tt>toArray(new Object[0])</tt> is identical in function to
914	>	* <tt>toArray()</tt>.
915		*
916		* @param a the array into which the elements of the list are to
917	<	*          be stored, if it is big enough; otherwise, a new array of the
918	<	*          same runtime type is allocated for this purpose.
919	<	* @return an array containing the elements of the list.
920	<	* @throws ArrayStoreException if the runtime type of a is not a
921	<	*         supertype of the runtime type of every element in this list.
922	<	* @throws NullPointerException if the specified array is null.
917	>	*          be stored, if it is big enough; otherwise, a new array of the
918	>	*          same runtime type is allocated for this purpose.
919	>	* @return an array containing the elements of the list
920	>	* @throws ArrayStoreException if the runtime type of the specified array
921	>	*         is not a supertype of the runtime type of every element in
922	>	*         this list
923	>	* @throws NullPointerException if the specified array is null
924		*/
925		public <T> T[] toArray(T[] a) {
926		if (a.length < size)
927		a = (T[])java.lang.reflect.Array.newInstance(
928		a.getClass().getComponentType(), size);
929		int i = 0;
930	<	Object[] result = a;
930	>	Object[] result = a;
931		for (Entry<E> e = header.next; e != header; e = e.next)
932		result[i++] = e.element;
933
#	Line 888 | Line 944 | public class LinkedList<E>
944		* is, serialize it).
945		*
946		* @serialData The size of the list (the number of elements it
947	<	*             contains) is emitted (int), followed by all of its
948	<	* elements (each an Object) in the proper order.
947	>	*             contains) is emitted (int), followed by all of its
948	>	*             elements (each an Object) in the proper order.
949		*/
950		private void writeObject(java.io.ObjectOutputStream s)
951		throws java.io.IOException {
952	<	// Write out any hidden serialization magic
953	<	s.defaultWriteObject();
952	>	// Write out any hidden serialization magic
953	>	s.defaultWriteObject();
954
955		// Write out size
956		s.writeInt(size);
957
958	<	// Write out all elements in the proper order.
958	>	// Write out all elements in the proper order.
959		for (Entry e = header.next; e != header; e = e.next)
960		s.writeObject(e.element);
961		}
#	Line 910 | Line 966 | public class LinkedList<E>
966		*/
967		private void readObject(java.io.ObjectInputStream s)
968		throws java.io.IOException, ClassNotFoundException {
969	<	// Read in any hidden serialization magic
970	<	s.defaultReadObject();
969	>	// Read in any hidden serialization magic
970	>	s.defaultReadObject();
971
972		// Read in size
973		int size = s.readInt();
#	Line 920 | Line 976 | public class LinkedList<E>
976		header = new Entry<E>(null, null, null);
977		header.next = header.previous = header;
978
979	<	// Read in all elements in the proper order.
980	<	for (int i=0; i<size; i++)
979	>	// Read in all elements in the proper order.
980	>	for (int i=0; i<size; i++)
981		addBefore((E)s.readObject(), header);
982		}
983		}

Diff Legend

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