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.11 by jsr166, Tue Oct 21 05:11:40 2003 UTC vs.
Revision 1.12 by jozart, Mon Nov 17 08:05:59 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);
96 >    public LinkedList(Collection<? extends E> c) {
97 >        this();
98 >        addAll(c);
99       }
100  
101      /**
# 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 >        E first = header.next.element;
135 >        remove(header.next);
136 >        return first;
137      }
138  
139      /**
# Line 143 | Line 143 | public class LinkedList<E>
143       * @throws    NoSuchElementException if this list is empty.
144       */
145      public E removeLast() {
146 <        E last = header.previous.element;
147 <        remove(header.previous);
148 <        return last;
146 >        E last = header.previous.element;
147 >        remove(header.previous);
148 >        return last;
149      }
150  
151      /**
# Line 154 | Line 154 | public class LinkedList<E>
154       * @param o the element to be inserted at the beginning of this list.
155       */
156      public void addFirst(E o) {
157 <        addBefore(o, header.next);
157 >        addBefore(o, header.next);
158      }
159  
160      /**
# Line 164 | Line 164 | public class LinkedList<E>
164       * @param o the element to be inserted at the end of this list.
165       */
166      public void addLast(E o) {
167 <        addBefore(o, header);
167 >        addBefore(o, header);
168      }
169  
170      /**
# Line 186 | Line 186 | public class LinkedList<E>
186       * @return the number of elements in this list.
187       */
188      public int size() {
189 <        return size;
189 >        return size;
190      }
191  
192      /**
# Line 197 | Line 197 | public class LinkedList<E>
197       * <tt>Collection.add</tt>).
198       */
199      public boolean add(E o) {
200 <        addBefore(o, header);
200 >        addBefore(o, header);
201          return true;
202      }
203  
# Line 255 | Line 255 | public class LinkedList<E>
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
# Line 270 | Line 270 | public class LinkedList<E>
270          int numNew = a.length;
271          if (numNew==0)
272              return false;
273 <        modCount++;
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++) {
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;
# Line 289 | Line 289 | public class LinkedList<E>
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 318 | Line 318 | public class LinkedList<E>
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 E set(int index, E element) {
324          Entry<E> e = entry(index);
# Line 336 | Line 336 | public class LinkedList<E>
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>).
339 >     *            range (<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 351 | Line 351 | public class LinkedList<E>
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>).
354 >     *            range (<tt>index &lt; 0 || index &gt;= size()</tt>).
355       */
356      public E remove(int index) {
357          Entry<E> e = entry(index);
# Line 389 | Line 389 | public class LinkedList<E>
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 419 | Line 419 | public class LinkedList<E>
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 511 | Line 511 | public class LinkedList<E>
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>).
518 >     *            (<tt>index &lt; 0 || index &gt; size()</tt>).
519       * @see List#listIterator(int)
520       */
521      public ListIterator<E> listIterator(int index) {
522 <        return new ListItr(index);
522 >        return new ListItr(index);
523      }
524  
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 <        }
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 void remove() {
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 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(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 <        }
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 <        }
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;
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();
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++;
644 >        e.previous.next = e.next;
645 >        e.next.previous = e.previous;
646 >        size--;
647 >        modCount++;
648      }
649  
650      /**
# Line 655 | Line 655 | public class LinkedList<E>
655       */
656      public Object clone() {
657          LinkedList<E> clone = null;
658 <        try {
659 <            clone = (LinkedList<E>) super.clone();
660 <        } catch (CloneNotSupportedException e) {
661 <            throw new InternalError();
662 <        }
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<E>(null, null, null);
# Line 679 | Line 679 | public class LinkedList<E>
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> e = header.next; e != header; e = e.next)
688              result[i++] = e.element;
689 <        return result;
689 >        return result;
690      }
691  
692      /**
# Line 704 | Line 704 | public class LinkedList<E>
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.
# Line 716 | Line 716 | public class LinkedList<E>
716              a = (T[])java.lang.reflect.Array.newInstance(
717                                  a.getClass().getComponentType(), size);
718          int i = 0;
719 <        Object[] result = a;
719 >        Object[] result = a;
720          for (Entry<E> e = header.next; e != header; e = e.next)
721              result[i++] = e.element;
722  
# Line 733 | Line 733 | public class LinkedList<E>
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
736 >     *             contains) is emitted (int), followed by all of its
737       * elements (each an Object) in the proper order.
738       */
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 755 | Line 755 | public class LinkedList<E>
755       */
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();
# Line 765 | Line 765 | public class LinkedList<E>
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++)
768 >        // Read in all elements in the proper order.
769 >        for (int i=0; i<size; i++)
770              addBefore((E)s.readObject(), header);
771      }
772   }

Diff Legend

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