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.5 by dl, Sun Aug 31 13:33:06 2003 UTC vs.
Revision 1.25 by jsr166, Mon May 2 06:06:17 2005 UTC

# Line 1 | Line 1
1   /*
2 < * @(#)LinkedList.java  1.53 03/06/22
2 > * %W% %E%
3   *
4 < * Copyright 2003 Sun Microsystems, Inc. All rights reserved.
4 > * Copyright 2005 Sun Microsystems, Inc. All rights reserved.
5   * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
6   */
7  
# Line 14 | Line 14 | package java.util;
14   * the <tt>LinkedList</tt> class provides uniformly named methods to
15   * <tt>get</tt>, <tt>remove</tt> and <tt>insert</tt> an element at the
16   * beginning and end of the list.  These operations allow linked lists to be
17 < * used as a stack, queue, or double-ended queue (deque).<p>
17 > * used as a stack, {@linkplain Queue queue}, or {@linkplain Deque
18 > * double-ended queue}. <p>
19   *
20 < * The class implements the <tt>Queue</tt> interface, providing
20 > * The class implements the <tt>Deque</tt> interface, providing
21   * first-in-first-out queue operations for <tt>add</tt>,
22 < * <tt>poll</tt>, etc. Other stack and deque operations could be
22 < * easily recast in terms of the standard list operations.  They're
23 < * included here primarily for convenience, though they may run
24 < * slightly faster than the equivalent List operations.<p>
22 > * <tt>poll</tt>, along with other stack and deque operations.<p>
23   *
24   * All of the operations perform as could be expected for a doubly-linked
25   * list.  Operations that index into the list will traverse the list from
26 < * the begining or the end, whichever is closer to the specified index.<p>
26 > * the beginning or the end, whichever is closer to the specified index.<p>
27   *
28   * <b>Note that this implementation is not synchronized.</b> If multiple
29   * threads access a list concurrently, and at least one of the threads
# Line 38 | Line 36 | package java.util;
36   * Collections.synchronizedList method.  This is best done at creation time,
37   * to prevent accidental unsynchronized access to the list: <pre>
38   *     List list = Collections.synchronizedList(new LinkedList(...));
39 < * </pre><p>
39 > * </pre>
40   *
41 < * The iterators returned by the this class's <tt>iterator</tt> and
41 > * <p>The iterators returned by this class's <tt>iterator</tt> and
42   * <tt>listIterator</tt> methods are <i>fail-fast</i>: if the list is
43 < * structurally modified at any time after the iterator is created, in any way
44 < * except through the Iterator's own <tt>remove</tt> or <tt>add</tt> methods,
45 < * the iterator will throw a <tt>ConcurrentModificationException</tt>.  Thus,
46 < * in the face of concurrent modification, the iterator fails quickly and
47 < * cleanly, rather than risking arbitrary, non-deterministic behavior at an
48 < * undetermined time in the future.
43 > * structurally modified at any time after the iterator is created, in
44 > * any way except through the Iterator's own <tt>remove</tt> or
45 > * <tt>add</tt> methods, the iterator will throw a {@link
46 > * ConcurrentModificationException}.  Thus, in the face of concurrent
47 > * modification, the iterator fails quickly and cleanly, rather than
48 > * risking arbitrary, non-deterministic behavior at an undetermined
49 > * time in the future.
50   *
51   * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
52   * as it is, generally speaking, impossible to make any hard guarantees in the
# Line 55 | Line 54 | package java.util;
54   * throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
55   * Therefore, it would be wrong to write a program that depended on this
56   * exception for its correctness:   <i>the fail-fast behavior of iterators
57 < * should be used only to detect bugs.</i><p>
57 > * should be used only to detect bugs.</i>
58   *
59 < * This class is a member of the
59 > * <p>This class is a member of the
60   * <a href="{@docRoot}/../guide/collections/index.html">
61   * Java Collections Framework</a>.
62   *
63   * @author  Josh Bloch
64 < * @version 1.53, 06/22/03
64 > * @version %I%, %G%
65   * @see     List
66   * @see     ArrayList
67   * @see     Vector
68   * @see     Collections#synchronizedList(List)
69   * @since 1.2
70 + * @param <E> the type of elements held in this collection
71   */
72  
73   public class LinkedList<E>
74      extends AbstractSequentialList<E>
75 <    implements List<E>, Queue<E>, Cloneable, java.io.Serializable
75 >    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
76   {
77      private transient Entry<E> header = new Entry<E>(null, null, null);
78      private transient int size = 0;
# Line 130 | 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;
134 <        remove(header.next);
135 <        return first;
133 >        return remove(header.next);
134      }
135  
136      /**
# Line 142 | 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;
146 <        remove(header.previous);
147 <        return last;
143 >        return remove(header.previous);
144      }
145  
146      /**
147       * Inserts the given element at the beginning of this list.
148       *
149 <     * @param o the element to be inserted at the beginning of this list.
149 >     * @param e the element to be inserted at the beginning of this list.
150       */
151 <    public void addFirst(E o) {
152 <        addBefore(o, header.next);
151 >    public void addFirst(E e) {
152 >        addBefore(e, header.next);
153      }
154  
155      /**
156       * Appends the given element to the end of this list.  (Identical in
157       * function to the <tt>add</tt> method; included only for consistency.)
158       *
159 <     * @param o the element to be inserted at the end of this list.
159 >     * @param e the element to be inserted at the end of this list.
160       */
161 <    public void addLast(E o) {
162 <        addBefore(o, header);
161 >    public void addLast(E e) {
162 >        addBefore(e, header);
163      }
164  
165      /**
# Line 257 | 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 288 | 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 302 | 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 316 | 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 334 | 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 349 | 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);
357 <        remove(e);
358 <        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 442 | Line 443 | public class LinkedList<E>
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.
446 >     * Retrieves, but does not remove, the head (first element) of this list.
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() {
451          if (size==0)
# Line 452 | Line 454 | public class LinkedList<E>
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.
457 >     * Retrieves, but does not remove, the head (first element) of this list.
458 >     * @return the head of this list.
459 >     * @throws NoSuchElementException if this list 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.
467 >     * Retrieves and removes the head (first element) of this list.
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() {
472          if (size==0)
# Line 471 | Line 475 | public class LinkedList<E>
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.
478 >     * Retrieves and removes the head (first element) of this list.
479 >     * @return the head of this list.
480 >     * @throws NoSuchElementException if this list is empty.
481 >     * @since 1.5
482       */
483      public E remove() {
484          return removeFirst();
# Line 482 | Line 487 | public class LinkedList<E>
487      /**
488       * Adds the specified element as the tail (last element) of this list.
489       *
490 <     * @param x the element to add.
490 >     * @param o 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 o) {
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 offer(E x) {
618 <        return add(x);
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      /**
# Line 508 | 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 576 | 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 631 | 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