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.2 by dl, Thu Aug 7 15:59:46 2003 UTC vs.
Revision 1.9 by dl, Sat Oct 18 12:29:27 2003 UTC

# Line 1 | Line 1
1   /*
2 < * @(#)LinkedList.java  1.43 01/12/03
2 > * %W% %E%
3   *
4 < * Copyright 2002 Sun Microsystems, Inc. All rights reserved.
4 > * Copyright 2003 Sun Microsystems, Inc. All rights reserved.
5   * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
6   */
7  
8   package java.util;
9  
10   /**
11 * <b>JSR166: Added Queue operations</b>.<p>
11   * Linked list implementation of the <tt>List</tt> interface.  Implements all
12   * optional list operations, and permits all elements (including
13   * <tt>null</tt>).  In addition to implementing the <tt>List</tt> interface,
# Line 17 | Line 16 | package java.util;
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>
18   *
19 < * All of the stack/queue/deque operations could be easily recast in terms of
20 < * the standard list operations.  They're included here primarily for
21 < * convenience, though they may run slightly faster than the equivalent List
22 < * operations.<p>
19 > * The class implements the <tt>Queue</tt> interface, providing
20 > * first-in-first-out queue operations for <tt>add</tt>,
21 > * <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>
25   *
26   * All of the operations perform as could be expected for a doubly-linked
27   * list.  Operations that index into the list will traverse the list from
28 < * the begining or the end, whichever is closer to the specified index.<p>
28 > * the beginning or the end, whichever is closer to the specified index.<p>
29   *
30   * <b>Note that this implementation is not synchronized.</b> If multiple
31   * threads access a list concurrently, and at least one of the threads
# Line 51 | Line 52 | package java.util;
52   * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
53   * as it is, generally speaking, impossible to make any hard guarantees in the
54   * presence of unsynchronized concurrent modification.  Fail-fast iterators
55 < * throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
55 > * throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
56   * Therefore, it would be wrong to write a program that depended on this
57   * exception for its correctness:   <i>the fail-fast behavior of iterators
58 < * should be used only to detect bugs.</i>
58 > * should be used only to detect bugs.</i><p>
59 > *
60 > * This class is a member of the
61 > * <a href="{@docRoot}/../guide/collections/index.html">
62 > * Java Collections Framework</a>.
63   *
64   * @author  Josh Bloch
65 < * @version 1.43, 12/03/01
66 < * @see     java.util.List
67 < * @see     java.util.ArrayList
68 < * @see     java.util.Vector
69 < * @see     java.util.Collections#synchronizedList(java.util.List)
65 > * @version %I%, %G%
66 > * @see     List
67 > * @see     ArrayList
68 > * @see     Vector
69 > * @see     Collections#synchronizedList(List)
70   * @since 1.2
71 + * @param <E> the base class of all elements held in this collection
72   */
73  
74 < public class LinkedList extends AbstractSequentialList
75 <                        implements List, Queue, Cloneable, java.io.Serializable
74 > public class LinkedList<E>
75 >    extends AbstractSequentialList<E>
76 >    implements List<E>, Queue<E>, Cloneable, java.io.Serializable
77   {
78 <    private transient Entry header = new Entry(null, null, null);
78 >    private transient Entry<E> header = new Entry<E>(null, null, null);
79      private transient int size = 0;
80  
81      /**
# Line 86 | Line 93 | public class LinkedList extends Abstract
93       * @param  c the collection whose elements are to be placed into this list.
94       * @throws NullPointerException if the specified collection is null.
95       */
96 <     public LinkedList(Collection c) {
97 <         this();
98 <         addAll(c);
96 >     public LinkedList(Collection<? extends E> c) {
97 >         this();
98 >         addAll(c);
99       }
100  
101      /**
# Line 97 | Line 104 | public class LinkedList extends Abstract
104       * @return the first element in this list.
105       * @throws    NoSuchElementException if this list is empty.
106       */
107 <    public Object getFirst() {
108 <        if (size==0)
109 <            throw new NoSuchElementException();
107 >    public E getFirst() {
108 >        if (size==0)
109 >            throw new NoSuchElementException();
110  
111 <        return header.next.element;
111 >        return header.next.element;
112      }
113  
114      /**
# Line 110 | Line 117 | public class LinkedList extends Abstract
117       * @return the last element in this list.
118       * @throws    NoSuchElementException if this list is empty.
119       */
120 <    public Object getLast()  {
121 <        if (size==0)
122 <            throw new NoSuchElementException();
120 >    public E getLast()  {
121 >        if (size==0)
122 >            throw new NoSuchElementException();
123  
124 <        return header.previous.element;
124 >        return header.previous.element;
125      }
126  
127      /**
# Line 123 | Line 130 | public class LinkedList extends Abstract
130       * @return the first element from this list.
131       * @throws    NoSuchElementException if this list is empty.
132       */
133 <    public Object removeFirst() {
134 <        Object first = header.next.element;
135 <        remove(header.next);
136 <        return first;
133 >    public E removeFirst() {
134 >        E first = header.next.element;
135 >        remove(header.next);
136 >        return first;
137      }
138  
139      /**
# Line 135 | Line 142 | public class LinkedList extends Abstract
142       * @return the last element from this list.
143       * @throws    NoSuchElementException if this list is empty.
144       */
145 <    public Object removeLast() {
146 <        Object last = header.previous.element;
147 <        remove(header.previous);
148 <        return last;
145 >    public E removeLast() {
146 >        E last = header.previous.element;
147 >        remove(header.previous);
148 >        return last;
149      }
150  
151      /**
152       * Inserts the given element at the beginning of this list.
153 <     *
153 >     *
154       * @param o the element to be inserted at the beginning of this list.
155       */
156 <    public void addFirst(Object o) {
157 <        addBefore(o, header.next);
156 >    public void addFirst(E o) {
157 >        addBefore(o, header.next);
158      }
159  
160      /**
161       * Appends the given element to the end of this list.  (Identical in
162       * function to the <tt>add</tt> method; included only for consistency.)
163 <     *
163 >     *
164       * @param o the element to be inserted at the end of this list.
165       */
166 <    public void addLast(Object o) {
167 <        addBefore(o, header);
166 >    public void addLast(E o) {
167 >        addBefore(o, header);
168      }
169  
170      /**
# Line 179 | Line 186 | public class LinkedList extends Abstract
186       * @return the number of elements in this list.
187       */
188      public int size() {
189 <        return size;
189 >        return size;
190      }
191  
192      /**
# Line 189 | Line 196 | public class LinkedList extends Abstract
196       * @return <tt>true</tt> (as per the general contract of
197       * <tt>Collection.add</tt>).
198       */
199 <    public boolean add(Object o) {
200 <        addBefore(o, header);
199 >    public boolean add(E o) {
200 >        addBefore(o, header);
201          return true;
202      }
203  
# Line 206 | Line 213 | public class LinkedList extends Abstract
213       */
214      public boolean remove(Object o) {
215          if (o==null) {
216 <            for (Entry e = header.next; e != header; e = e.next) {
216 >            for (Entry<E> e = header.next; e != header; e = e.next) {
217                  if (e.element==null) {
218                      remove(e);
219                      return true;
220                  }
221              }
222          } else {
223 <            for (Entry e = header.next; e != header; e = e.next) {
223 >            for (Entry<E> e = header.next; e != header; e = e.next) {
224                  if (o.equals(e.element)) {
225                      remove(e);
226                      return true;
# Line 235 | Line 242 | public class LinkedList extends Abstract
242       * @return <tt>true</tt> if this list changed as a result of the call.
243       * @throws NullPointerException if the specified collection is null.
244       */
245 <    public boolean addAll(Collection c) {
245 >    public boolean addAll(Collection<? extends E> c) {
246          return addAll(size, c);
247      }
248  
# Line 248 | Line 255 | public class LinkedList extends Abstract
255       * specified collection's iterator.
256       *
257       * @param index index at which to insert first element
258 <     *              from the specified collection.
258 >     *              from the specified collection.
259       * @param c elements to be inserted into this list.
260       * @return <tt>true</tt> if this list changed as a result of the call.
261       * @throws IndexOutOfBoundsException if the specified index is out of
262       *            range (<tt>index &lt; 0 || index &gt; size()</tt>).
263       * @throws NullPointerException if the specified collection is null.
264       */
265 <    public boolean addAll(int index, Collection c) {
266 <        int numNew = c.size();
267 <        if (numNew==0) {
268 <            if (index < 0 || index >= size)
269 <                throw new IndexOutOfBoundsException();
270 <            else
271 <                return false;
272 <        }
273 <        modCount++;
274 <
275 <        Entry successor = (index==size ? header : entry(index));
276 <        Entry predecessor = successor.previous;
277 <        Iterator it = c.iterator();
278 <        for (int i=0; i<numNew; i++) {
272 <            Entry e = new Entry(it.next(), successor, predecessor);
265 >    public boolean addAll(int index, Collection<? extends E> c) {
266 >        if (index < 0 || index > size)
267 >            throw new IndexOutOfBoundsException("Index: "+index+
268 >                                                ", Size: "+size);
269 >        Object[] a = c.toArray();
270 >        int numNew = a.length;
271 >        if (numNew==0)
272 >            return false;
273 >        modCount++;
274 >
275 >        Entry<E> successor = (index==size ? header : entry(index));
276 >        Entry<E> predecessor = successor.previous;
277 >        for (int i=0; i<numNew; i++) {
278 >            Entry<E> e = new Entry<E>((E)a[i], successor, predecessor);
279              predecessor.next = e;
280              predecessor = e;
281          }
# Line 283 | Line 289 | public class LinkedList extends Abstract
289       * Removes all of the elements from this list.
290       */
291      public void clear() {
292 <        modCount++;
292 >        modCount++;
293          header.next = header.previous = header;
294 <        size = 0;
294 >        size = 0;
295      }
296  
297  
# Line 296 | Line 302 | public class LinkedList extends Abstract
302       *
303       * @param index index of element to return.
304       * @return the element at the specified position in this list.
305 <     *
305 >     *
306       * @throws IndexOutOfBoundsException if the specified index is is out of
307       * range (<tt>index &lt; 0 || index &gt;= size()</tt>).
308       */
309 <    public Object get(int index) {
309 >    public E get(int index) {
310          return entry(index).element;
311      }
312  
# Line 312 | Line 318 | public class LinkedList extends Abstract
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>).
321 >     *            range (<tt>index &lt; 0 || index &gt;= size()</tt>).
322       */
323 <    public Object set(int index, Object element) {
324 <        Entry e = entry(index);
325 <        Object oldVal = e.element;
323 >    public E set(int index, E element) {
324 >        Entry<E> e = entry(index);
325 >        E oldVal = e.element;
326          e.element = element;
327          return oldVal;
328      }
# Line 328 | Line 334 | public class LinkedList extends Abstract
334       *
335       * @param index index at which the specified element is to be inserted.
336       * @param element element to be inserted.
337 <     *
337 >     *
338       * @throws IndexOutOfBoundsException if the specified index is out of
339 <     *            range (<tt>index &lt; 0 || index &gt; size()</tt>).
339 >     *            range (<tt>index &lt; 0 || index &gt; size()</tt>).
340       */
341 <    public void add(int index, Object element) {
341 >    public void add(int index, E element) {
342          addBefore(element, (index==size ? header : entry(index)));
343      }
344  
# Line 343 | Line 349 | public class LinkedList extends Abstract
349       *
350       * @param index the index of the element to removed.
351       * @return the element previously at the specified position.
352 <     *
352 >     *
353       * @throws IndexOutOfBoundsException if the specified index is out of
354 <     *            range (<tt>index &lt; 0 || index &gt;= size()</tt>).
354 >     *            range (<tt>index &lt; 0 || index &gt;= size()</tt>).
355       */
356 <    public Object remove(int index) {
357 <        Entry e = entry(index);
356 >    public E remove(int index) {
357 >        Entry<E> e = entry(index);
358          remove(e);
359          return e.element;
360      }
# Line 356 | Line 362 | public class LinkedList extends Abstract
362      /**
363       * Return the indexed entry.
364       */
365 <    private Entry entry(int index) {
365 >    private Entry<E> entry(int index) {
366          if (index < 0 || index >= size)
367              throw new IndexOutOfBoundsException("Index: "+index+
368                                                  ", Size: "+size);
369 <        Entry e = header;
369 >        Entry<E> e = header;
370          if (index < (size >> 1)) {
371              for (int i = 0; i <= index; i++)
372                  e = e.next;
# Line 383 | Line 389 | public class LinkedList extends Abstract
389       *
390       * @param o element to search for.
391       * @return the index in this list of the first occurrence of the
392 <     *         specified element, or -1 if the list does not contain this
393 <     *         element.
392 >     *         specified element, or -1 if the list does not contain this
393 >     *         element.
394       */
395      public int indexOf(Object o) {
396          int index = 0;
# Line 413 | Line 419 | public class LinkedList extends Abstract
419       *
420       * @param o element to search for.
421       * @return the index in this list of the last occurrence of the
422 <     *         specified element, or -1 if the list does not contain this
423 <     *         element.
422 >     *         specified element, or -1 if the list does not contain this
423 >     *         element.
424       */
425      public int lastIndexOf(Object o) {
426          int index = size;
# Line 434 | Line 440 | public class LinkedList extends Abstract
440          return -1;
441      }
442  
443 +    // Queue operations.
444 +
445 +    /**
446 +     * Retrieves, but does not remove, the head (first element) of this list.
447 +     * @return the head of this queue, or <tt>null</tt> if this queue is empty.
448 +     * @since 1.5
449 +     */
450 +    public E peek() {
451 +        if (size==0)
452 +            return null;
453 +        return getFirst();
454 +    }
455 +
456 +    /**
457 +     * Retrieves, but does not remove, the head (first element) of this list.
458 +     * @return the head of this queue.
459 +     * @throws NoSuchElementException if this queue is empty.
460 +     * @since 1.5
461 +     */
462 +    public E element() {
463 +        return getFirst();
464 +    }
465 +
466 +    /**
467 +     * Retrieves and removes the head (first element) of this list.
468 +     * @return the head of this queue, or <tt>null</tt> if this queue is empty.
469 +     * @since 1.5
470 +     */
471 +    public E poll() {
472 +        if (size==0)
473 +            return null;
474 +        return removeFirst();
475 +    }
476 +
477 +    /**
478 +     * Retrieves and removes the head (first element) of this list.
479 +     * @return the head of this queue.
480 +     * @throws NoSuchElementException if this queue is empty.
481 +     * @since 1.5
482 +     */
483 +    public E remove() {
484 +        return removeFirst();
485 +    }
486 +
487 +    /**
488 +     * Adds the specified element as the tail (last element) of this list.
489 +     *
490 +     * @param x the element to add.
491 +     * @return <tt>true</tt> (as per the general contract of
492 +     * <tt>Queue.offer</tt>)
493 +     * @since 1.5
494 +     */
495 +    public boolean offer(E x) {
496 +        return add(x);
497 +    }
498 +
499      /**
500       * Returns a list-iterator of the elements in this list (in proper
501       * sequence), starting at the specified position in the list.
# Line 449 | Line 511 | public class LinkedList extends Abstract
511       * time in the future.
512       *
513       * @param index index of first element to be returned from the
514 <     *              list-iterator (by a call to <tt>next</tt>).
514 >     *              list-iterator (by a call to <tt>next</tt>).
515       * @return a ListIterator of the elements in this list (in proper
516 <     *         sequence), starting at the specified position in the list.
516 >     *         sequence), starting at the specified position in the list.
517       * @throws    IndexOutOfBoundsException if index is out of range
518 <     *            (<tt>index &lt; 0 || index &gt; size()</tt>).
519 <     * @see java.util.List#listIterator(int)
518 >     *            (<tt>index &lt; 0 || index &gt; size()</tt>).
519 >     * @see List#listIterator(int)
520       */
521 <    public ListIterator listIterator(int index) {
522 <        return new ListItr(index);
521 >    public ListIterator<E> listIterator(int index) {
522 >        return new ListItr(index);
523      }
524  
525 <    private class ListItr implements ListIterator {
526 <        private Entry lastReturned = header;
527 <        private Entry next;
528 <        private int nextIndex;
529 <        private int expectedModCount = modCount;
530 <
531 <        ListItr(int index) {
532 <            if (index < 0 || index > size)
533 <                throw new IndexOutOfBoundsException("Index: "+index+
534 <                                                    ", Size: "+size);
535 <            if (index < (size >> 1)) {
536 <                next = header.next;
537 <                for (nextIndex=0; nextIndex<index; nextIndex++)
538 <                    next = next.next;
539 <            } else {
540 <                next = header;
541 <                for (nextIndex=size; nextIndex>index; nextIndex--)
542 <                    next = next.previous;
543 <            }
544 <        }
545 <
546 <        public boolean hasNext() {
547 <            return nextIndex != size;
548 <        }
549 <
550 <        public Object next() {
551 <            checkForComodification();
552 <            if (nextIndex == size)
553 <                throw new NoSuchElementException();
554 <
555 <            lastReturned = next;
556 <            next = next.next;
557 <            nextIndex++;
558 <            return lastReturned.element;
559 <        }
560 <
561 <        public boolean hasPrevious() {
562 <            return nextIndex != 0;
563 <        }
564 <
565 <        public Object previous() {
566 <            if (nextIndex == 0)
567 <                throw new NoSuchElementException();
568 <
569 <            lastReturned = next = next.previous;
570 <            nextIndex--;
571 <            checkForComodification();
572 <            return lastReturned.element;
573 <        }
574 <
575 <        public int nextIndex() {
576 <            return nextIndex;
577 <        }
525 >    private class ListItr implements ListIterator<E> {
526 >        private Entry<E> lastReturned = header;
527 >        private Entry<E> next;
528 >        private int nextIndex;
529 >        private int expectedModCount = modCount;
530 >
531 >        ListItr(int index) {
532 >            if (index < 0 || index > size)
533 >                throw new IndexOutOfBoundsException("Index: "+index+
534 >                                                    ", Size: "+size);
535 >            if (index < (size >> 1)) {
536 >                next = header.next;
537 >                for (nextIndex=0; nextIndex<index; nextIndex++)
538 >                    next = next.next;
539 >            } else {
540 >                next = header;
541 >                for (nextIndex=size; nextIndex>index; nextIndex--)
542 >                    next = next.previous;
543 >            }
544 >        }
545 >
546 >        public boolean hasNext() {
547 >            return nextIndex != size;
548 >        }
549 >
550 >        public E next() {
551 >            checkForComodification();
552 >            if (nextIndex == size)
553 >                throw new NoSuchElementException();
554 >
555 >            lastReturned = next;
556 >            next = next.next;
557 >            nextIndex++;
558 >            return lastReturned.element;
559 >        }
560 >
561 >        public boolean hasPrevious() {
562 >            return nextIndex != 0;
563 >        }
564 >
565 >        public E previous() {
566 >            if (nextIndex == 0)
567 >                throw new NoSuchElementException();
568 >
569 >            lastReturned = next = next.previous;
570 >            nextIndex--;
571 >            checkForComodification();
572 >            return lastReturned.element;
573 >        }
574 >
575 >        public int nextIndex() {
576 >            return nextIndex;
577 >        }
578 >
579 >        public int previousIndex() {
580 >            return nextIndex-1;
581 >        }
582  
583 <        public int previousIndex() {
518 <            return nextIndex-1;
519 <        }
520 <
521 <        public void remove() {
583 >        public void remove() {
584              checkForComodification();
585              try {
586                  LinkedList.this.remove(lastReturned);
587              } catch (NoSuchElementException e) {
588                  throw new IllegalStateException();
589              }
590 <            if (next==lastReturned)
590 >            if (next==lastReturned)
591                  next = lastReturned.next;
592              else
593 <                nextIndex--;
594 <            lastReturned = header;
595 <            expectedModCount++;
596 <        }
597 <
598 <        public void set(Object o) {
599 <            if (lastReturned == header)
600 <                throw new IllegalStateException();
601 <            checkForComodification();
602 <            lastReturned.element = o;
603 <        }
604 <
605 <        public void add(Object o) {
606 <            checkForComodification();
607 <            lastReturned = header;
608 <            addBefore(o, next);
609 <            nextIndex++;
610 <            expectedModCount++;
611 <        }
612 <
613 <        final void checkForComodification() {
614 <            if (modCount != expectedModCount)
615 <                throw new ConcurrentModificationException();
616 <        }
617 <    }
618 <
619 <    private static class Entry {
620 <        Object element;
621 <        Entry next;
622 <        Entry previous;
623 <
624 <        Entry(Object element, Entry next, Entry previous) {
625 <            this.element = element;
626 <            this.next = next;
627 <            this.previous = previous;
628 <        }
629 <    }
630 <
631 <    private Entry addBefore(Object o, Entry e) {
632 <        Entry newEntry = new Entry(o, e, e.previous);
633 <        newEntry.previous.next = newEntry;
634 <        newEntry.next.previous = newEntry;
635 <        size++;
636 <        modCount++;
637 <        return newEntry;
638 <    }
639 <
640 <    private void remove(Entry e) {
641 <        if (e == header)
642 <            throw new NoSuchElementException();
643 <
644 <        e.previous.next = e.next;
645 <        e.next.previous = e.previous;
646 <        size--;
647 <        modCount++;
593 >                nextIndex--;
594 >            lastReturned = header;
595 >            expectedModCount++;
596 >        }
597 >
598 >        public void set(E o) {
599 >            if (lastReturned == header)
600 >                throw new IllegalStateException();
601 >            checkForComodification();
602 >            lastReturned.element = o;
603 >        }
604 >
605 >        public void add(E o) {
606 >            checkForComodification();
607 >            lastReturned = header;
608 >            addBefore(o, next);
609 >            nextIndex++;
610 >            expectedModCount++;
611 >        }
612 >
613 >        final void checkForComodification() {
614 >            if (modCount != expectedModCount)
615 >                throw new ConcurrentModificationException();
616 >        }
617 >    }
618 >
619 >    private static class Entry<E> {
620 >        E element;
621 >        Entry<E> next;
622 >        Entry<E> previous;
623 >
624 >        Entry(E element, Entry<E> next, Entry<E> previous) {
625 >            this.element = element;
626 >            this.next = next;
627 >            this.previous = previous;
628 >        }
629 >    }
630 >
631 >    private Entry<E> addBefore(E o, Entry<E> e) {
632 >        Entry<E> newEntry = new Entry<E>(o, e, e.previous);
633 >        newEntry.previous.next = newEntry;
634 >        newEntry.next.previous = newEntry;
635 >        size++;
636 >        modCount++;
637 >        return newEntry;
638 >    }
639 >
640 >    private void remove(Entry<E> e) {
641 >        if (e == header)
642 >            throw new NoSuchElementException();
643 >
644 >        e.previous.next = e.next;
645 >        e.next.previous = e.previous;
646 >        size--;
647 >        modCount++;
648      }
649  
650      /**
# Line 592 | Line 654 | public class LinkedList extends Abstract
654       * @return a shallow copy of this <tt>LinkedList</tt> instance.
655       */
656      public Object clone() {
657 <        LinkedList clone = null;
658 <        try {
659 <            clone = (LinkedList)super.clone();
660 <        } catch (CloneNotSupportedException e) {
661 <            throw new InternalError();
662 <        }
657 >        LinkedList<E> clone = null;
658 >        try {
659 >            clone = (LinkedList<E>) super.clone();
660 >        } catch (CloneNotSupportedException e) {
661 >            throw new InternalError();
662 >        }
663  
664          // Put clone into "virgin" state
665 <        clone.header = new Entry(null, null, null);
665 >        clone.header = new Entry<E>(null, null, null);
666          clone.header.next = clone.header.previous = clone.header;
667          clone.size = 0;
668          clone.modCount = 0;
669  
670          // Initialize clone with our elements
671 <        for (Entry e = header.next; e != header; e = e.next)
671 >        for (Entry<E> e = header.next; e != header; e = e.next)
672              clone.add(e.element);
673  
674          return clone;
# Line 617 | Line 679 | public class LinkedList extends Abstract
679       * in the correct order.
680       *
681       * @return an array containing all of the elements in this list
682 <     *         in the correct order.
682 >     *         in the correct order.
683       */
684      public Object[] toArray() {
685 <        Object[] result = new Object[size];
685 >        Object[] result = new Object[size];
686          int i = 0;
687 <        for (Entry e = header.next; e != header; e = e.next)
687 >        for (Entry<E> e = header.next; e != header; e = e.next)
688              result[i++] = e.element;
689 <        return result;
689 >        return result;
690      }
691  
692      /**
# Line 642 | Line 704 | public class LinkedList extends Abstract
704       * does not contain any null elements.
705       *
706       * @param a the array into which the elements of the list are to
707 <     *          be stored, if it is big enough; otherwise, a new array of the
708 <     *          same runtime type is allocated for this purpose.
707 >     *          be stored, if it is big enough; otherwise, a new array of the
708 >     *          same runtime type is allocated for this purpose.
709       * @return an array containing the elements of the list.
710       * @throws ArrayStoreException if the runtime type of a is not a
711       *         supertype of the runtime type of every element in this list.
712       * @throws NullPointerException if the specified array is null.
713       */
714 <    public Object[] toArray(Object a[]) {
714 >    public <T> T[] toArray(T[] a) {
715          if (a.length < size)
716 <            a = (Object[])java.lang.reflect.Array.newInstance(
716 >            a = (T[])java.lang.reflect.Array.newInstance(
717                                  a.getClass().getComponentType(), size);
718          int i = 0;
719 <        for (Entry e = header.next; e != header; e = e.next)
720 <            a[i++] = e.element;
719 >        Object[] result = a;
720 >        for (Entry<E> e = header.next; e != header; e = e.next)
721 >            result[i++] = e.element;
722  
723          if (a.length > size)
724              a[size] = null;
# Line 670 | Line 733 | public class LinkedList extends Abstract
733       * is, serialize it).
734       *
735       * @serialData The size of the list (the number of elements it
736 <     *             contains) is emitted (int), followed by all of its
737 <     * elements (each an Object) in the proper order.  
736 >     *             contains) is emitted (int), followed by all of its
737 >     * elements (each an Object) in the proper order.
738       */
739 <    private synchronized void writeObject(java.io.ObjectOutputStream s)
739 >    private void writeObject(java.io.ObjectOutputStream s)
740          throws java.io.IOException {
741 <        // Write out any hidden serialization magic
742 <        s.defaultWriteObject();
741 >        // Write out any hidden serialization magic
742 >        s.defaultWriteObject();
743  
744          // Write out size
745          s.writeInt(size);
746  
747 <        // Write out all elements in the proper order.
747 >        // Write out all elements in the proper order.
748          for (Entry e = header.next; e != header; e = e.next)
749              s.writeObject(e.element);
750      }
# Line 690 | Line 753 | public class LinkedList extends Abstract
753       * Reconstitute this <tt>LinkedList</tt> instance from a stream (that is
754       * deserialize it).
755       */
756 <    private synchronized void readObject(java.io.ObjectInputStream s)
756 >    private void readObject(java.io.ObjectInputStream s)
757          throws java.io.IOException, ClassNotFoundException {
758 <        // Read in any hidden serialization magic
759 <        s.defaultReadObject();
758 >        // Read in any hidden serialization magic
759 >        s.defaultReadObject();
760  
761          // Read in size
762          int size = s.readInt();
763  
764          // Initialize header
765 <        header = new Entry(null, null, null);
765 >        header = new Entry<E>(null, null, null);
766          header.next = header.previous = header;
767  
768 <        // Read in all elements in the proper order.
769 <        for (int i=0; i<size; i++)
770 <            add(s.readObject());
708 <    }
709 <
710 <    public Object peek() {
711 <        if (size==0)
712 <            return null;
713 <        return getFirst();
714 <    }
715 <
716 <    public Object element() {
717 <        return getFirst();
768 >        // Read in all elements in the proper order.
769 >        for (int i=0; i<size; i++)
770 >            addBefore((E)s.readObject(), header);
771      }
719
720    public Object poll() {
721        if (size==0)
722            return null;
723        return removeFirst();
724    }
725
726    public Object remove() {
727        return removeFirst();
728    }
729
730    public boolean offer(Object x) {
731        return add(x);
732    }
733
772   }

Diff Legend

Removed lines
+ Added lines
< Changed lines
> Changed lines