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.28 by jsr166, Mon May 16 05:17:07 2005 UTC vs.
Revision 1.47 by jsr166, Sun May 20 07:54:01 2007 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
#	Line 65 | Line 85 | package java.util;
85		* @see     List
86		* @see     ArrayList
87		* @see     Vector
68	–	* @see     Collections#synchronizedList(List)
88		* @since 1.2
89		* @param <E> the type of elements held in this collection
90		*/
#	Line 92 | Line 111 | public class LinkedList<E>
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.
#	Line 144 | Line 163 | public class LinkedList<E>
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 e the element to be inserted at the beginning of this list
168	>	* @param e the element to add
169		*/
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 e the element to be inserted at the end of this list
179	>	* @param e the element to add
180		*/
181		public void addLast(E e) {
182		addBefore(e, header);
#	Line 187 | Line 207 | public class LinkedList<E>
207		/**
208		* Appends the specified element to the end of this list.
209		*
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 per the spec for {@link Collection#add})
213	>	* @return <tt>true</tt> (as specified by {@link Collection#add})
214		*/
215		public boolean add(E e) {
216		addBefore(e, header);
#	Line 232 | 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
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		*/
#	Line 253 | Line 275 | public class LinkedList<E>
275		*
276		* @param index index at which to insert the first element
277		*              from the specified collection
278	<	* @param c elements to be inserted into this list
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
#	Line 375 | 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.
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 in this list of the first occurrence of the
408	<	*         specified element, or -1 if the list does not contain this
387	<	*         element
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 405 | 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.
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 in this list of the last occurrence of the
437	<	*         specified element, or -1 if the list does not contain this
417	<	*         element
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 483 | Line 503 | public class LinkedList<E>
503		* Adds the specified element as the tail (last element) of this list.
504		*
505		* @param e the element to add
506	<	* @return <tt>true</tt> (as per the spec for {@link Queue#offer})
506	>	* @return <tt>true</tt> (as specified by {@link Queue#offer})
507		* @since 1.5
508		*/
509		public boolean offer(E e) {
#	Line 495 | 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 507 | 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 544 | 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 558 | 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 623 | 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 796 | Line 816 | public class LinkedList<E>
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		*
#	Line 824 | 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];
#	Line 839 | Line 887 | public class LinkedList<E>
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
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) {

Diff Legend

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