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.4 by dl, Mon Aug 11 17:44:24 2003 UTC vs.
Revision 1.27 by jsr166, Sat May 14 02:19:00 2005 UTC

# Line 1 | Line 1
1   /*
2 < * @(#)LinkedList.java  1.53 03/06/22
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
26 < * the begining or the end, whichever is closer to the specified index.<p>
26 > * the beginning or the end, whichever is closer to the specified index.<p>
27   *
28   * <b>Note that this implementation is not synchronized.</b> If multiple
29   * threads access a list concurrently, and at least one of the threads
# 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   *
63   * @author  Josh Bloch
64 < * @version 1.53, 06/22/03
64 > * @version %I%, %G%
65   * @see     List
66   * @see     ArrayList
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      /**
# Line 172 | Line 168 | public class LinkedList<E>
168       * at least one element <tt>e</tt> such that <tt>(o==null ? e==null
169       * : 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  
# Line 207 | Line 202 | public class LinkedList<E>
202       * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt> (if such an
203       * element exists).
204       *
205 <     * @param o element to be removed from this list, if present.
206 <     * @return <tt>true</tt> if the list contained the specified element.
205 >     * @param o element to be removed from this list, if present
206 >     * @return <tt>true</tt> if the list contained the specified element
207       */
208      public boolean remove(Object o) {
209          if (o==null) {
# Line 237 | Line 232 | public class LinkedList<E>
232       * progress.  (This implies that the behavior of this call is undefined if
233       * the specified Collection is this list, and this list is nonempty.)
234       *
235 <     * @param c the elements to be inserted into this list.
236 <     * @return <tt>true</tt> if this list changed as a result of the call.
237 <     * @throws NullPointerException if the specified collection is null.
235 >     * @param c the elements to be inserted into this list
236 >     * @return <tt>true</tt> if this list changed as a result of the call
237 >     * @throws NullPointerException if the specified collection is null
238       */
239      public boolean addAll(Collection<? extends E> c) {
240          return addAll(size, c);
# Line 253 | Line 248 | public class LinkedList<E>
248       * in the list in the order that they are returned by the
249       * specified collection's iterator.
250       *
251 <     * @param index index at which to insert first element
252 <     *              from the specified collection.
253 <     * @param c elements to be inserted into this list.
254 <     * @return <tt>true</tt> if this list changed as a result of the call.
255 <     * @throws IndexOutOfBoundsException if the specified index is out of
256 <     *            range (<tt>index &lt; 0 || index &gt; size()</tt>).
257 <     * @throws NullPointerException if the specified collection is null.
251 >     * @param index index at which to insert the first element
252 >     *              from the specified collection
253 >     * @param c elements to be inserted into this list
254 >     * @return <tt>true</tt> if this list changed as a result of the call
255 >     * @throws IndexOutOfBoundsException if the index is out of range
256 >     *         (<tt>index &lt; 0 || index &gt; size()</tt>)
257 >     * @throws NullPointerException if the specified collection is null
258       */
259      public boolean addAll(int index, Collection<? extends E> c) {
260          if (index < 0 || index > size)
# Line 288 | Line 283 | public class LinkedList<E>
283       * Removes all of the elements from this list.
284       */
285      public void clear() {
286 <        modCount++;
286 >        Entry<E> e = header.next;
287 >        while (e != header) {
288 >            Entry<E> next = e.next;
289 >            e.next = e.previous = null;
290 >            e.element = null;
291 >            e = next;
292 >        }
293          header.next = header.previous = header;
294 <        size = 0;
294 >        size = 0;
295 >        modCount++;
296      }
297  
298  
# Line 299 | Line 301 | public class LinkedList<E>
301      /**
302       * Returns the element at the specified position in this list.
303       *
304 <     * @param index index of element to return.
305 <     * @return the element at the specified position in this list.
306 <     *
307 <     * @throws IndexOutOfBoundsException if the specified index is is out of
306 <     * range (<tt>index &lt; 0 || index &gt;= size()</tt>).
304 >     * @param index index of element to return
305 >     * @return the element at the specified position in this list
306 >     * @throws IndexOutOfBoundsException if the index is out of range
307 >     *         (<tt>index &lt; 0 || index &gt; size()</tt>)
308       */
309      public E get(int index) {
310          return entry(index).element;
# Line 313 | Line 314 | public class LinkedList<E>
314       * Replaces the element at the specified position in this list with the
315       * specified element.
316       *
317 <     * @param index index of element to replace.
318 <     * @param element element to be stored at the specified position.
319 <     * @return the element previously at the specified position.
320 <     * @throws IndexOutOfBoundsException if the specified index is out of
321 <     *            range (<tt>index &lt; 0 || index &gt;= size()</tt>).
317 >     * @param index index of element to replace
318 >     * @param element element to be stored at the specified position
319 >     * @return the element previously at the specified position
320 >     * @throws IndexOutOfBoundsException if the index is out of range
321 >     *         (<tt>index &lt; 0 || index &gt; size()</tt>)
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.
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>).
338 >     * @throws IndexOutOfBoundsException if the index is out of range
339 >     *         (<tt>index &lt; 0 || index &gt; size()</tt>)
340       */
341      public void add(int index, E element) {
342          addBefore(element, (index==size ? header : entry(index)));
# Line 346 | Line 347 | public class LinkedList<E>
347       * subsequent elements to the left (subtracts one from their indices).
348       * Returns the element that was removed from the list.
349       *
350 <     * @param index the index of the element to removed.
351 <     * @return the element previously at the specified position.
350 >     * @param index the index of the element to be removed
351 >     * @return the element previously at the specified position
352       *
353 <     * @throws IndexOutOfBoundsException if the specified index is out of
354 <     *            range (<tt>index &lt; 0 || index &gt;= size()</tt>).
353 >     * @throws IndexOutOfBoundsException if the index is out of range
354 >     *         (<tt>index &lt; 0 || index &gt; size()</tt>)
355       */
356      public E remove(int index) {
357 <        Entry<E> e = entry(index);
357 <        remove(e);
358 <        return e.element;
357 >        return remove(entry(index));
358      }
359  
360      /**
361 <     * Return the indexed entry.
361 >     * Returns the indexed entry.
362       */
363      private Entry<E> entry(int index) {
364          if (index < 0 || index >= size)
# Line 386 | Line 385 | public class LinkedList<E>
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.
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
391 <     *         element.
390 >     *         specified element, or -1 if the list does not contain this
391 >     *         element
392       */
393      public int indexOf(Object o) {
394          int index = 0;
# Line 416 | Line 415 | public class LinkedList<E>
415       * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>, or -1 if
416       * there is no such index.
417       *
418 <     * @param o element to search for.
418 >     * @param o element to search for
419       * @return the index in this list of the last occurrence of the
420 <     *         specified element, or -1 if the list does not contain this
421 <     *         element.
420 >     *         specified element, or -1 if the list does not contain this
421 >     *         element
422       */
423      public int lastIndexOf(Object o) {
424          int index = size;
# Line 442 | Line 441 | public class LinkedList<E>
441      // Queue operations.
442  
443      /**
444 <     * Retrieves, but does not remove, the head (first element) of this list..
445 <     * @return the head of this queue, or <tt>null</tt> if this queue is empty.
444 >     * Retrieves, but does not remove, the head (first element) of this list.
445 >     * @return the head of this list, or <tt>null</tt> if this list is empty
446 >     * @since 1.5
447       */
448      public E peek() {
449          if (size==0)
# Line 452 | Line 452 | public class LinkedList<E>
452      }
453  
454      /**
455 <     * Retrieves, but does not remove, the head (first element) of this list..
456 <     * @return the head of this queue.
457 <     * @throws NoSuchElementException if this queue is empty.
455 >     * Retrieves, but does not remove, the head (first element) of this list.
456 >     * @return the head of this list
457 >     * @throws NoSuchElementException if this list is empty
458 >     * @since 1.5
459       */
460      public E element() {
461          return getFirst();
462      }
463  
464      /**
465 <     * Retrieves and removes the head (first element) of this list..
466 <     * @return the head of this queue, or <tt>null</tt> if this queue is empty.
465 >     * Retrieves and removes the head (first element) of this list
466 >     * @return the head of this list, or <tt>null</tt> if this list is empty
467 >     * @since 1.5
468       */
469      public E poll() {
470          if (size==0)
# Line 471 | Line 473 | public class LinkedList<E>
473      }
474  
475      /**
476 <     * Retrieves and removes the head (first element) of this list..
477 <     * @return the head of this queue.
478 <     * @throws NoSuchElementException if this queue is empty.
476 >     * Retrieves and removes the head (first element) of this list.
477 >     *
478 >     * @return the head of this list
479 >     * @throws NoSuchElementException if this list is empty
480 >     * @since 1.5
481       */
482      public E remove() {
483          return removeFirst();
# Line 482 | Line 486 | public class LinkedList<E>
486      /**
487       * Adds the specified element as the tail (last element) of this list.
488       *
489 <     * @param o the element to add.
490 <     * @return <tt>true</tt> (as per the general contract of
491 <     * <tt>Queue.offer</tt>)
489 >     * @param e the element to add
490 >     * @return <tt>true</tt> (as per the spec for {@link Queue#offer})
491 >     * @since 1.5
492 >     */
493 >    public boolean offer(E e) {
494 >        return add(e);
495 >    }
496 >
497 >    // Deque operations
498 >    /**
499 >     * Inserts the specified element at the front of this list.
500 >     *
501 >     * @param e the element to insert
502 >     * @return <tt>true</tt> (as per the spec for {@link Deque#offerFirst})
503 >     * @since 1.6
504 >     */
505 >    public boolean offerFirst(E e) {
506 >        addFirst(e);
507 >        return true;
508 >    }
509 >
510 >    /**
511 >     * Inserts the specified element at the end of this list.
512 >     *
513 >     * @param e the element to insert
514 >     * @return <tt>true</tt> (as per the spec for {@link Deque#offerLast})
515 >     * @since 1.6
516 >     */
517 >    public boolean offerLast(E e) {
518 >        addLast(e);
519 >        return true;
520 >    }
521 >
522 >    /**
523 >     * Retrieves, but does not remove, the first element of this list,
524 >     * or returns <tt>null</tt> if this list is empty.
525 >     *
526 >     * @return the first element of this list, or <tt>null</tt>
527 >     *         if this list is empty.
528 >     * @since 1.6
529 >     */
530 >    public E peekFirst() {
531 >        if (size==0)
532 >            return null;
533 >        return getFirst();
534 >    }
535 >
536 >    /**
537 >     * Retrieves, but does not remove, the last element of this list,
538 >     * or returns <tt>null</tt> if this list is empty.
539 >     *
540 >     * @return the last element of this list, or <tt>null</tt>
541 >     *         if this list is empty.
542 >     * @since 1.6
543 >     */
544 >    public E peekLast() {
545 >        if (size==0)
546 >            return null;
547 >        return getLast();
548 >    }
549 >
550 >    /**
551 >     * Retrieves and removes the first element of this list, or
552 >     * <tt>null</tt> if this list is empty.
553 >     *
554 >     * @return the first element of this list, or <tt>null</tt> if
555 >     *     this list is empty
556 >     * @since 1.6
557       */
558 <    public boolean offer(E x) {
559 <        return add(x);
558 >    public E pollFirst() {
559 >        if (size==0)
560 >            return null;
561 >        return removeFirst();
562 >    }
563 >
564 >    /**
565 >     * Retrieves and removes the last element of this list, or
566 >     * <tt>null</tt> if this list is empty.
567 >     *
568 >     * @return the last element of this list, or <tt>null</tt> if
569 >     *     this list is empty
570 >     * @since 1.6
571 >     */
572 >    public E pollLast() {
573 >        if (size==0)
574 >            return null;
575 >        return removeLast();
576 >    }
577 >
578 >    /**
579 >     * Pushes an element onto the stack represented by this list.  In other
580 >     * words, inserts the element at the front of this list.
581 >     *
582 >     * <p>This method is equivalent to {@link #addFirst}.
583 >     *
584 >     * @param e the element to push
585 >     * @since 1.6
586 >     */
587 >    public void push(E e) {
588 >        addFirst(e);
589 >    }
590 >
591 >    /**
592 >     * Pops an element from the stack represented by this list.  In other
593 >     * words, removes and returns the first element of this list.
594 >     *
595 >     * <p>This method is equivalent to {@link #removeFirst()}.
596 >     *
597 >     * @return the element at the front of this list (which is the top
598 >     *         of the stack represented by this list)
599 >     * @throws NoSuchElementException if this list is empty
600 >     * @since 1.6
601 >     */
602 >    public E pop() {
603 >        return removeFirst();
604 >    }
605 >
606 >    /**
607 >     * Removes the first occurrence of the specified element in this
608 >     * list (when traversing the list from head to tail).  If the list
609 >     * does not contain the element, it is unchanged.
610 >     *
611 >     * @param o element to be removed from this list, if present
612 >     * @return <tt>true</tt> if the list contained the specified element
613 >     * @since 1.6
614 >     */
615 >    public boolean removeFirstOccurrence(Object o) {
616 >        return remove(o);
617 >    }
618 >
619 >    /**
620 >     * Removes the last occurrence of the specified element in this
621 >     * list (when traversing the list from head to tail).  If the list
622 >     * does not contain the element, it is unchanged.
623 >     *
624 >     * @param o element to be removed from this list, if present
625 >     * @return <tt>true</tt> if the list contained the specified element
626 >     * @since 1.6
627 >     */
628 >    public boolean removeLastOccurrence(Object o) {
629 >        if (o==null) {
630 >            for (Entry e = header.previous; e != header; e = e.previous) {
631 >                if (e.element==null) {
632 >                    remove(e);
633 >                    return true;
634 >                }
635 >            }
636 >        } else {
637 >            for (Entry e = header.previous; e != header; e = e.previous) {
638 >                if (o.equals(e.element)) {
639 >                    remove(e);
640 >                    return true;
641 >                }
642 >            }
643 >        }
644 >        return false;
645      }
646  
647      /**
# Line 504 | Line 658 | public class LinkedList<E>
658       * than risking arbitrary, non-deterministic behavior at an undetermined
659       * time in the future.
660       *
661 <     * @param index index of first element to be returned from the
662 <     *              list-iterator (by a call to <tt>next</tt>).
661 >     * @param index index of the first element to be returned from the
662 >     *              list-iterator (by a call to <tt>next</tt>).
663       * @return a ListIterator of the elements in this list (in proper
664 <     *         sequence), starting at the specified position in the list.
665 <     * @throws    IndexOutOfBoundsException if index is out of range
666 <     *            (<tt>index &lt; 0 || index &gt; size()</tt>).
664 >     *         sequence), starting at the specified position in the list.
665 >     * @throws IndexOutOfBoundsException if the index is out of range
666 >     *         (<tt>index &lt; 0 || index &gt; size()</tt>).
667       * @see List#listIterator(int)
668       */
669      public ListIterator<E> listIterator(int index) {
# Line 576 | Line 730 | public class LinkedList<E>
730  
731          public void remove() {
732              checkForComodification();
733 +            Entry<E> lastNext = lastReturned.next;
734              try {
735                  LinkedList.this.remove(lastReturned);
736              } catch (NoSuchElementException e) {
737                  throw new IllegalStateException();
738              }
739              if (next==lastReturned)
740 <                next = lastReturned.next;
740 >                next = lastNext;
741              else
742                  nextIndex--;
743              lastReturned = header;
744              expectedModCount++;
745          }
746  
747 <        public void set(E o) {
747 >        public void set(E e) {
748              if (lastReturned == header)
749                  throw new IllegalStateException();
750              checkForComodification();
751 <            lastReturned.element = o;
751 >            lastReturned.element = e;
752          }
753  
754 <        public void add(E o) {
754 >        public void add(E e) {
755              checkForComodification();
756              lastReturned = header;
757 <            addBefore(o, next);
757 >            addBefore(e, next);
758              nextIndex++;
759              expectedModCount++;
760          }
# Line 622 | Line 777 | public class LinkedList<E>
777          }
778      }
779  
780 <    private Entry<E> addBefore(E o, Entry<E> e) {
781 <        Entry<E> newEntry = new Entry<E>(o, e, e.previous);
780 >    private Entry<E> addBefore(E e, Entry<E> entry) {
781 >        Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);
782          newEntry.previous.next = newEntry;
783          newEntry.next.previous = newEntry;
784          size++;
# Line 631 | Line 786 | public class LinkedList<E>
786          return newEntry;
787      }
788  
789 <    private void remove(Entry<E> e) {
789 >    private E remove(Entry<E> e) {
790          if (e == header)
791              throw new NoSuchElementException();
792  
793 +        E result = e.element;
794          e.previous.next = e.next;
795          e.next.previous = e.previous;
796 +        e.next = e.previous = null;
797 +        e.element = null;
798          size--;
799          modCount++;
800 +        return result;
801      }
802  
803      /**
804       * Returns a shallow copy of this <tt>LinkedList</tt>. (The elements
805       * themselves are not cloned.)
806       *
807 <     * @return a shallow copy of this <tt>LinkedList</tt> instance.
807 >     * @return a shallow copy of this <tt>LinkedList</tt> instance
808       */
809      public Object clone() {
810          LinkedList<E> clone = null;
# Line 673 | Line 832 | public class LinkedList<E>
832       * in the correct order.
833       *
834       * @return an array containing all of the elements in this list
835 <     *         in the correct order.
835 >     *         in the correct order.
836       */
837      public Object[] toArray() {
838          Object[] result = new Object[size];
# Line 698 | Line 857 | public class LinkedList<E>
857       * does not contain any null elements.
858       *
859       * @param a the array into which the elements of the list are to
860 <     *          be stored, if it is big enough; otherwise, a new array of the
861 <     *          same runtime type is allocated for this purpose.
862 <     * @return an array containing the elements of the list.
860 >     *          be stored, if it is big enough; otherwise, a new array of the
861 >     *          same runtime type is allocated for this purpose.
862 >     * @return an array containing the elements of the list
863       * @throws ArrayStoreException if the runtime type of a is not a
864 <     *         supertype of the runtime type of every element in this list.
865 <     * @throws NullPointerException if the specified array is null.
864 >     *         supertype of the runtime type of every element in this list
865 >     * @throws NullPointerException if the specified array is null
866       */
867      public <T> T[] toArray(T[] a) {
868          if (a.length < size)
# Line 727 | Line 886 | public class LinkedList<E>
886       * is, serialize it).
887       *
888       * @serialData The size of the list (the number of elements it
889 <     *             contains) is emitted (int), followed by all of its
890 <     * elements (each an Object) in the proper order.
889 >     *             contains) is emitted (int), followed by all of its
890 >     *             elements (each an Object) in the proper order.
891       */
892      private void writeObject(java.io.ObjectOutputStream s)
893          throws java.io.IOException {

Diff Legend

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