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.18 by dl, Tue Dec 28 16:15:36 2004 UTC vs.
Revision 1.29 by jsr166, Tue May 17 04:09:23 2005 UTC

# Line 1 | Line 1
1   /*
2   * %W% %E%
3   *
4 < * Copyright 2004 Sun Microsystems, Inc. All rights reserved.
4 > * Copyright 2005 Sun Microsystems, Inc. All rights reserved.
5   * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
6   */
7  
8 < package java.util;
8 > package java.util;
9  
10   /**
11   * Linked list implementation of the <tt>List</tt> interface.  Implements all
# Line 14 | Line 14 | package java.util;
14   * the <tt>LinkedList</tt> class provides uniformly named methods to
15   * <tt>get</tt>, <tt>remove</tt> and <tt>insert</tt> an element at the
16   * beginning and end of the list.  These operations allow linked lists to be
17 < * used as a stack, queue, or double-ended queue ({@link Deque}).<p>
17 > * used as a stack, {@linkplain Queue queue}, or {@linkplain Deque
18 > * double-ended queue}. <p>
19   *
20   * The class implements the <tt>Deque</tt> interface, providing
21   * first-in-first-out queue operations for <tt>add</tt>,
22 < * <tt>poll</tt>, along with other stack and deque operations.
22 > * <tt>poll</tt>, along with other stack and deque operations.<p>
23   *
24   * All of the operations perform as could be expected for a doubly-linked
25   * list.  Operations that index into the list will traverse the list from
# Line 35 | Line 36 | package java.util;
36   * Collections.synchronizedList method.  This is best done at creation time,
37   * to prevent accidental unsynchronized access to the list: <pre>
38   *     List list = Collections.synchronizedList(new LinkedList(...));
39 < * </pre><p>
39 > * </pre>
40   *
41 < * The iterators returned by the this class's <tt>iterator</tt> and
41 > * <p>The iterators returned by this class's <tt>iterator</tt> and
42   * <tt>listIterator</tt> methods are <i>fail-fast</i>: if the list is
43 < * structurally modified at any time after the iterator is created, in any way
44 < * except through the Iterator's own <tt>remove</tt> or <tt>add</tt> methods,
45 < * the iterator will throw a <tt>ConcurrentModificationException</tt>.  Thus,
46 < * in the face of concurrent modification, the iterator fails quickly and
47 < * cleanly, rather than risking arbitrary, non-deterministic behavior at an
48 < * undetermined time in the future.
43 > * structurally modified at any time after the iterator is created, in
44 > * any way except through the Iterator's own <tt>remove</tt> or
45 > * <tt>add</tt> methods, the iterator will throw a {@link
46 > * ConcurrentModificationException}.  Thus, in the face of concurrent
47 > * modification, the iterator fails quickly and cleanly, rather than
48 > * risking arbitrary, non-deterministic behavior at an undetermined
49 > * time in the future.
50   *
51   * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
52   * as it is, generally speaking, impossible to make any hard guarantees in the
# Line 52 | Line 54 | package java.util;
54   * throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
55   * Therefore, it would be wrong to write a program that depended on this
56   * exception for its correctness:   <i>the fail-fast behavior of iterators
57 < * should be used only to detect bugs.</i><p>
57 > * should be used only to detect bugs.</i>
58   *
59 < * This class is a member of the
59 > * <p>This class is a member of the
60   * <a href="{@docRoot}/../guide/collections/index.html">
61   * Java Collections Framework</a>.
62   *
# Line 87 | Line 89 | public class LinkedList<E>
89       * collection, in the order they are returned by the collection's
90       * iterator.
91       *
92 <     * @param  c the collection whose elements are to be placed into this list.
93 <     * @throws NullPointerException if the specified collection is null.
92 >     * @param  c the collection whose elements are to be placed into this list
93 >     * @throws NullPointerException if the specified collection is null
94       */
95       public LinkedList(Collection<? extends E> c) {
96           this();
# Line 98 | Line 100 | public class LinkedList<E>
100      /**
101       * Returns the first element in this list.
102       *
103 <     * @return the first element in this list.
104 <     * @throws    NoSuchElementException if this list is empty.
103 >     * @return the first element in this list
104 >     * @throws NoSuchElementException if this list is empty
105       */
106      public E getFirst() {
107          if (size==0)
# Line 111 | Line 113 | public class LinkedList<E>
113      /**
114       * Returns the last element in this list.
115       *
116 <     * @return the last element in this list.
117 <     * @throws    NoSuchElementException if this list is empty.
116 >     * @return the last element in this list
117 >     * @throws NoSuchElementException if this list is empty
118       */
119      public E getLast()  {
120          if (size==0)
# Line 124 | Line 126 | public class LinkedList<E>
126      /**
127       * Removes and returns the first element from this list.
128       *
129 <     * @return the first element from this list.
130 <     * @throws    NoSuchElementException if this list is empty.
129 >     * @return the first element from this list
130 >     * @throws NoSuchElementException if this list is empty
131       */
132      public E removeFirst() {
133          return remove(header.next);
# Line 134 | Line 136 | public class LinkedList<E>
136      /**
137       * Removes and returns the last element from this list.
138       *
139 <     * @return the last element from this list.
140 <     * @throws    NoSuchElementException if this list is empty.
139 >     * @return the last element from this list
140 >     * @throws NoSuchElementException if this list is empty
141       */
142      public E removeLast() {
143          return remove(header.previous);
# Line 144 | Line 146 | public class LinkedList<E>
146      /**
147       * Inserts the given element at the beginning of this list.
148       *
149 <     * @param o the element to be inserted at the beginning of this list.
149 >     * @param e the element to be inserted at the beginning of this list
150       */
151 <    public void addFirst(E o) {
152 <        addBefore(o, header.next);
151 >    public void addFirst(E e) {
152 >        addBefore(e, header.next);
153      }
154  
155      /**
156       * Appends the given element to the end of this list.  (Identical in
157       * function to the <tt>add</tt> method; included only for consistency.)
158       *
159 <     * @param o the element to be inserted at the end of this list.
159 >     * @param e the element to be inserted at the end of this list
160       */
161 <    public void addLast(E o) {
162 <        addBefore(o, header);
161 >    public void addLast(E e) {
162 >        addBefore(e, header);
163      }
164  
165      /**
166       * Returns <tt>true</tt> if this list contains the specified element.
167       * More formally, returns <tt>true</tt> if and only if this list contains
168 <     * at least one element <tt>e</tt> such that <tt>(o==null ? e==null
169 <     * : o.equals(e))</tt>.
168 >     * at least one element <tt>e</tt> such that
169 >     * <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>.
170       *
171 <     * @param o element whose presence in this list is to be tested.
172 <     * @return <tt>true</tt> if this list contains the specified element.
171 >     * @param o element whose presence in this list is to be tested
172 >     * @return <tt>true</tt> if this list contains the specified element
173       */
174      public boolean contains(Object o) {
175          return indexOf(o) != -1;
# Line 176 | Line 178 | public class LinkedList<E>
178      /**
179       * Returns the number of elements in this list.
180       *
181 <     * @return the number of elements in this list.
181 >     * @return the number of elements in this list
182       */
183      public int size() {
184          return size;
# Line 185 | Line 187 | public class LinkedList<E>
187      /**
188       * Appends the specified element to the end of this list.
189       *
190 <     * @param o element to be appended to this list.
191 <     * @return <tt>true</tt> (as per the general contract of
190 <     * <tt>Collection.add</tt>).
190 >     * @param e element to be appended to this list
191 >     * @return <tt>true</tt> (as per the spec for {@link Collection#add})
192       */
193 <    public boolean add(E o) {
194 <        addBefore(o, header);
193 >    public boolean add(E e) {
194 >        addBefore(e, header);
195          return true;
196      }
197  
198      /**
199 <     * Removes the first occurrence of the specified element in this list.  If
200 <     * the list does not contain the element, it is unchanged.  More formally,
201 <     * removes the element with the lowest index <tt>i</tt> such that
202 <     * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt> (if such an
203 <     * element exists).
199 >     * Removes the first occurrence of the specified element from this list,
200 >     * if it is present.  If this list does not contain the element, it is
201 >     * unchanged.  More formally, removes the element with the lowest index
202 >     * <tt>i</tt> such that
203 >     * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>
204 >     * (if such an element exists).  Returns <tt>true</tt> if this list
205 >     * contained the specified element (or equivalently, if this list
206 >     * changed as a result of the call).
207       *
208 <     * @param o element to be removed from this list, if present.
209 <     * @return <tt>true</tt> if the list contained the specified element.
208 >     * @param o element to be removed from this list, if present
209 >     * @return <tt>true</tt> if this list contained the specified element
210       */
211      public boolean remove(Object o) {
212          if (o==null) {
# Line 231 | Line 235 | public class LinkedList<E>
235       * progress.  (This implies that the behavior of this call is undefined if
236       * the specified Collection is this list, and this list is nonempty.)
237       *
238 <     * @param c the elements to be inserted into this list.
239 <     * @return <tt>true</tt> if this list changed as a result of the call.
240 <     * @throws NullPointerException if the specified collection is null.
238 >     * @param c the elements to be inserted into this list
239 >     * @return <tt>true</tt> if this list changed as a result of the call
240 >     * @throws NullPointerException if the specified collection is null
241       */
242      public boolean addAll(Collection<? extends E> c) {
243          return addAll(size, c);
# Line 247 | Line 251 | public class LinkedList<E>
251       * in the list in the order that they are returned by the
252       * specified collection's iterator.
253       *
254 <     * @param index index at which to insert first element
255 <     *              from the specified collection.
256 <     * @param c elements to be inserted into this list.
257 <     * @return <tt>true</tt> if this list changed as a result of the call.
258 <     * @throws IndexOutOfBoundsException if the specified index is out of
259 <     *            range (<tt>index &lt; 0 || index &gt; size()</tt>).
256 <     * @throws NullPointerException if the specified collection is null.
254 >     * @param index index at which to insert the first element
255 >     *              from the specified collection
256 >     * @param c elements to be inserted into this list
257 >     * @return <tt>true</tt> if this list changed as a result of the call
258 >     * @throws IndexOutOfBoundsException {@inheritDoc}
259 >     * @throws NullPointerException if the specified collection is null
260       */
261      public boolean addAll(int index, Collection<? extends E> c) {
262          if (index < 0 || index > size)
# Line 300 | Line 303 | public class LinkedList<E>
303      /**
304       * Returns the element at the specified position in this list.
305       *
306 <     * @param index index of element to return.
307 <     * @return the element at the specified position in this list.
308 <     *
306 <     * @throws IndexOutOfBoundsException if the specified index is out of
307 <     * range (<tt>index &lt; 0 || index &gt;= size()</tt>).
306 >     * @param index index of the element to return
307 >     * @return the element at the specified position in this list
308 >     * @throws IndexOutOfBoundsException {@inheritDoc}
309       */
310      public E get(int index) {
311          return entry(index).element;
# Line 314 | Line 315 | public class LinkedList<E>
315       * Replaces the element at the specified position in this list with the
316       * specified element.
317       *
318 <     * @param index index of element to replace.
319 <     * @param element element to be stored at the specified position.
320 <     * @return the element previously at the specified position.
321 <     * @throws IndexOutOfBoundsException if the specified index is out of
321 <     *            range (<tt>index &lt; 0 || index &gt;= size()</tt>).
318 >     * @param index index of the element to replace
319 >     * @param element element to be stored at the specified position
320 >     * @return the element previously at the specified position
321 >     * @throws IndexOutOfBoundsException {@inheritDoc}
322       */
323      public E set(int index, E element) {
324          Entry<E> e = entry(index);
# Line 332 | Line 332 | public class LinkedList<E>
332       * Shifts the element currently at that position (if any) and any
333       * subsequent elements to the right (adds one to their indices).
334       *
335 <     * @param index index at which the specified element is to be inserted.
336 <     * @param element element to be inserted.
337 <     *
338 <     * @throws IndexOutOfBoundsException if the specified index is out of
339 <     *            range (<tt>index &lt; 0 || index &gt; size()</tt>).
335 >     * @param index index at which the specified element is to be inserted
336 >     * @param element element to be inserted
337 >     * @throws IndexOutOfBoundsException {@inheritDoc}
338       */
339      public void add(int index, E element) {
340          addBefore(element, (index==size ? header : entry(index)));
# Line 347 | Line 345 | public class LinkedList<E>
345       * subsequent elements to the left (subtracts one from their indices).
346       * Returns the element that was removed from the list.
347       *
348 <     * @param index the index of the element to removed.
349 <     * @return the element previously at the specified position.
350 <     *
353 <     * @throws IndexOutOfBoundsException if the specified index is out of
354 <     *            range (<tt>index &lt; 0 || index &gt;= size()</tt>).
348 >     * @param index the index of the element to be removed
349 >     * @return the element previously at the specified position
350 >     * @throws IndexOutOfBoundsException {@inheritDoc}
351       */
352      public E remove(int index) {
353          return remove(entry(index));
354      }
355  
356      /**
357 <     * Return the indexed entry.
357 >     * Returns the indexed entry.
358       */
359      private Entry<E> entry(int index) {
360          if (index < 0 || index >= size)
# Line 379 | Line 375 | public class LinkedList<E>
375      // Search Operations
376  
377      /**
378 <     * Returns the index in this list of the first occurrence of the
379 <     * specified element, or -1 if the List does not contain this
380 <     * element.  More formally, returns the lowest index i such that
381 <     * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>, or -1 if
382 <     * there is no such index.
383 <     *
384 <     * @param o element to search for.
385 <     * @return the index in this list of the first occurrence of the
386 <     *         specified element, or -1 if the list does not contain this
391 <     *         element.
378 >     * Returns the index of the first occurrence of the specified element
379 >     * in this list, or -1 if this list does not contain the element.
380 >     * More formally, returns the lowest index <tt>i</tt> such that
381 >     * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>,
382 >     * or -1 if there is no such index.
383 >     *
384 >     * @param o element to search for
385 >     * @return the index of the first occurrence of the specified element in
386 >     *         this list, or -1 if this list does not contain the element
387       */
388      public int indexOf(Object o) {
389          int index = 0;
# Line 409 | Line 404 | public class LinkedList<E>
404      }
405  
406      /**
407 <     * Returns the index in this list of the last occurrence of the
408 <     * specified element, or -1 if the list does not contain this
409 <     * element.  More formally, returns the highest index i such that
410 <     * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>, or -1 if
411 <     * there is no such index.
412 <     *
413 <     * @param o element to search for.
414 <     * @return the index in this list of the last occurrence of the
415 <     *         specified element, or -1 if the list does not contain this
421 <     *         element.
407 >     * Returns the index of the last occurrence of the specified element
408 >     * in this list, or -1 if this list does not contain the element.
409 >     * More formally, returns the highest index <tt>i</tt> such that
410 >     * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>,
411 >     * or -1 if there is no such index.
412 >     *
413 >     * @param o element to search for
414 >     * @return the index of the last occurrence of the specified element in
415 >     *         this list, or -1 if this list does not contain the element
416       */
417      public int lastIndexOf(Object o) {
418          int index = size;
# Line 442 | Line 436 | public class LinkedList<E>
436  
437      /**
438       * Retrieves, but does not remove, the head (first element) of this list.
439 <     * @return the head of this queue, or <tt>null</tt> if this queue is empty.
439 >     * @return the head of this list, or <tt>null</tt> if this list is empty
440       * @since 1.5
441       */
442      public E peek() {
# Line 453 | Line 447 | public class LinkedList<E>
447  
448      /**
449       * Retrieves, but does not remove, the head (first element) of this list.
450 <     * @return the head of this queue.
451 <     * @throws NoSuchElementException if this queue is empty.
450 >     * @return the head of this list
451 >     * @throws NoSuchElementException if this list is empty
452       * @since 1.5
453       */
454      public E element() {
# Line 462 | Line 456 | public class LinkedList<E>
456      }
457  
458      /**
459 <     * Retrieves and removes the head (first element) of this list.
460 <     * @return the head of this queue, or <tt>null</tt> if this queue is empty.
459 >     * Retrieves and removes the head (first element) of this list
460 >     * @return the head of this list, or <tt>null</tt> if this list is empty
461       * @since 1.5
462       */
463      public E poll() {
# Line 474 | Line 468 | public class LinkedList<E>
468  
469      /**
470       * Retrieves and removes the head (first element) of this list.
471 <     * @return the head of this queue.
472 <     * @throws NoSuchElementException if this queue is empty.
471 >     *
472 >     * @return the head of this list
473 >     * @throws NoSuchElementException if this list is empty
474       * @since 1.5
475       */
476      public E remove() {
# Line 485 | Line 480 | public class LinkedList<E>
480      /**
481       * Adds the specified element as the tail (last element) of this list.
482       *
483 <     * @param o the element to add.
484 <     * @return <tt>true</tt> (as per the general contract of
490 <     * <tt>Queue.offer</tt>)
483 >     * @param e the element to add
484 >     * @return <tt>true</tt> (as per the spec for {@link Queue#offer})
485       * @since 1.5
486       */
487 <    public boolean offer(E o) {
488 <        return add(o);
487 >    public boolean offer(E e) {
488 >        return add(e);
489      }
490  
491      // Deque operations
492      /**
493 <     * Inserts the specified element to the front this deque.
493 >     * Inserts the specified element at the front of this list.
494       *
495       * @param e the element to insert
496       * @return <tt>true</tt> (as per the spec for {@link Deque#offerFirst})
# Line 508 | Line 502 | public class LinkedList<E>
502      }
503  
504      /**
505 <     * Inserts the specified element to the end this deque.
505 >     * Inserts the specified element at the end of this list.
506       *
507       * @param e the element to insert
508       * @return <tt>true</tt> (as per the spec for {@link Deque#offerLast})
# Line 520 | Line 514 | public class LinkedList<E>
514      }
515  
516      /**
517 <     * Retrieves, but does not remove, the first element of this deque,
518 <     * returning <tt>null</tt> if this deque is empty.
517 >     * Retrieves, but does not remove, the first element of this list,
518 >     * or returns <tt>null</tt> if this list is empty.
519       *
520 <     * @return the first element of this deque, or <tt>null</tt> if
521 <     *     this deque is empty
520 >     * @return the first element of this list, or <tt>null</tt>
521 >     *         if this list is empty
522       * @since 1.6
523       */
524      public E peekFirst() {
# Line 534 | Line 528 | public class LinkedList<E>
528      }
529  
530      /**
531 <     * Retrieves, but does not remove, the last element of this deque,
532 <     * returning <tt>null</tt> if this deque is empty.
531 >     * Retrieves, but does not remove, the last element of this list,
532 >     * or returns <tt>null</tt> if this list is empty.
533       *
534 <     * @return the last element of this deque, or <tt>null</tt> if this deque
535 <     *     is empty
534 >     * @return the last element of this list, or <tt>null</tt>
535 >     *         if this list is empty
536       * @since 1.6
537       */
538      public E peekLast() {
# Line 548 | Line 542 | public class LinkedList<E>
542      }
543  
544      /**
545 <     * Retrieves and removes the first element of this deque, or
546 <     * <tt>null</tt> if this deque is empty.
545 >     * Retrieves and removes the first element of this list, or
546 >     * <tt>null</tt> if this list is empty.
547       *
548 <     * @return the first element of this deque, or <tt>null</tt> if
549 <     *     this deque is empty
548 >     * @return the first element of this list, or <tt>null</tt> if
549 >     *     this list is empty
550       * @since 1.6
551       */
552      public E pollFirst() {
# Line 562 | Line 556 | public class LinkedList<E>
556      }
557  
558      /**
559 <     * Retrieves and removes the last element of this deque, or
560 <     * <tt>null</tt> if this deque is empty.
559 >     * Retrieves and removes the last element of this list, or
560 >     * <tt>null</tt> if this list is empty.
561       *
562 <     * @return the last element of this deque, or <tt>null</tt> if
563 <     *     this deque is empty
562 >     * @return the last element of this list, or <tt>null</tt> if
563 >     *     this list is empty
564       * @since 1.6
565       */
566      public E pollLast() {
# Line 576 | Line 570 | public class LinkedList<E>
570      }
571  
572      /**
573 <     * Pushes an element onto the stack represented by this deque.  In other
574 <     * words, inserts the element to the front this deque.
573 >     * Pushes an element onto the stack represented by this list.  In other
574 >     * words, inserts the element at the front of this list.
575       *
576       * <p>This method is equivalent to {@link #addFirst}.
577       *
# Line 589 | Line 583 | public class LinkedList<E>
583      }
584  
585      /**
586 <     * Pops an element from the stack represented by this deque.  In other
587 <     * words, removes and returns the the first element of this deque.
586 >     * Pops an element from the stack represented by this list.  In other
587 >     * words, removes and returns the first element of this list.
588       *
589       * <p>This method is equivalent to {@link #removeFirst()}.
590       *
591 <     * @return the element at the front of this deque (which is the top
592 <     *     of the stack represented by this deque)
593 <     * @throws NoSuchElementException if this deque is empty
591 >     * @return the element at the front of this list (which is the top
592 >     *         of the stack represented by this list)
593 >     * @throws NoSuchElementException if this list is empty
594       * @since 1.6
595       */
596      public E pop() {
# Line 605 | Line 599 | public class LinkedList<E>
599  
600      /**
601       * Removes the first occurrence of the specified element in this
602 <     * deque (when traversing the deque from head to tail).  If the deque
602 >     * list (when traversing the list from head to tail).  If the list
603       * does not contain the element, it is unchanged.
604       *
605 <     * @param e element to be removed from this deque, if present
606 <     * @return <tt>true</tt> if the deque contained the specified element
605 >     * @param o element to be removed from this list, if present
606 >     * @return <tt>true</tt> if the list contained the specified element
607       * @since 1.6
608       */
609 <    public boolean removeFirstOccurrence(Object e) {
610 <        return remove(e);
609 >    public boolean removeFirstOccurrence(Object o) {
610 >        return remove(o);
611      }
612  
613      /**
614       * Removes the last occurrence of the specified element in this
615 <     * deque (when traversing the deque from head to tail).  If the deque
615 >     * list (when traversing the list from head to tail).  If the list
616       * does not contain the element, it is unchanged.
617       *
618 <     * @param o element to be removed from this deque, if present
619 <     * @return <tt>true</tt> if the deque contained the specified element
618 >     * @param o element to be removed from this list, if present
619 >     * @return <tt>true</tt> if the list contained the specified element
620       * @since 1.6
621       */
622      public boolean removeLastOccurrence(Object o) {
# Line 658 | Line 652 | public class LinkedList<E>
652       * than risking arbitrary, non-deterministic behavior at an undetermined
653       * time in the future.
654       *
655 <     * @param index index of first element to be returned from the
656 <     *              list-iterator (by a call to <tt>next</tt>).
655 >     * @param index index of the first element to be returned from the
656 >     *              list-iterator (by a call to <tt>next</tt>)
657       * @return a ListIterator of the elements in this list (in proper
658 <     *         sequence), starting at the specified position in the list.
659 <     * @throws    IndexOutOfBoundsException if index is out of range
666 <     *            (<tt>index &lt; 0 || index &gt; size()</tt>).
658 >     *         sequence), starting at the specified position in the list
659 >     * @throws IndexOutOfBoundsException {@inheritDoc}
660       * @see List#listIterator(int)
661       */
662      public ListIterator<E> listIterator(int index) {
# Line 744 | Line 737 | public class LinkedList<E>
737              expectedModCount++;
738          }
739  
740 <        public void set(E o) {
740 >        public void set(E e) {
741              if (lastReturned == header)
742                  throw new IllegalStateException();
743              checkForComodification();
744 <            lastReturned.element = o;
744 >            lastReturned.element = e;
745          }
746  
747 <        public void add(E o) {
747 >        public void add(E e) {
748              checkForComodification();
749              lastReturned = header;
750 <            addBefore(o, next);
750 >            addBefore(e, next);
751              nextIndex++;
752              expectedModCount++;
753          }
# Line 777 | Line 770 | public class LinkedList<E>
770          }
771      }
772  
773 <    private Entry<E> addBefore(E o, Entry<E> e) {
774 <        Entry<E> newEntry = new Entry<E>(o, e, e.previous);
773 >    private Entry<E> addBefore(E e, Entry<E> entry) {
774 >        Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);
775          newEntry.previous.next = newEntry;
776          newEntry.next.previous = newEntry;
777          size++;
# Line 804 | Line 797 | public class LinkedList<E>
797       * Returns a shallow copy of this <tt>LinkedList</tt>. (The elements
798       * themselves are not cloned.)
799       *
800 <     * @return a shallow copy of this <tt>LinkedList</tt> instance.
800 >     * @return a shallow copy of this <tt>LinkedList</tt> instance
801       */
802      public Object clone() {
803          LinkedList<E> clone = null;
# Line 829 | Line 822 | public class LinkedList<E>
822  
823      /**
824       * Returns an array containing all of the elements in this list
825 <     * in the correct order.
825 >     * in proper sequence (from first to last element).
826       *
827 +     * <p>The returned array will be "safe" in that no references to it are
828 +     * maintained by this list.  (In other words, this method must allocate
829 +     * a new array).  The caller is thus free to modify the returned array.
830 +     *
831       * @return an array containing all of the elements in this list
832 <     *         in the correct order.
832 >     *         in proper sequence
833       */
834      public Object[] toArray() {
835          Object[] result = new Object[size];
# Line 844 | Line 841 | public class LinkedList<E>
841  
842      /**
843       * Returns an array containing all of the elements in this list in
844 <     * the correct order; the runtime type of the returned array is that of
845 <     * the specified array.  If the list fits in the specified array, it
846 <     * is returned therein.  Otherwise, a new array is allocated with the
847 <     * runtime type of the specified array and the size of this list.<p>
848 <     *
849 <     * If the list fits in the specified array with room to spare
850 <     * (i.e., the array has more elements than the list),
851 <     * the element in the array immediately following the end of the
852 <     * collection is set to null.  This is useful in determining the length
853 <     * of the list <i>only</i> if the caller knows that the list
854 <     * does not contain any null elements.
844 >     * proper sequence (from first to last element); the runtime type of
845 >     * the returned array is that of the specified array.  If the list fits
846 >     * in the specified array, it is returned therein.  Otherwise, a new
847 >     * array is allocated with the runtime type of the specified array and
848 >     * the size of this list.
849 >     *
850 >     * <p>If the list fits in the specified array with room to spare (i.e.,
851 >     * the array has more elements than the list), the element in the array
852 >     * immediately following the end of the list is set to <tt>null</tt>.
853 >     * (This is useful in determining the length of the list <i>only</i> if
854 >     * the caller knows that the list does not contain any null elements.)
855 >     *
856 >     * <p>Like the {@link #toArray()} method, this method acts as bridge between
857 >     * array-based and collection-based APIs.  Further, this method allows
858 >     * precise control over the runtime type of the output array, and may,
859 >     * under certain circumstances, be used to save allocation costs.
860 >     *
861 >     * <p>Suppose <tt>x</tt> is a list known to contain only strings.
862 >     * The following code can be used to dump the list into a newly
863 >     * allocated array of <tt>String</tt>:
864 >     *
865 >     * <pre>
866 >     *     String[] y = x.toArray(new String[0]);</pre>
867 >     *
868 >     * Note that <tt>toArray(new Object[0])</tt> is identical in function to
869 >     * <tt>toArray()</tt>.
870       *
871       * @param a the array into which the elements of the list are to
872 <     *          be stored, if it is big enough; otherwise, a new array of the
873 <     *          same runtime type is allocated for this purpose.
874 <     * @return an array containing the elements of the list.
875 <     * @throws ArrayStoreException if the runtime type of a is not a
876 <     *         supertype of the runtime type of every element in this list.
877 <     * @throws NullPointerException if the specified array is null.
872 >     *          be stored, if it is big enough; otherwise, a new array of the
873 >     *          same runtime type is allocated for this purpose.
874 >     * @return an array containing the elements of the list
875 >     * @throws ArrayStoreException if the runtime type of the specified array
876 >     *         is not a supertype of the runtime type of every element in
877 >     *         this list
878 >     * @throws NullPointerException if the specified array is null
879       */
880      public <T> T[] toArray(T[] a) {
881          if (a.length < size)
# Line 886 | Line 899 | public class LinkedList<E>
899       * is, serialize it).
900       *
901       * @serialData The size of the list (the number of elements it
902 <     *             contains) is emitted (int), followed by all of its
903 <     * elements (each an Object) in the proper order.
902 >     *             contains) is emitted (int), followed by all of its
903 >     *             elements (each an Object) in the proper order.
904       */
905      private void writeObject(java.io.ObjectOutputStream s)
906          throws java.io.IOException {

Diff Legend

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