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.13 by jozart, Mon Nov 17 08:09:34 2003 UTC vs.
Revision 1.14 by jsr166, Sun Dec 28 00:55:45 2003 UTC

# Line 63 | Line 63 | package java.util;
63   *
64   * @author  Josh Bloch
65   * @version %I%, %G%
66 < * @see     List
67 < * @see     ArrayList
68 < * @see     Vector
69 < * @see     Collections#synchronizedList(List)
66 > * @see     List
67 > * @see     ArrayList
68 > * @see     Vector
69 > * @see     Collections#synchronizedList(List)
70   * @since 1.2
71   * @param <E> the type of elements held in this collection
72   */
# Line 93 | Line 93 | public class LinkedList<E>
93       * @param  c the collection whose elements are to be placed into this list.
94       * @throws NullPointerException if the specified collection is null.
95       */
96 <    public LinkedList(Collection<? extends E> c) {
97 <        this();
98 <        addAll(c);
99 <    }
96 >     public LinkedList(Collection<? extends E> c) {
97 >         this();
98 >         addAll(c);
99 >     }
100  
101      /**
102       * Returns the first element in this list.
# Line 105 | Line 105 | public class LinkedList<E>
105       * @throws    NoSuchElementException if this list is empty.
106       */
107      public E getFirst() {
108 <        if (size==0)
109 <            throw new NoSuchElementException();
108 >        if (size==0)
109 >            throw new NoSuchElementException();
110  
111 <        return header.next.element;
111 >        return header.next.element;
112      }
113  
114      /**
# Line 118 | Line 118 | public class LinkedList<E>
118       * @throws    NoSuchElementException if this list is empty.
119       */
120      public E getLast()  {
121 <        if (size==0)
122 <            throw new NoSuchElementException();
121 >        if (size==0)
122 >            throw new NoSuchElementException();
123  
124 <        return header.previous.element;
124 >        return header.previous.element;
125      }
126  
127      /**
# Line 131 | Line 131 | public class LinkedList<E>
131       * @throws    NoSuchElementException if this list is empty.
132       */
133      public E removeFirst() {
134 <        E first = header.next.element;
135 <        remove(header.next);
136 <        return first;
134 >        return remove(header.next);
135      }
136  
137      /**
# Line 143 | Line 141 | public class LinkedList<E>
141       * @throws    NoSuchElementException if this list is empty.
142       */
143      public E removeLast() {
144 <        E last = header.previous.element;
147 <        remove(header.previous);
148 <        return last;
144 >        return remove(header.previous);
145      }
146  
147      /**
# Line 154 | Line 150 | public class LinkedList<E>
150       * @param o the element to be inserted at the beginning of this list.
151       */
152      public void addFirst(E o) {
153 <        addBefore(o, header.next);
153 >        addBefore(o, header.next);
154      }
155  
156      /**
# Line 164 | Line 160 | public class LinkedList<E>
160       * @param o the element to be inserted at the end of this list.
161       */
162      public void addLast(E o) {
163 <        addBefore(o, header);
163 >        addBefore(o, header);
164      }
165  
166      /**
# Line 186 | Line 182 | public class LinkedList<E>
182       * @return the number of elements in this list.
183       */
184      public int size() {
185 <        return size;
185 >        return size;
186      }
187  
188      /**
# Line 197 | Line 193 | public class LinkedList<E>
193       * <tt>Collection.add</tt>).
194       */
195      public boolean add(E o) {
196 <        addBefore(o, header);
196 >        addBefore(o, header);
197          return true;
198      }
199  
# Line 255 | Line 251 | public class LinkedList<E>
251       * specified collection's iterator.
252       *
253       * @param index index at which to insert first element
254 <     *              from the specified collection.
254 >     *              from the specified collection.
255       * @param c elements to be inserted into this list.
256       * @return <tt>true</tt> if this list changed as a result of the call.
257       * @throws IndexOutOfBoundsException if the specified index is out of
# Line 270 | Line 266 | public class LinkedList<E>
266          int numNew = a.length;
267          if (numNew==0)
268              return false;
269 <        modCount++;
269 >        modCount++;
270  
271          Entry<E> successor = (index==size ? header : entry(index));
272          Entry<E> predecessor = successor.previous;
273 <        for (int i=0; i<numNew; i++) {
273 >        for (int i=0; i<numNew; i++) {
274              Entry<E> e = new Entry<E>((E)a[i], successor, predecessor);
275              predecessor.next = e;
276              predecessor = e;
# Line 289 | 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;
297 +        modCount++;
298      }
299  
300  
# Line 318 | Line 321 | public class LinkedList<E>
321       * @param element element to be stored at the specified position.
322       * @return the element previously at the specified position.
323       * @throws IndexOutOfBoundsException if the specified index is out of
324 <     *            range (<tt>index &lt; 0 || index &gt;= size()</tt>).
324 >     *            range (<tt>index &lt; 0 || index &gt;= size()</tt>).
325       */
326      public E set(int index, E element) {
327          Entry<E> e = entry(index);
# Line 336 | Line 339 | public class LinkedList<E>
339       * @param element element to be inserted.
340       *
341       * @throws IndexOutOfBoundsException if the specified index is out of
342 <     *            range (<tt>index &lt; 0 || index &gt; size()</tt>).
342 >     *            range (<tt>index &lt; 0 || index &gt; size()</tt>).
343       */
344      public void add(int index, E element) {
345          addBefore(element, (index==size ? header : entry(index)));
# Line 351 | Line 354 | public class LinkedList<E>
354       * @return the element previously at the specified position.
355       *
356       * @throws IndexOutOfBoundsException if the specified index is out of
357 <     *            range (<tt>index &lt; 0 || index &gt;= size()</tt>).
357 >     *            range (<tt>index &lt; 0 || index &gt;= size()</tt>).
358       */
359      public E remove(int index) {
360 <        Entry<E> e = entry(index);
358 <        remove(e);
359 <        return e.element;
360 >        return remove(entry(index));
361      }
362  
363      /**
# Line 389 | Line 390 | public class LinkedList<E>
390       *
391       * @param o element to search for.
392       * @return the index in this list of the first occurrence of the
393 <     *         specified element, or -1 if the list does not contain this
394 <     *         element.
393 >     *         specified element, or -1 if the list does not contain this
394 >     *         element.
395       */
396      public int indexOf(Object o) {
397          int index = 0;
# Line 419 | Line 420 | public class LinkedList<E>
420       *
421       * @param o element to search for.
422       * @return the index in this list of the last occurrence of the
423 <     *         specified element, or -1 if the list does not contain this
424 <     *         element.
423 >     *         specified element, or -1 if the list does not contain this
424 >     *         element.
425       */
426      public int lastIndexOf(Object o) {
427          int index = size;
# Line 511 | Line 512 | public class LinkedList<E>
512       * time in the future.
513       *
514       * @param index index of first element to be returned from the
515 <     *              list-iterator (by a call to <tt>next</tt>).
515 >     *              list-iterator (by a call to <tt>next</tt>).
516       * @return a ListIterator of the elements in this list (in proper
517 <     *         sequence), starting at the specified position in the list.
517 >     *         sequence), starting at the specified position in the list.
518       * @throws    IndexOutOfBoundsException if index is out of range
519 <     *            (<tt>index &lt; 0 || index &gt; size()</tt>).
519 >     *            (<tt>index &lt; 0 || index &gt; size()</tt>).
520       * @see List#listIterator(int)
521       */
522      public ListIterator<E> listIterator(int index) {
523 <        return new ListItr(index);
523 >        return new ListItr(index);
524      }
525  
526      private class ListItr implements ListIterator<E> {
527 <        private Entry<E> lastReturned = header;
528 <        private Entry<E> next;
529 <        private int nextIndex;
530 <        private int expectedModCount = modCount;
531 <
532 <        ListItr(int index) {
533 <            if (index < 0 || index > size)
534 <                throw new IndexOutOfBoundsException("Index: "+index+
535 <                                                    ", Size: "+size);
536 <            if (index < (size >> 1)) {
537 <                next = header.next;
538 <                for (nextIndex=0; nextIndex<index; nextIndex++)
539 <                    next = next.next;
540 <            } else {
541 <                next = header;
542 <                for (nextIndex=size; nextIndex>index; nextIndex--)
543 <                    next = next.previous;
544 <            }
545 <        }
546 <
547 <        public boolean hasNext() {
548 <            return nextIndex != size;
549 <        }
550 <
551 <        public E next() {
552 <            checkForComodification();
553 <            if (nextIndex == size)
554 <                throw new NoSuchElementException();
555 <
556 <            lastReturned = next;
557 <            next = next.next;
558 <            nextIndex++;
559 <            return lastReturned.element;
560 <        }
561 <
562 <        public boolean hasPrevious() {
563 <            return nextIndex != 0;
564 <        }
565 <
566 <        public E previous() {
567 <            if (nextIndex == 0)
568 <                throw new NoSuchElementException();
569 <
570 <            lastReturned = next = next.previous;
571 <            nextIndex--;
572 <            checkForComodification();
573 <            return lastReturned.element;
574 <        }
575 <
576 <        public int nextIndex() {
577 <            return nextIndex;
578 <        }
579 <
580 <        public int previousIndex() {
581 <            return nextIndex-1;
582 <        }
527 >        private Entry<E> lastReturned = header;
528 >        private Entry<E> next;
529 >        private int nextIndex;
530 >        private int expectedModCount = modCount;
531 >
532 >        ListItr(int index) {
533 >            if (index < 0 || index > size)
534 >                throw new IndexOutOfBoundsException("Index: "+index+
535 >                                                    ", Size: "+size);
536 >            if (index < (size >> 1)) {
537 >                next = header.next;
538 >                for (nextIndex=0; nextIndex<index; nextIndex++)
539 >                    next = next.next;
540 >            } else {
541 >                next = header;
542 >                for (nextIndex=size; nextIndex>index; nextIndex--)
543 >                    next = next.previous;
544 >            }
545 >        }
546 >
547 >        public boolean hasNext() {
548 >            return nextIndex != size;
549 >        }
550 >
551 >        public E next() {
552 >            checkForComodification();
553 >            if (nextIndex == size)
554 >                throw new NoSuchElementException();
555 >
556 >            lastReturned = next;
557 >            next = next.next;
558 >            nextIndex++;
559 >            return lastReturned.element;
560 >        }
561 >
562 >        public boolean hasPrevious() {
563 >            return nextIndex != 0;
564 >        }
565 >
566 >        public E previous() {
567 >            if (nextIndex == 0)
568 >                throw new NoSuchElementException();
569 >
570 >            lastReturned = next = next.previous;
571 >            nextIndex--;
572 >            checkForComodification();
573 >            return lastReturned.element;
574 >        }
575 >
576 >        public int nextIndex() {
577 >            return nextIndex;
578 >        }
579 >
580 >        public int previousIndex() {
581 >            return nextIndex-1;
582 >        }
583  
584 <        public void remove() {
584 >        public void remove() {
585              checkForComodification();
586 +            Entry<E> lastNext = lastReturned.next;
587              try {
588                  LinkedList.this.remove(lastReturned);
589              } catch (NoSuchElementException e) {
590                  throw new IllegalStateException();
591              }
592 <            if (next==lastReturned)
593 <                next = lastReturned.next;
592 >            if (next==lastReturned)
593 >                next = lastNext;
594              else
595 <                nextIndex--;
596 <            lastReturned = header;
597 <            expectedModCount++;
598 <        }
599 <
600 <        public void set(E o) {
601 <            if (lastReturned == header)
602 <                throw new IllegalStateException();
603 <            checkForComodification();
604 <            lastReturned.element = o;
605 <        }
606 <
607 <        public void add(E o) {
608 <            checkForComodification();
609 <            lastReturned = header;
610 <            addBefore(o, next);
611 <            nextIndex++;
612 <            expectedModCount++;
613 <        }
614 <
615 <        final void checkForComodification() {
616 <            if (modCount != expectedModCount)
617 <                throw new ConcurrentModificationException();
618 <        }
595 >                nextIndex--;
596 >            lastReturned = header;
597 >            expectedModCount++;
598 >        }
599 >
600 >        public void set(E o) {
601 >            if (lastReturned == header)
602 >                throw new IllegalStateException();
603 >            checkForComodification();
604 >            lastReturned.element = o;
605 >        }
606 >
607 >        public void add(E o) {
608 >            checkForComodification();
609 >            lastReturned = header;
610 >            addBefore(o, next);
611 >            nextIndex++;
612 >            expectedModCount++;
613 >        }
614 >
615 >        final void checkForComodification() {
616 >            if (modCount != expectedModCount)
617 >                throw new ConcurrentModificationException();
618 >        }
619      }
620  
621      private static class Entry<E> {
622 <        E element;
623 <        Entry<E> next;
624 <        Entry<E> previous;
625 <
626 <        Entry(E element, Entry<E> next, Entry<E> previous) {
627 <            this.element = element;
628 <            this.next = next;
629 <            this.previous = previous;
630 <        }
622 >        E element;
623 >        Entry<E> next;
624 >        Entry<E> previous;
625 >
626 >        Entry(E element, Entry<E> next, Entry<E> previous) {
627 >            this.element = element;
628 >            this.next = next;
629 >            this.previous = previous;
630 >        }
631      }
632  
633      private Entry<E> addBefore(E o, Entry<E> e) {
634 <        Entry<E> newEntry = new Entry<E>(o, e, e.previous);
635 <        newEntry.previous.next = newEntry;
636 <        newEntry.next.previous = newEntry;
637 <        size++;
638 <        modCount++;
639 <        return newEntry;
640 <    }
641 <
642 <    private void remove(Entry<E> e) {
643 <        if (e == header)
644 <            throw new NoSuchElementException();
645 <
646 <        e.previous.next = e.next;
647 <        e.next.previous = e.previous;
648 <        size--;
649 <        modCount++;
634 >        Entry<E> newEntry = new Entry<E>(o, e, e.previous);
635 >        newEntry.previous.next = newEntry;
636 >        newEntry.next.previous = newEntry;
637 >        size++;
638 >        modCount++;
639 >        return newEntry;
640 >    }
641 >
642 >    private E remove(Entry<E> e) {
643 >        if (e == header)
644 >            throw new NoSuchElementException();
645 >
646 >        E result = e.element;
647 >        e.previous.next = e.next;
648 >        e.next.previous = e.previous;
649 >        e.next = e.previous = null;
650 >        e.element = null;
651 >        size--;
652 >        modCount++;
653 >        return result;
654      }
655  
656      /**
# Line 655 | Line 661 | public class LinkedList<E>
661       */
662      public Object clone() {
663          LinkedList<E> clone = null;
664 <        try {
665 <            clone = (LinkedList<E>) super.clone();
666 <        } catch (CloneNotSupportedException e) {
667 <            throw new InternalError();
668 <        }
664 >        try {
665 >            clone = (LinkedList<E>) super.clone();
666 >        } catch (CloneNotSupportedException e) {
667 >            throw new InternalError();
668 >        }
669  
670          // Put clone into "virgin" state
671          clone.header = new Entry<E>(null, null, null);
# Line 679 | Line 685 | public class LinkedList<E>
685       * in the correct order.
686       *
687       * @return an array containing all of the elements in this list
688 <     *         in the correct order.
688 >     *         in the correct order.
689       */
690      public Object[] toArray() {
691 <        Object[] result = new Object[size];
691 >        Object[] result = new Object[size];
692          int i = 0;
693          for (Entry<E> e = header.next; e != header; e = e.next)
694              result[i++] = e.element;
695 <        return result;
695 >        return result;
696      }
697  
698      /**
# Line 704 | Line 710 | public class LinkedList<E>
710       * does not contain any null elements.
711       *
712       * @param a the array into which the elements of the list are to
713 <     *          be stored, if it is big enough; otherwise, a new array of the
714 <     *          same runtime type is allocated for this purpose.
713 >     *          be stored, if it is big enough; otherwise, a new array of the
714 >     *          same runtime type is allocated for this purpose.
715       * @return an array containing the elements of the list.
716       * @throws ArrayStoreException if the runtime type of a is not a
717       *         supertype of the runtime type of every element in this list.
# Line 716 | Line 722 | public class LinkedList<E>
722              a = (T[])java.lang.reflect.Array.newInstance(
723                                  a.getClass().getComponentType(), size);
724          int i = 0;
725 <        Object[] result = a;
725 >        Object[] result = a;
726          for (Entry<E> e = header.next; e != header; e = e.next)
727              result[i++] = e.element;
728  
# Line 733 | Line 739 | public class LinkedList<E>
739       * is, serialize it).
740       *
741       * @serialData The size of the list (the number of elements it
742 <     *             contains) is emitted (int), followed by all of its
742 >     *             contains) is emitted (int), followed by all of its
743       * elements (each an Object) in the proper order.
744       */
745      private void writeObject(java.io.ObjectOutputStream s)
746          throws java.io.IOException {
747 <        // Write out any hidden serialization magic
748 <        s.defaultWriteObject();
747 >        // Write out any hidden serialization magic
748 >        s.defaultWriteObject();
749  
750          // Write out size
751          s.writeInt(size);
752  
753 <        // Write out all elements in the proper order.
753 >        // Write out all elements in the proper order.
754          for (Entry e = header.next; e != header; e = e.next)
755              s.writeObject(e.element);
756      }
# Line 755 | Line 761 | public class LinkedList<E>
761       */
762      private void readObject(java.io.ObjectInputStream s)
763          throws java.io.IOException, ClassNotFoundException {
764 <        // Read in any hidden serialization magic
765 <        s.defaultReadObject();
764 >        // Read in any hidden serialization magic
765 >        s.defaultReadObject();
766  
767          // Read in size
768          int size = s.readInt();
# Line 765 | Line 771 | public class LinkedList<E>
771          header = new Entry<E>(null, null, null);
772          header.next = header.previous = header;
773  
774 <        // Read in all elements in the proper order.
775 <        for (int i=0; i<size; i++)
774 >        // Read in all elements in the proper order.
775 >        for (int i=0; i<size; i++)
776              addBefore((E)s.readObject(), header);
777      }
778   }

Diff Legend

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