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.8 by dl, Fri Sep 26 11:37:06 2003 UTC vs.
Revision 1.28 by jsr166, Mon May 16 05:17:07 2005 UTC

# Line 1 | Line 1
1   /*
2   * %W% %E%
3   *
4 < * Copyright 2003 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  
# 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 (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>Queue</tt> interface, providing
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>, etc. Other stack and deque operations could be
22 < * easily recast in terms of the standard list operations.  They're
23 < * included here primarily for convenience, though they may run
24 < * slightly faster than the equivalent List operations.<p>
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 38 | 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 55 | 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 68 | Line 67 | package java.util;
67   * @see     Vector
68   * @see     Collections#synchronizedList(List)
69   * @since 1.2
70 + * @param <E> the type of elements held in this collection
71   */
72  
73   public class LinkedList<E>
74      extends AbstractSequentialList<E>
75 <    implements List<E>, Queue<E>, Cloneable, java.io.Serializable
75 >    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
76   {
77      private transient Entry<E> header = new Entry<E>(null, null, null);
78      private transient int size = 0;
# Line 89 | 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 100 | 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 113 | 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 126 | 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 <        E first = header.next.element;
134 <        remove(header.next);
135 <        return first;
133 >        return remove(header.next);
134      }
135  
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 <        E last = header.previous.element;
146 <        remove(header.previous);
147 <        return last;
143 >        return remove(header.previous);
144      }
145  
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 182 | 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 191 | 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
196 <     * <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 237 | 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 253 | 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>).
262 <     * @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 288 | Line 285 | public class LinkedList<E>
285       * Removes all of the elements from this list.
286       */
287      public void clear() {
288 <        modCount++;
288 >        Entry<E> e = header.next;
289 >        while (e != header) {
290 >            Entry<E> next = e.next;
291 >            e.next = e.previous = null;
292 >            e.element = null;
293 >            e = next;
294 >        }
295          header.next = header.previous = header;
296 <        size = 0;
296 >        size = 0;
297 >        modCount++;
298      }
299  
300  
# Line 299 | 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 <     *
305 <     * @throws IndexOutOfBoundsException if the specified index is is out of
306 <     * 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 313 | 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
320 <     *            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 331 | 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 <     *
337 <     * @throws IndexOutOfBoundsException if the specified index is out of
338 <     *            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 346 | 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 <     *
352 <     * @throws IndexOutOfBoundsException if the specified index is out of
353 <     *            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 <        Entry<E> e = entry(index);
357 <        remove(e);
358 <        return e.element;
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 386 | Line 381 | public class LinkedList<E>
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.
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
387 <     *         element.
386 >     *         specified element, or -1 if the list does not contain this
387 >     *         element
388       */
389      public int indexOf(Object o) {
390          int index = 0;
# Line 416 | Line 411 | public class LinkedList<E>
411       * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>, or -1 if
412       * there is no such index.
413       *
414 <     * @param o element to search for.
414 >     * @param o element to search for
415       * @return the index in this list of the last occurrence of the
416 <     *         specified element, or -1 if the list does not contain this
417 <     *         element.
416 >     *         specified element, or -1 if the list does not contain this
417 >     *         element
418       */
419      public int lastIndexOf(Object o) {
420          int index = size;
# Line 443 | Line 438 | public class LinkedList<E>
438  
439      /**
440       * Retrieves, but does not remove, the head (first element) of this list.
441 <     * @return the head of this queue, or <tt>null</tt> if this queue is empty.
441 >     * @return the head of this list, or <tt>null</tt> if this list is empty
442       * @since 1.5
443       */
444      public E peek() {
# Line 454 | Line 449 | public class LinkedList<E>
449  
450      /**
451       * Retrieves, but does not remove, the head (first element) of this list.
452 <     * @return the head of this queue.
453 <     * @throws NoSuchElementException if this queue is empty.
452 >     * @return the head of this list
453 >     * @throws NoSuchElementException if this list is empty
454       * @since 1.5
455       */
456      public E element() {
# Line 463 | Line 458 | public class LinkedList<E>
458      }
459  
460      /**
461 <     * Retrieves and removes the head (first element) of this list.
462 <     * @return the head of this queue, or <tt>null</tt> if this queue is empty.
461 >     * Retrieves and removes the head (first element) of this list
462 >     * @return the head of this list, or <tt>null</tt> if this list is empty
463       * @since 1.5
464       */
465      public E poll() {
# Line 475 | Line 470 | public class LinkedList<E>
470  
471      /**
472       * Retrieves and removes the head (first element) of this list.
473 <     * @return the head of this queue.
474 <     * @throws NoSuchElementException if this queue is empty.
473 >     *
474 >     * @return the head of this list
475 >     * @throws NoSuchElementException if this list is empty
476       * @since 1.5
477       */
478      public E remove() {
# Line 486 | Line 482 | public class LinkedList<E>
482      /**
483       * Adds the specified element as the tail (last element) of this list.
484       *
485 <     * @param x the element to add.
486 <     * @return <tt>true</tt> (as per the general contract of
491 <     * <tt>Queue.offer</tt>)
485 >     * @param e the element to add
486 >     * @return <tt>true</tt> (as per the spec for {@link Queue#offer})
487       * @since 1.5
488       */
489 <    public boolean offer(E x) {
490 <        return add(x);
489 >    public boolean offer(E e) {
490 >        return add(e);
491 >    }
492 >
493 >    // Deque operations
494 >    /**
495 >     * Inserts the specified element at the front of this list.
496 >     *
497 >     * @param e the element to insert
498 >     * @return <tt>true</tt> (as per the spec for {@link Deque#offerFirst})
499 >     * @since 1.6
500 >     */
501 >    public boolean offerFirst(E e) {
502 >        addFirst(e);
503 >        return true;
504 >    }
505 >
506 >    /**
507 >     * Inserts the specified element at the end of this list.
508 >     *
509 >     * @param e the element to insert
510 >     * @return <tt>true</tt> (as per the spec for {@link Deque#offerLast})
511 >     * @since 1.6
512 >     */
513 >    public boolean offerLast(E e) {
514 >        addLast(e);
515 >        return true;
516 >    }
517 >
518 >    /**
519 >     * Retrieves, but does not remove, the first element of this list,
520 >     * or returns <tt>null</tt> if this list is empty.
521 >     *
522 >     * @return the first element of this list, or <tt>null</tt>
523 >     *         if this list is empty
524 >     * @since 1.6
525 >     */
526 >    public E peekFirst() {
527 >        if (size==0)
528 >            return null;
529 >        return getFirst();
530 >    }
531 >
532 >    /**
533 >     * Retrieves, but does not remove, the last element of this list,
534 >     * or returns <tt>null</tt> if this list is empty.
535 >     *
536 >     * @return the last element of this list, or <tt>null</tt>
537 >     *         if this list is empty
538 >     * @since 1.6
539 >     */
540 >    public E peekLast() {
541 >        if (size==0)
542 >            return null;
543 >        return getLast();
544 >    }
545 >
546 >    /**
547 >     * Retrieves and removes the first element of this list, or
548 >     * <tt>null</tt> if this list is empty.
549 >     *
550 >     * @return the first element of this list, or <tt>null</tt> if
551 >     *     this list is empty
552 >     * @since 1.6
553 >     */
554 >    public E pollFirst() {
555 >        if (size==0)
556 >            return null;
557 >        return removeFirst();
558 >    }
559 >
560 >    /**
561 >     * Retrieves and removes the last element of this list, or
562 >     * <tt>null</tt> if this list is empty.
563 >     *
564 >     * @return the last element of this list, or <tt>null</tt> if
565 >     *     this list is empty
566 >     * @since 1.6
567 >     */
568 >    public E pollLast() {
569 >        if (size==0)
570 >            return null;
571 >        return removeLast();
572 >    }
573 >
574 >    /**
575 >     * Pushes an element onto the stack represented by this list.  In other
576 >     * words, inserts the element at the front of this list.
577 >     *
578 >     * <p>This method is equivalent to {@link #addFirst}.
579 >     *
580 >     * @param e the element to push
581 >     * @since 1.6
582 >     */
583 >    public void push(E e) {
584 >        addFirst(e);
585 >    }
586 >
587 >    /**
588 >     * Pops an element from the stack represented by this list.  In other
589 >     * words, removes and returns the first element of this list.
590 >     *
591 >     * <p>This method is equivalent to {@link #removeFirst()}.
592 >     *
593 >     * @return the element at the front of this list (which is the top
594 >     *         of the stack represented by this list)
595 >     * @throws NoSuchElementException if this list is empty
596 >     * @since 1.6
597 >     */
598 >    public E pop() {
599 >        return removeFirst();
600 >    }
601 >
602 >    /**
603 >     * Removes the first occurrence of the specified element in this
604 >     * list (when traversing the list from head to tail).  If the list
605 >     * does not contain the element, it is unchanged.
606 >     *
607 >     * @param o element to be removed from this list, if present
608 >     * @return <tt>true</tt> if the list contained the specified element
609 >     * @since 1.6
610 >     */
611 >    public boolean removeFirstOccurrence(Object o) {
612 >        return remove(o);
613 >    }
614 >
615 >    /**
616 >     * Removes the last occurrence of the specified element in this
617 >     * list (when traversing the list from head to tail).  If the list
618 >     * does not contain the element, it is unchanged.
619 >     *
620 >     * @param o element to be removed from this list, if present
621 >     * @return <tt>true</tt> if the list contained the specified element
622 >     * @since 1.6
623 >     */
624 >    public boolean removeLastOccurrence(Object o) {
625 >        if (o==null) {
626 >            for (Entry e = header.previous; e != header; e = e.previous) {
627 >                if (e.element==null) {
628 >                    remove(e);
629 >                    return true;
630 >                }
631 >            }
632 >        } else {
633 >            for (Entry e = header.previous; e != header; e = e.previous) {
634 >                if (o.equals(e.element)) {
635 >                    remove(e);
636 >                    return true;
637 >                }
638 >            }
639 >        }
640 >        return false;
641      }
642  
643      /**
# Line 509 | Line 654 | public class LinkedList<E>
654       * than risking arbitrary, non-deterministic behavior at an undetermined
655       * time in the future.
656       *
657 <     * @param index index of first element to be returned from the
658 <     *              list-iterator (by a call to <tt>next</tt>).
657 >     * @param index index of the first element to be returned from the
658 >     *              list-iterator (by a call to <tt>next</tt>)
659       * @return a ListIterator of the elements in this list (in proper
660 <     *         sequence), starting at the specified position in the list.
661 <     * @throws    IndexOutOfBoundsException if index is out of range
517 <     *            (<tt>index &lt; 0 || index &gt; size()</tt>).
660 >     *         sequence), starting at the specified position in the list
661 >     * @throws IndexOutOfBoundsException {@inheritDoc}
662       * @see List#listIterator(int)
663       */
664      public ListIterator<E> listIterator(int index) {
# Line 581 | Line 725 | public class LinkedList<E>
725  
726          public void remove() {
727              checkForComodification();
728 +            Entry<E> lastNext = lastReturned.next;
729              try {
730                  LinkedList.this.remove(lastReturned);
731              } catch (NoSuchElementException e) {
732                  throw new IllegalStateException();
733              }
734              if (next==lastReturned)
735 <                next = lastReturned.next;
735 >                next = lastNext;
736              else
737                  nextIndex--;
738              lastReturned = header;
739              expectedModCount++;
740          }
741  
742 <        public void set(E o) {
742 >        public void set(E e) {
743              if (lastReturned == header)
744                  throw new IllegalStateException();
745              checkForComodification();
746 <            lastReturned.element = o;
746 >            lastReturned.element = e;
747          }
748  
749 <        public void add(E o) {
749 >        public void add(E e) {
750              checkForComodification();
751              lastReturned = header;
752 <            addBefore(o, next);
752 >            addBefore(e, next);
753              nextIndex++;
754              expectedModCount++;
755          }
# Line 627 | Line 772 | public class LinkedList<E>
772          }
773      }
774  
775 <    private Entry<E> addBefore(E o, Entry<E> e) {
776 <        Entry<E> newEntry = new Entry<E>(o, e, e.previous);
775 >    private Entry<E> addBefore(E e, Entry<E> entry) {
776 >        Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);
777          newEntry.previous.next = newEntry;
778          newEntry.next.previous = newEntry;
779          size++;
# Line 636 | Line 781 | public class LinkedList<E>
781          return newEntry;
782      }
783  
784 <    private void remove(Entry<E> e) {
784 >    private E remove(Entry<E> e) {
785          if (e == header)
786              throw new NoSuchElementException();
787  
788 +        E result = e.element;
789          e.previous.next = e.next;
790          e.next.previous = e.previous;
791 +        e.next = e.previous = null;
792 +        e.element = null;
793          size--;
794          modCount++;
795 +        return result;
796      }
797  
798      /**
799       * Returns a shallow copy of this <tt>LinkedList</tt>. (The elements
800       * themselves are not cloned.)
801       *
802 <     * @return a shallow copy of this <tt>LinkedList</tt> instance.
802 >     * @return a shallow copy of this <tt>LinkedList</tt> instance
803       */
804      public Object clone() {
805          LinkedList<E> clone = null;
# Line 678 | Line 827 | public class LinkedList<E>
827       * in the correct order.
828       *
829       * @return an array containing all of the elements in this list
830 <     *         in the correct order.
830 >     *         in the correct order
831       */
832      public Object[] toArray() {
833          Object[] result = new Object[size];
# Line 703 | Line 852 | public class LinkedList<E>
852       * does not contain any null elements.
853       *
854       * @param a the array into which the elements of the list are to
855 <     *          be stored, if it is big enough; otherwise, a new array of the
856 <     *          same runtime type is allocated for this purpose.
857 <     * @return an array containing the elements of the list.
855 >     *          be stored, if it is big enough; otherwise, a new array of the
856 >     *          same runtime type is allocated for this purpose.
857 >     * @return an array containing the elements of the list
858       * @throws ArrayStoreException if the runtime type of a is not a
859 <     *         supertype of the runtime type of every element in this list.
860 <     * @throws NullPointerException if the specified array is null.
859 >     *         supertype of the runtime type of every element in this list
860 >     * @throws NullPointerException if the specified array is null
861       */
862      public <T> T[] toArray(T[] a) {
863          if (a.length < size)
# Line 732 | Line 881 | public class LinkedList<E>
881       * is, serialize it).
882       *
883       * @serialData The size of the list (the number of elements it
884 <     *             contains) is emitted (int), followed by all of its
885 <     * elements (each an Object) in the proper order.
884 >     *             contains) is emitted (int), followed by all of its
885 >     *             elements (each an Object) in the proper order.
886       */
887      private void writeObject(java.io.ObjectOutputStream s)
888          throws java.io.IOException {

Diff Legend

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