ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/jsr166/jsr166/src/main/java/util/LinkedList.java
(Generate patch)

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.36 by jsr166, Sat Jun 18 01:56:01 2005 UTC

# Line 6 | Line 6
6   */
7  
8   package java.util;
9 + import java.util.*; // for javadoc
10  
11   /**
12   * Linked list implementation of the <tt>List</tt> interface.  Implements all
# Line 89 | Line 90 | public class LinkedList<E>
90       * collection, in the order they are returned by the collection's
91       * iterator.
92       *
93 <     * @param  c the collection whose elements are to be placed into this list.
94 <     * @throws NullPointerException if the specified collection is null.
93 >     * @param  c the collection whose elements are to be placed into this list
94 >     * @throws NullPointerException if the specified collection is null
95       */
96 <     public LinkedList(Collection<? extends E> c) {
97 <         this();
98 <         addAll(c);
99 <     }
96 >    public LinkedList(Collection<? extends E> c) {
97 >        this();
98 >        addAll(c);
99 >    }
100  
101      /**
102       * Returns the first element in this list.
103       *
104 <     * @return the first element in this list.
105 <     * @throws    NoSuchElementException if this list is empty.
104 >     * @return the first element in this list
105 >     * @throws NoSuchElementException if this list is empty
106       */
107      public E getFirst() {
108          if (size==0)
# Line 113 | Line 114 | public class LinkedList<E>
114      /**
115       * Returns the last element in this list.
116       *
117 <     * @return the last element in this list.
118 <     * @throws    NoSuchElementException if this list is empty.
117 >     * @return the last element in this list
118 >     * @throws NoSuchElementException if this list is empty
119       */
120      public E getLast()  {
121          if (size==0)
# Line 126 | Line 127 | public class LinkedList<E>
127      /**
128       * Removes and returns the first element from this list.
129       *
130 <     * @return the first element from this list.
131 <     * @throws    NoSuchElementException if this list is empty.
130 >     * @return the first element from this list
131 >     * @throws NoSuchElementException if this list is empty
132       */
133      public E removeFirst() {
134          return remove(header.next);
# Line 136 | Line 137 | public class LinkedList<E>
137      /**
138       * Removes and returns the last element from this list.
139       *
140 <     * @return the last element from this list.
141 <     * @throws    NoSuchElementException if this list is empty.
140 >     * @return the last element from this list
141 >     * @throws NoSuchElementException if this list is empty
142       */
143      public E removeLast() {
144          return remove(header.previous);
145      }
146  
147      /**
148 <     * Inserts the given element at the beginning of this list.
148 >     * Inserts the specified element at the beginning of this list.
149       *
150 <     * @param o the element to be inserted at the beginning of this list.
150 >     * @param e the element to add
151       */
152 <    public void addFirst(E o) {
153 <        addBefore(o, header.next);
152 >    public void addFirst(E e) {
153 >        addBefore(e, header.next);
154      }
155  
156      /**
157 <     * Appends the given element to the end of this list.  (Identical in
158 <     * function to the <tt>add</tt> method; included only for consistency.)
157 >     * Appends the specified element to the end of this list.
158 >     *
159 >     * <p>This method is equivalent to {@link #add}.
160       *
161 <     * @param o the element to be inserted at the end of this list.
161 >     * @param e the element to add
162       */
163 <    public void addLast(E o) {
164 <        addBefore(o, header);
163 >    public void addLast(E e) {
164 >        addBefore(e, header);
165      }
166  
167      /**
168       * Returns <tt>true</tt> if this list contains the specified element.
169       * More formally, returns <tt>true</tt> if and only if this list contains
170 <     * at least one element <tt>e</tt> such that <tt>(o==null ? e==null
171 <     * : o.equals(e))</tt>.
170 >     * at least one element <tt>e</tt> such that
171 >     * <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>.
172       *
173 <     * @param o element whose presence in this list is to be tested.
174 <     * @return <tt>true</tt> if this list contains the specified element.
173 >     * @param o element whose presence in this list is to be tested
174 >     * @return <tt>true</tt> if this list contains the specified element
175       */
176      public boolean contains(Object o) {
177          return indexOf(o) != -1;
# Line 178 | Line 180 | public class LinkedList<E>
180      /**
181       * Returns the number of elements in this list.
182       *
183 <     * @return the number of elements in this list.
183 >     * @return the number of elements in this list
184       */
185      public int size() {
186          return size;
# Line 187 | Line 189 | public class LinkedList<E>
189      /**
190       * Appends the specified element to the end of this list.
191       *
192 <     * @param o element to be appended to this list.
193 <     * @return <tt>true</tt> (as per the general contract of
194 <     * <tt>Collection.add</tt>).
192 >     * <p>This method is equivalent to {@link #addLast}.
193 >     *
194 >     * @param e element to be appended to this list
195 >     * @return <tt>true</tt> (as per the spec for {@link Collection#add})
196       */
197 <    public boolean add(E o) {
198 <        addBefore(o, header);
197 >    public boolean add(E e) {
198 >        addBefore(e, header);
199          return true;
200      }
201  
202      /**
203 <     * Removes the first occurrence of the specified element in this list.  If
204 <     * the list does not contain the element, it is unchanged.  More formally,
205 <     * removes the element with the lowest index <tt>i</tt> such that
206 <     * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt> (if such an
207 <     * element exists).
203 >     * Removes the first occurrence of the specified element from this list,
204 >     * if it is present.  If this list does not contain the element, it is
205 >     * unchanged.  More formally, removes the element with the lowest index
206 >     * <tt>i</tt> such that
207 >     * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>
208 >     * (if such an element exists).  Returns <tt>true</tt> if this list
209 >     * contained the specified element (or equivalently, if this list
210 >     * changed as a result of the call).
211       *
212 <     * @param o element to be removed from this list, if present.
213 <     * @return <tt>true</tt> if the list contained the specified element.
212 >     * @param o element to be removed from this list, if present
213 >     * @return <tt>true</tt> if this list contained the specified element
214       */
215      public boolean remove(Object o) {
216          if (o==null) {
# Line 230 | Line 236 | public class LinkedList<E>
236       * this list, in the order that they are returned by the specified
237       * collection's iterator.  The behavior of this operation is undefined if
238       * the specified collection is modified while the operation is in
239 <     * progress.  (This implies that the behavior of this call is undefined if
240 <     * the specified Collection is this list, and this list is nonempty.)
239 >     * progress.  (Note that this will occur if the specified collection is
240 >     * this list, and it's nonempty.)
241       *
242 <     * @param c the elements to be inserted into this list.
243 <     * @return <tt>true</tt> if this list changed as a result of the call.
244 <     * @throws NullPointerException if the specified collection is null.
242 >     * @param c collection containing elements to be added to this list
243 >     * @return <tt>true</tt> if this list changed as a result of the call
244 >     * @throws NullPointerException if the specified collection is null
245       */
246      public boolean addAll(Collection<? extends E> c) {
247          return addAll(size, c);
# Line 249 | Line 255 | public class LinkedList<E>
255       * in the list in the order that they are returned by the
256       * specified collection's iterator.
257       *
258 <     * @param index index at which to insert first element
259 <     *              from the specified collection.
260 <     * @param c elements to be inserted into this list.
261 <     * @return <tt>true</tt> if this list changed as a result of the call.
262 <     * @throws IndexOutOfBoundsException if the index is out of range
263 <     *         (<tt>index &lt; 0 || index &gt; size()</tt>).
258 <     * @throws NullPointerException if the specified collection is null.
258 >     * @param index index at which to insert the first element
259 >     *              from the specified collection
260 >     * @param c collection containing elements to be added to this list
261 >     * @return <tt>true</tt> if this list changed as a result of the call
262 >     * @throws IndexOutOfBoundsException {@inheritDoc}
263 >     * @throws NullPointerException if the specified collection is null
264       */
265      public boolean addAll(int index, Collection<? extends E> c) {
266          if (index < 0 || index > size)
# Line 302 | Line 307 | public class LinkedList<E>
307      /**
308       * Returns the element at the specified position in this list.
309       *
310 <     * @param index index of element to return.
311 <     * @return the element at the specified position in this list.
312 <     *
308 <     * @throws IndexOutOfBoundsException if the index is out of range
309 <     *         (<tt>index &lt; 0 || index &gt; size()</tt>).
310 >     * @param index index of the element to return
311 >     * @return the element at the specified position in this list
312 >     * @throws IndexOutOfBoundsException {@inheritDoc}
313       */
314      public E get(int index) {
315          return entry(index).element;
# Line 316 | Line 319 | public class LinkedList<E>
319       * Replaces the element at the specified position in this list with the
320       * specified element.
321       *
322 <     * @param index index of element to replace.
323 <     * @param element element to be stored at the specified position.
324 <     * @return the element previously at the specified position.
325 <     * @throws IndexOutOfBoundsException if the index is out of range
323 <     *         (<tt>index &lt; 0 || index &gt; size()</tt>).
322 >     * @param index index of the element to replace
323 >     * @param element element to be stored at the specified position
324 >     * @return the element previously at the specified position
325 >     * @throws IndexOutOfBoundsException {@inheritDoc}
326       */
327      public E set(int index, E element) {
328          Entry<E> e = entry(index);
# Line 334 | Line 336 | public class LinkedList<E>
336       * Shifts the element currently at that position (if any) and any
337       * subsequent elements to the right (adds one to their indices).
338       *
339 <     * @param index index at which the specified element is to be inserted.
340 <     * @param element element to be inserted.
341 <     *
340 <     * @throws IndexOutOfBoundsException if the index is out of range
341 <     *         (<tt>index &lt; 0 || index &gt; size()</tt>).
339 >     * @param index index at which the specified element is to be inserted
340 >     * @param element element to be inserted
341 >     * @throws IndexOutOfBoundsException {@inheritDoc}
342       */
343      public void add(int index, E element) {
344          addBefore(element, (index==size ? header : entry(index)));
# Line 349 | Line 349 | public class LinkedList<E>
349       * subsequent elements to the left (subtracts one from their indices).
350       * Returns the element that was removed from the list.
351       *
352 <     * @param index the index of the element to removed.
353 <     * @return the element previously at the specified position.
354 <     *
355 <     * @throws IndexOutOfBoundsException if the index is out of range
356 <     *         (<tt>index &lt; 0 || index &gt; size()</tt>).
352 >     * @param index the index of the element to be removed
353 >     * @return the element previously at the specified position
354 >     * @throws IndexOutOfBoundsException {@inheritDoc}
355       */
356      public E remove(int index) {
357          return remove(entry(index));
# Line 381 | Line 379 | public class LinkedList<E>
379      // Search Operations
380  
381      /**
382 <     * Returns the index in this list of the first occurrence of the
383 <     * specified element, or -1 if the List does not contain this
384 <     * element.  More formally, returns the lowest index i such that
385 <     * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>, or -1 if
386 <     * there is no such index.
387 <     *
388 <     * @param o element to search for.
389 <     * @return the index in this list of the first occurrence of the
390 <     *         specified element, or -1 if the list does not contain this
393 <     *         element.
382 >     * Returns the index of the first occurrence of the specified element
383 >     * in this list, or -1 if this list does not contain the element.
384 >     * More formally, returns the lowest index <tt>i</tt> such that
385 >     * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>,
386 >     * or -1 if there is no such index.
387 >     *
388 >     * @param o element to search for
389 >     * @return the index of the first occurrence of the specified element in
390 >     *         this list, or -1 if this list does not contain the element
391       */
392      public int indexOf(Object o) {
393          int index = 0;
# Line 411 | Line 408 | public class LinkedList<E>
408      }
409  
410      /**
411 <     * Returns the index in this list of the last occurrence of the
412 <     * specified element, or -1 if the list does not contain this
413 <     * element.  More formally, returns the highest index i such that
414 <     * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>, or -1 if
415 <     * there is no such index.
416 <     *
417 <     * @param o element to search for.
418 <     * @return the index in this list of the last occurrence of the
419 <     *         specified element, or -1 if the list does not contain this
423 <     *         element.
411 >     * Returns the index of the last occurrence of the specified element
412 >     * in this list, or -1 if this list does not contain the element.
413 >     * More formally, returns the highest index <tt>i</tt> such that
414 >     * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>,
415 >     * or -1 if there is no such index.
416 >     *
417 >     * @param o element to search for
418 >     * @return the index of the last occurrence of the specified element in
419 >     *         this list, or -1 if this list does not contain the element
420       */
421      public int lastIndexOf(Object o) {
422          int index = size;
# Line 444 | Line 440 | public class LinkedList<E>
440  
441      /**
442       * Retrieves, but does not remove, the head (first element) of this list.
443 <     * @return the head of this list, or <tt>null</tt> if this list is empty.
443 >     * @return the head of this list, or <tt>null</tt> if this list is empty
444       * @since 1.5
445       */
446      public E peek() {
# Line 455 | Line 451 | public class LinkedList<E>
451  
452      /**
453       * Retrieves, but does not remove, the head (first element) of this list.
454 <     * @return the head of this list.
455 <     * @throws NoSuchElementException if this list is empty.
454 >     * @return the head of this list
455 >     * @throws NoSuchElementException if this list is empty
456       * @since 1.5
457       */
458      public E element() {
# Line 464 | Line 460 | public class LinkedList<E>
460      }
461  
462      /**
463 <     * Retrieves and removes the head (first element) of this list.
464 <     * @return the head of this list, or <tt>null</tt> if this list is empty.
463 >     * Retrieves and removes the head (first element) of this list
464 >     * @return the head of this list, or <tt>null</tt> if this list is empty
465       * @since 1.5
466       */
467      public E poll() {
# Line 476 | Line 472 | public class LinkedList<E>
472  
473      /**
474       * Retrieves and removes the head (first element) of this list.
475 <     * @return the head of this list.
476 <     * @throws NoSuchElementException if this list is empty.
475 >     *
476 >     * @return the head of this list
477 >     * @throws NoSuchElementException if this list is empty
478       * @since 1.5
479       */
480      public E remove() {
# Line 487 | Line 484 | public class LinkedList<E>
484      /**
485       * Adds the specified element as the tail (last element) of this list.
486       *
487 <     * @param o the element to add.
488 <     * @return <tt>true</tt> (as per the general contract of
492 <     * <tt>Queue.offer</tt>)
487 >     * @param e the element to add
488 >     * @return <tt>true</tt> (as per the spec for {@link Queue#offer})
489       * @since 1.5
490       */
491 <    public boolean offer(E o) {
492 <        return add(o);
491 >    public boolean offer(E e) {
492 >        return add(e);
493      }
494  
495      // Deque operations
# Line 523 | Line 519 | public class LinkedList<E>
519  
520      /**
521       * Retrieves, but does not remove, the first element of this list,
522 <     * returning <tt>null</tt> if this list is empty.
522 >     * or returns <tt>null</tt> if this list is empty.
523       *
524 <     * @return the first element of this list, or <tt>null</tt> if
525 <     *     this list is empty
524 >     * @return the first element of this list, or <tt>null</tt>
525 >     *         if this list is empty
526       * @since 1.6
527       */
528      public E peekFirst() {
# Line 537 | Line 533 | public class LinkedList<E>
533  
534      /**
535       * Retrieves, but does not remove, the last element of this list,
536 <     * returning <tt>null</tt> if this list is empty.
536 >     * or returns <tt>null</tt> if this list is empty.
537       *
538 <     * @return the last element of this list, or <tt>null</tt> if this list
539 <     *     is empty
538 >     * @return the last element of this list, or <tt>null</tt>
539 >     *         if this list is empty
540       * @since 1.6
541       */
542      public E peekLast() {
# Line 597 | Line 593 | public class LinkedList<E>
593       * <p>This method is equivalent to {@link #removeFirst()}.
594       *
595       * @return the element at the front of this list (which is the top
596 <     *     of the stack represented by this list)
597 <     * @throws NoSuchElementException if this list is empty.
596 >     *         of the stack represented by this list)
597 >     * @throws NoSuchElementException if this list is empty
598       * @since 1.6
599       */
600      public E pop() {
# Line 629 | Line 625 | public class LinkedList<E>
625       */
626      public boolean removeLastOccurrence(Object o) {
627          if (o==null) {
628 <            for (Entry e = header.previous; e != header; e = e.previous) {
628 >            for (Entry<E> e = header.previous; e != header; e = e.previous) {
629                  if (e.element==null) {
630                      remove(e);
631                      return true;
632                  }
633              }
634          } else {
635 <            for (Entry e = header.previous; e != header; e = e.previous) {
635 >            for (Entry<E> e = header.previous; e != header; e = e.previous) {
636                  if (o.equals(e.element)) {
637                      remove(e);
638                      return true;
# Line 660 | Line 656 | public class LinkedList<E>
656       * than risking arbitrary, non-deterministic behavior at an undetermined
657       * time in the future.
658       *
659 <     * @param index index of first element to be returned from the
660 <     *              list-iterator (by a call to <tt>next</tt>).
659 >     * @param index index of the first element to be returned from the
660 >     *              list-iterator (by a call to <tt>next</tt>)
661       * @return a ListIterator of the elements in this list (in proper
662 <     *         sequence), starting at the specified position in the list.
663 <     * @throws IndexOutOfBoundsException if the index is out of range
668 <     *         (<tt>index &lt; 0 || index &gt; size()</tt>).
662 >     *         sequence), starting at the specified position in the list
663 >     * @throws IndexOutOfBoundsException {@inheritDoc}
664       * @see List#listIterator(int)
665       */
666      public ListIterator<E> listIterator(int index) {
# Line 746 | Line 741 | public class LinkedList<E>
741              expectedModCount++;
742          }
743  
744 <        public void set(E o) {
744 >        public void set(E e) {
745              if (lastReturned == header)
746                  throw new IllegalStateException();
747              checkForComodification();
748 <            lastReturned.element = o;
748 >            lastReturned.element = e;
749          }
750  
751 <        public void add(E o) {
751 >        public void add(E e) {
752              checkForComodification();
753              lastReturned = header;
754 <            addBefore(o, next);
754 >            addBefore(e, next);
755              nextIndex++;
756              expectedModCount++;
757          }
# Line 779 | Line 774 | public class LinkedList<E>
774          }
775      }
776  
777 <    private Entry<E> addBefore(E o, Entry<E> e) {
778 <        Entry<E> newEntry = new Entry<E>(o, e, e.previous);
777 >    private Entry<E> addBefore(E e, Entry<E> entry) {
778 >        Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);
779          newEntry.previous.next = newEntry;
780          newEntry.next.previous = newEntry;
781          size++;
# Line 806 | Line 801 | public class LinkedList<E>
801       * Returns a shallow copy of this <tt>LinkedList</tt>. (The elements
802       * themselves are not cloned.)
803       *
804 <     * @return a shallow copy of this <tt>LinkedList</tt> instance.
804 >     * @return a shallow copy of this <tt>LinkedList</tt> instance
805       */
806      public Object clone() {
807          LinkedList<E> clone = null;
# Line 831 | Line 826 | public class LinkedList<E>
826  
827      /**
828       * Returns an array containing all of the elements in this list
829 <     * in the correct order.
829 >     * in proper sequence (from first to last element).
830 >     *
831 >     * <p>The returned array will be "safe" in that no references to it are
832 >     * maintained by this list.  (In other words, this method must allocate
833 >     * a new array).  The caller is thus free to modify the returned array.
834 >     *
835 >     * <p>This method acts as bridge between array-based and collection-based
836 >     * APIs.
837       *
838       * @return an array containing all of the elements in this list
839 <     *         in the correct order.
839 >     *         in proper sequence
840       */
841      public Object[] toArray() {
842          Object[] result = new Object[size];
# Line 846 | Line 848 | public class LinkedList<E>
848  
849      /**
850       * Returns an array containing all of the elements in this list in
851 <     * the correct order; the runtime type of the returned array is that of
852 <     * the specified array.  If the list fits in the specified array, it
853 <     * is returned therein.  Otherwise, a new array is allocated with the
854 <     * runtime type of the specified array and the size of this list.<p>
855 <     *
856 <     * If the list fits in the specified array with room to spare
857 <     * (i.e., the array has more elements than the list),
858 <     * the element in the array immediately following the end of the
859 <     * collection is set to null.  This is useful in determining the length
860 <     * of the list <i>only</i> if the caller knows that the list
861 <     * does not contain any null elements.
851 >     * proper sequence (from first to last element); the runtime type of
852 >     * the returned array is that of the specified array.  If the list fits
853 >     * in the specified array, it is returned therein.  Otherwise, a new
854 >     * array is allocated with the runtime type of the specified array and
855 >     * the size of this list.
856 >     *
857 >     * <p>If the list fits in the specified array with room to spare (i.e.,
858 >     * the array has more elements than the list), the element in the array
859 >     * immediately following the end of the list is set to <tt>null</tt>.
860 >     * (This is useful in determining the length of the list <i>only</i> if
861 >     * the caller knows that the list does not contain any null elements.)
862 >     *
863 >     * <p>Like the {@link #toArray()} method, this method acts as bridge between
864 >     * array-based and collection-based APIs.  Further, this method allows
865 >     * precise control over the runtime type of the output array, and may,
866 >     * under certain circumstances, be used to save allocation costs.
867 >     *
868 >     * <p>Suppose <tt>x</tt> is a list known to contain only strings.
869 >     * The following code can be used to dump the list into a newly
870 >     * allocated array of <tt>String</tt>:
871 >     *
872 >     * <pre>
873 >     *     String[] y = x.toArray(new String[0]);</pre>
874 >     *
875 >     * Note that <tt>toArray(new Object[0])</tt> is identical in function to
876 >     * <tt>toArray()</tt>.
877       *
878       * @param a the array into which the elements of the list are to
879 <     *          be stored, if it is big enough; otherwise, a new array of the
880 <     *          same runtime type is allocated for this purpose.
881 <     * @return an array containing the elements of the list.
882 <     * @throws ArrayStoreException if the runtime type of a is not a
883 <     *         supertype of the runtime type of every element in this list.
884 <     * @throws NullPointerException if the specified array is null.
879 >     *          be stored, if it is big enough; otherwise, a new array of the
880 >     *          same runtime type is allocated for this purpose.
881 >     * @return an array containing the elements of the list
882 >     * @throws ArrayStoreException if the runtime type of the specified array
883 >     *         is not a supertype of the runtime type of every element in
884 >     *         this list
885 >     * @throws NullPointerException if the specified array is null
886       */
887      public <T> T[] toArray(T[] a) {
888          if (a.length < size)
# Line 888 | Line 906 | public class LinkedList<E>
906       * is, serialize it).
907       *
908       * @serialData The size of the list (the number of elements it
909 <     *             contains) is emitted (int), followed by all of its
910 <     * elements (each an Object) in the proper order.
909 >     *             contains) is emitted (int), followed by all of its
910 >     *             elements (each an Object) in the proper order.
911       */
912      private void writeObject(java.io.ObjectOutputStream s)
913          throws java.io.IOException {

Diff Legend

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