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.24 by jsr166, Tue Apr 26 19:54:03 2005 UTC

# Line 1 | Line 1
1   /*
2   * %W% %E%
3   *
4 < * Copyright 2003 Sun Microsystems, Inc. All rights reserved.
4 > * Copyright 2005 Sun Microsystems, Inc. All rights reserved.
5   * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
6   */
7  
# Line 14 | Line 14 | package java.util;
14   * the <tt>LinkedList</tt> class provides uniformly named methods to
15   * <tt>get</tt>, <tt>remove</tt> and <tt>insert</tt> an element at the
16   * beginning and end of the list.  These operations allow linked lists to be
17 < * used as a stack, queue, or double-ended queue (deque).<p>
17 > * used as a stack, {@linkplain Queue queue}, or {@linkplain Deque
18 > * double-ended queue}. <p>
19   *
20 < * The class implements the <tt>Queue</tt> interface, providing
20 > * The class implements the <tt>Deque</tt> interface, providing
21   * first-in-first-out queue operations for <tt>add</tt>,
22 < * <tt>poll</tt>, etc. Other stack and deque operations could be
22 < * easily recast in terms of the standard list operations.  They're
23 < * included here primarily for convenience, though they may run
24 < * slightly faster than the equivalent List operations.<p>
22 > * <tt>poll</tt>, along with other stack and deque operations.<p>
23   *
24   * All of the operations perform as could be expected for a doubly-linked
25   * list.  Operations that index into the list will traverse the list from
# Line 38 | Line 36 | package java.util;
36   * Collections.synchronizedList method.  This is best done at creation time,
37   * to prevent accidental unsynchronized access to the list: <pre>
38   *     List list = Collections.synchronizedList(new LinkedList(...));
39 < * </pre><p>
39 > * </pre>
40   *
41 < * The iterators returned by the this class's <tt>iterator</tt> and
41 > * <p>The iterators returned by this class's <tt>iterator</tt> and
42   * <tt>listIterator</tt> methods are <i>fail-fast</i>: if the list is
43 < * structurally modified at any time after the iterator is created, in any way
44 < * except through the Iterator's own <tt>remove</tt> or <tt>add</tt> methods,
45 < * the iterator will throw a <tt>ConcurrentModificationException</tt>.  Thus,
46 < * in the face of concurrent modification, the iterator fails quickly and
47 < * cleanly, rather than risking arbitrary, non-deterministic behavior at an
48 < * undetermined time in the future.
43 > * structurally modified at any time after the iterator is created, in
44 > * any way except through the Iterator's own <tt>remove</tt> or
45 > * <tt>add</tt> methods, the iterator will throw a {@link
46 > * ConcurrentModificationException}.  Thus, in the face of concurrent
47 > * modification, the iterator fails quickly and cleanly, rather than
48 > * risking arbitrary, non-deterministic behavior at an undetermined
49 > * time in the future.
50   *
51   * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
52   * as it is, generally speaking, impossible to make any hard guarantees in the
# Line 55 | Line 54 | package java.util;
54   * throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
55   * Therefore, it would be wrong to write a program that depended on this
56   * exception for its correctness:   <i>the fail-fast behavior of iterators
57 < * should be used only to detect bugs.</i><p>
57 > * should be used only to detect bugs.</i>
58   *
59 < * This class is a member of the
59 > * <p>This class is a member of the
60   * <a href="{@docRoot}/../guide/collections/index.html">
61   * Java Collections Framework</a>.
62   *
# Line 73 | Line 72 | package java.util;
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 131 | Line 130 | public class LinkedList<E>
130       * @throws    NoSuchElementException if this list is empty.
131       */
132      public E removeFirst() {
133 <        E first = header.next.element;
135 <        remove(header.next);
136 <        return first;
133 >        return remove(header.next);
134      }
135  
136      /**
# Line 143 | Line 140 | public class LinkedList<E>
140       * @throws    NoSuchElementException if this list is empty.
141       */
142      public E removeLast() {
143 <        E last = header.previous.element;
147 <        remove(header.previous);
148 <        return last;
143 >        return remove(header.previous);
144      }
145  
146      /**
# Line 258 | Line 253 | public class LinkedList<E>
253       *              from the specified collection.
254       * @param c elements to be inserted into this list.
255       * @return <tt>true</tt> if this list changed as a result of the call.
256 <     * @throws IndexOutOfBoundsException if the specified index is out of
257 <     *            range (<tt>index &lt; 0 || index &gt; size()</tt>).
256 >     * @throws IndexOutOfBoundsException if the index is out of range
257 >     *         (<tt>index &lt; 0 || index &gt; size()</tt>).
258       * @throws NullPointerException if the specified collection is null.
259       */
260      public boolean addAll(int index, Collection<? extends E> c) {
# Line 289 | Line 284 | public class LinkedList<E>
284       * Removes all of the elements from this list.
285       */
286      public void clear() {
287 <        modCount++;
287 >        Entry<E> e = header.next;
288 >        while (e != header) {
289 >            Entry<E> next = e.next;
290 >            e.next = e.previous = null;
291 >            e.element = null;
292 >            e = next;
293 >        }
294          header.next = header.previous = header;
295 <        size = 0;
295 >        size = 0;
296 >        modCount++;
297      }
298  
299  
# Line 303 | Line 305 | public class LinkedList<E>
305       * @param index index of element to return.
306       * @return the element at the specified position in this list.
307       *
308 <     * @throws IndexOutOfBoundsException if the specified index is is out of
309 <     * range (<tt>index &lt; 0 || index &gt;= size()</tt>).
308 >     * @throws IndexOutOfBoundsException if the index is out of range
309 >     *         (<tt>index &lt; 0 || index &gt; size()</tt>).
310       */
311      public E get(int index) {
312          return entry(index).element;
# Line 317 | Line 319 | public class LinkedList<E>
319       * @param index index of element to replace.
320       * @param element element to be stored at the specified position.
321       * @return the element previously at the specified position.
322 <     * @throws IndexOutOfBoundsException if the specified index is out of
323 <     *            range (<tt>index &lt; 0 || index &gt;= size()</tt>).
322 >     * @throws IndexOutOfBoundsException if the index is out of range
323 >     *         (<tt>index &lt; 0 || index &gt; size()</tt>).
324       */
325      public E set(int index, E element) {
326          Entry<E> e = entry(index);
# Line 335 | Line 337 | public class LinkedList<E>
337       * @param index index at which the specified element is to be inserted.
338       * @param element element to be inserted.
339       *
340 <     * @throws IndexOutOfBoundsException if the specified index is out of
341 <     *            range (<tt>index &lt; 0 || index &gt; size()</tt>).
340 >     * @throws IndexOutOfBoundsException if the index is out of range
341 >     *         (<tt>index &lt; 0 || index &gt; size()</tt>).
342       */
343      public void add(int index, E element) {
344          addBefore(element, (index==size ? header : entry(index)));
# Line 350 | Line 352 | public class LinkedList<E>
352       * @param index the index of the element to removed.
353       * @return the element previously at the specified position.
354       *
355 <     * @throws IndexOutOfBoundsException if the specified index is out of
356 <     *            range (<tt>index &lt; 0 || index &gt;= size()</tt>).
355 >     * @throws IndexOutOfBoundsException if the index is out of range
356 >     *         (<tt>index &lt; 0 || index &gt; size()</tt>).
357       */
358      public E remove(int index) {
359 <        Entry<E> e = entry(index);
358 <        remove(e);
359 <        return e.element;
359 >        return remove(entry(index));
360      }
361  
362      /**
363 <     * Return the indexed entry.
363 >     * Returns the indexed entry.
364       */
365      private Entry<E> entry(int index) {
366          if (index < 0 || index >= size)
# Line 444 | Line 444 | public class LinkedList<E>
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.
447 >     * @return the head of this list, or <tt>null</tt> if this list is empty.
448       * @since 1.5
449       */
450      public E peek() {
# Line 455 | Line 455 | public class LinkedList<E>
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.
458 >     * @return the head of this list.
459 >     * @throws NoSuchElementException if this list is empty.
460       * @since 1.5
461       */
462      public E element() {
# Line 465 | Line 465 | public class LinkedList<E>
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.
468 >     * @return the head of this list, or <tt>null</tt> if this list is empty.
469       * @since 1.5
470       */
471      public E poll() {
# Line 476 | Line 476 | public class LinkedList<E>
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.
479 >     * @return the head of this list.
480 >     * @throws NoSuchElementException if this list is empty.
481       * @since 1.5
482       */
483      public E remove() {
# Line 496 | Line 496 | public class LinkedList<E>
496          return add(o);
497      }
498  
499 +    // Deque operations
500 +    /**
501 +     * Inserts the specified element at the front of this list.
502 +     *
503 +     * @param e the element to insert
504 +     * @return <tt>true</tt> (as per the spec for {@link Deque#offerFirst})
505 +     * @since 1.6
506 +     */
507 +    public boolean offerFirst(E e) {
508 +        addFirst(e);
509 +        return true;
510 +    }
511 +
512 +    /**
513 +     * Inserts the specified element at the end of this list.
514 +     *
515 +     * @param e the element to insert
516 +     * @return <tt>true</tt> (as per the spec for {@link Deque#offerLast})
517 +     * @since 1.6
518 +     */
519 +    public boolean offerLast(E e) {
520 +        addLast(e);
521 +        return true;
522 +    }
523 +
524 +    /**
525 +     * Retrieves, but does not remove, the first element of this list,
526 +     * returning <tt>null</tt> if this list is empty.
527 +     *
528 +     * @return the first element of this list, or <tt>null</tt> if
529 +     *     this list is empty
530 +     * @since 1.6
531 +     */
532 +    public E peekFirst() {
533 +        if (size==0)
534 +            return null;
535 +        return getFirst();
536 +    }
537 +
538 +    /**
539 +     * Retrieves, but does not remove, the last element of this list,
540 +     * returning <tt>null</tt> if this list is empty.
541 +     *
542 +     * @return the last element of this list, or <tt>null</tt> if this list
543 +     *     is empty
544 +     * @since 1.6
545 +     */
546 +    public E peekLast() {
547 +        if (size==0)
548 +            return null;
549 +        return getLast();
550 +    }
551 +
552 +    /**
553 +     * Retrieves and removes the first element of this list, or
554 +     * <tt>null</tt> if this list is empty.
555 +     *
556 +     * @return the first element of this list, or <tt>null</tt> if
557 +     *     this list is empty
558 +     * @since 1.6
559 +     */
560 +    public E pollFirst() {
561 +        if (size==0)
562 +            return null;
563 +        return removeFirst();
564 +    }
565 +
566 +    /**
567 +     * Retrieves and removes the last element of this list, or
568 +     * <tt>null</tt> if this list is empty.
569 +     *
570 +     * @return the last element of this list, or <tt>null</tt> if
571 +     *     this list is empty
572 +     * @since 1.6
573 +     */
574 +    public E pollLast() {
575 +        if (size==0)
576 +            return null;
577 +        return removeLast();
578 +    }
579 +
580 +    /**
581 +     * Pushes an element onto the stack represented by this list.  In other
582 +     * words, inserts the element at the front of this list.
583 +     *
584 +     * <p>This method is equivalent to {@link #addFirst}.
585 +     *
586 +     * @param e the element to push
587 +     * @since 1.6
588 +     */
589 +    public void push(E e) {
590 +        addFirst(e);
591 +    }
592 +
593 +    /**
594 +     * Pops an element from the stack represented by this list.  In other
595 +     * words, removes and returns the first element of this list.
596 +     *
597 +     * <p>This method is equivalent to {@link #removeFirst()}.
598 +     *
599 +     * @return the element at the front of this list (which is the top
600 +     *     of the stack represented by this list)
601 +     * @throws NoSuchElementException if this list is empty.
602 +     * @since 1.6
603 +     */
604 +    public E pop() {
605 +        return removeFirst();
606 +    }
607 +
608 +    /**
609 +     * Removes the first occurrence of the specified element in this
610 +     * list (when traversing the list from head to tail).  If the list
611 +     * does not contain the element, it is unchanged.
612 +     *
613 +     * @param o element to be removed from this list, if present
614 +     * @return <tt>true</tt> if the list contained the specified element
615 +     * @since 1.6
616 +     */
617 +    public boolean removeFirstOccurrence(Object o) {
618 +        return remove(o);
619 +    }
620 +
621 +    /**
622 +     * Removes the last occurrence of the specified element in this
623 +     * list (when traversing the list from head to tail).  If the list
624 +     * does not contain the element, it is unchanged.
625 +     *
626 +     * @param o element to be removed from this list, if present
627 +     * @return <tt>true</tt> if the list contained the specified element
628 +     * @since 1.6
629 +     */
630 +    public boolean removeLastOccurrence(Object o) {
631 +        if (o==null) {
632 +            for (Entry e = header.previous; e != header; e = e.previous) {
633 +                if (e.element==null) {
634 +                    remove(e);
635 +                    return true;
636 +                }
637 +            }
638 +        } else {
639 +            for (Entry e = header.previous; e != header; e = e.previous) {
640 +                if (o.equals(e.element)) {
641 +                    remove(e);
642 +                    return true;
643 +                }
644 +            }
645 +        }
646 +        return false;
647 +    }
648 +
649      /**
650       * Returns a list-iterator of the elements in this list (in proper
651       * sequence), starting at the specified position in the list.
# Line 514 | Line 664 | public class LinkedList<E>
664       *              list-iterator (by a call to <tt>next</tt>).
665       * @return a ListIterator of the elements in this list (in proper
666       *         sequence), starting at the specified position in the list.
667 <     * @throws    IndexOutOfBoundsException if index is out of range
668 <     *            (<tt>index &lt; 0 || index &gt; size()</tt>).
667 >     * @throws IndexOutOfBoundsException if the index is out of range
668 >     *         (<tt>index &lt; 0 || index &gt; size()</tt>).
669       * @see List#listIterator(int)
670       */
671      public ListIterator<E> listIterator(int index) {
# Line 582 | Line 732 | public class LinkedList<E>
732  
733          public void remove() {
734              checkForComodification();
735 +            Entry<E> lastNext = lastReturned.next;
736              try {
737                  LinkedList.this.remove(lastReturned);
738              } catch (NoSuchElementException e) {
739                  throw new IllegalStateException();
740              }
741              if (next==lastReturned)
742 <                next = lastReturned.next;
742 >                next = lastNext;
743              else
744                  nextIndex--;
745              lastReturned = header;
# Line 637 | Line 788 | public class LinkedList<E>
788          return newEntry;
789      }
790  
791 <    private void remove(Entry<E> e) {
791 >    private E remove(Entry<E> e) {
792          if (e == header)
793              throw new NoSuchElementException();
794  
795 +        E result = e.element;
796          e.previous.next = e.next;
797          e.next.previous = e.previous;
798 +        e.next = e.previous = null;
799 +        e.element = null;
800          size--;
801          modCount++;
802 +        return result;
803      }
804  
805      /**

Diff Legend

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