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.10 by dl, Sun Oct 19 13:38:29 2003 UTC vs.
Revision 1.17 by dl, Tue Dec 28 12:14:07 2004 UTC

# Line 1 | Line 1
1   /*
2   * %W% %E%
3   *
4 < * Copyright 2003 Sun Microsystems, Inc. All rights reserved.
4 > * Copyright 2004 Sun Microsystems, Inc. All rights reserved.
5   * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
6   */
7  
8 < package java.util;
8 > package java.util;
9  
10   /**
11   * Linked list implementation of the <tt>List</tt> interface.  Implements all
# 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, queue, or double-ended queue ({@link Deque}).<p>
18   *
19 < * The class implements the <tt>Queue</tt> interface, providing
19 > * The class implements the <tt>Deque</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>
21 > * <tt>poll</tt>, along with other stack and deque operations.
22   *
23   * All of the operations perform as could be expected for a doubly-linked
24   * list.  Operations that index into the list will traverse the list from
# Line 73 | Line 70 | package java.util;
70  
71   public class LinkedList<E>
72      extends AbstractSequentialList<E>
73 <    implements List<E>, Queue<E>, Cloneable, java.io.Serializable
73 >    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
74   {
75      private transient Entry<E> header = new Entry<E>(null, null, null);
76      private transient int size = 0;
# Line 131 | Line 128 | public class LinkedList<E>
128       * @throws    NoSuchElementException if this list is empty.
129       */
130      public E removeFirst() {
131 <        E first = header.next.element;
135 <        remove(header.next);
136 <        return first;
131 >        return remove(header.next);
132      }
133  
134      /**
# Line 143 | Line 138 | public class LinkedList<E>
138       * @throws    NoSuchElementException if this list is empty.
139       */
140      public E removeLast() {
141 <        E last = header.previous.element;
147 <        remove(header.previous);
148 <        return last;
141 >        return remove(header.previous);
142      }
143  
144      /**
# Line 289 | Line 282 | public class LinkedList<E>
282       * Removes all of the elements from this list.
283       */
284      public void clear() {
285 <        modCount++;
285 >        Entry<E> e = header.next;
286 >        while (e != header) {
287 >            Entry<E> next = e.next;
288 >            e.next = e.previous = null;
289 >            e.element = null;
290 >            e = next;
291 >        }
292          header.next = header.previous = header;
293 <        size = 0;
293 >        size = 0;
294 >        modCount++;
295      }
296  
297  
# Line 303 | Line 303 | public class LinkedList<E>
303       * @param index index of element to return.
304       * @return the element at the specified position in this list.
305       *
306 <     * @throws IndexOutOfBoundsException if the specified index is is out of
306 >     * @throws IndexOutOfBoundsException if the specified index is out of
307       * range (<tt>index &lt; 0 || index &gt;= size()</tt>).
308       */
309      public E get(int index) {
# Line 354 | Line 354 | public class LinkedList<E>
354       *            range (<tt>index &lt; 0 || index &gt;= size()</tt>).
355       */
356      public E remove(int index) {
357 <        Entry<E> e = entry(index);
358 <        remove(e);
359 <        return e.element;
357 >        return remove(entry(index));
358      }
359  
360      /**
# Line 487 | Line 485 | public class LinkedList<E>
485      /**
486       * Adds the specified element as the tail (last element) of this list.
487       *
488 <     * @param x the element to add.
488 >     * @param o the element to add.
489       * @return <tt>true</tt> (as per the general contract of
490       * <tt>Queue.offer</tt>)
491       * @since 1.5
492       */
493 <    public boolean offer(E x) {
494 <        return add(x);
493 >    public boolean offer(E o) {
494 >        return add(o);
495 >    }
496 >
497 >    // Deque operations
498 >    /**
499 >     * Inserts the specified element to the front this deque.
500 >     *
501 >     * @param e the element to insert
502 >     * @return <tt>true</tt> (as per the spec for {@link Deque#offerFirst})
503 >     * @since 1.6
504 >     */
505 >    public boolean offerFirst(E e) {
506 >        addFirst(e);
507 >        return true;
508 >    }
509 >
510 >    /**
511 >     * Inserts the specified element to the end this deque.
512 >     *
513 >     * @param e the element to insert
514 >     * @return <tt>true</tt> (as per the spec for {@link Deque#offerLast})
515 >     * @since 1.6
516 >     */
517 >    public boolean offerLast(E e) {
518 >        addLast(e);
519 >        return true;
520 >    }
521 >
522 >    /**
523 >     * Retrieves, but does not remove, the first element of this deque,
524 >     * returning <tt>null</tt> if this deque is empty.
525 >     *
526 >     * @return the first element of this deque, or <tt>null</tt> if
527 >     *     this deque is empty
528 >     * @since 1.6
529 >     */
530 >    public E peekFirst() {
531 >        if (size==0)
532 >            return null;
533 >        return removeFirst();
534 >    }
535 >
536 >    /**
537 >     * Retrieves, but does not remove, the last element of this deque,
538 >     * returning <tt>null</tt> if this deque is empty.
539 >     *
540 >     * @return the last element of this deque, or <tt>null</tt> if this deque
541 >     *     is empty
542 >     * @since 1.6
543 >     */
544 >    public E peekLast() {
545 >        if (size==0)
546 >            return null;
547 >        return removeLast();
548 >    }
549 >
550 >    /**
551 >     * Retrieves and removes the first element of this deque, or
552 >     * <tt>null</tt> if this deque is empty.
553 >     *
554 >     * @return the first element of this deque, or <tt>null</tt> if
555 >     *     this deque is empty
556 >     * @since 1.6
557 >     */
558 >    public E pollFirst() {
559 >        if (size==0)
560 >            return null;
561 >        return removeFirst();
562 >    }
563 >
564 >    /**
565 >     * Retrieves and removes the last element of this deque, or
566 >     * <tt>null</tt> if this deque is empty.
567 >     *
568 >     * @return the last element of this deque, or <tt>null</tt> if
569 >     *     this deque is empty
570 >     * @since 1.6
571 >     */
572 >    public E pollLast() {
573 >        if (size==0)
574 >            return null;
575 >        return removeLast();
576 >    }
577 >
578 >    /**
579 >     * Pushes an element onto the stack represented by this deque.  In other
580 >     * words, inserts the element to the front this deque.
581 >     *
582 >     * <p>This method is equivalent to {@link #addFirst}.
583 >     *
584 >     * @param e the element to push
585 >     * @since 1.6
586 >     */
587 >    public void push(E e) {
588 >        addFirst(e);
589 >    }
590 >
591 >    /**
592 >     * Pops an element from the stack represented by this deque.  In other
593 >     * words, removes and returns the the first element of this deque.
594 >     *
595 >     * <p>This method is equivalent to {@link #removeFirst()}.
596 >     *
597 >     * @return the element at the front of this deque (which is the top
598 >     *     of the stack represented by this deque)
599 >     * @throws NoSuchElementException if this deque is empty
600 >     * @since 1.6
601 >     */
602 >    public E pop() {
603 >        return removeFirst();
604 >    }
605 >
606 >    /**
607 >     * Removes the first occurrence of the specified element in this
608 >     * deque (when traversing the deque from head to tail).  If the deque
609 >     * does not contain the element, it is unchanged.
610 >     *
611 >     * @param e element to be removed from this deque, if present
612 >     * @return <tt>true</tt> if the deque contained the specified element
613 >     * @since 1.6
614 >     */
615 >    public boolean removeFirstOccurrence(Object e) {
616 >        return remove(e);
617 >    }
618 >
619 >    /**
620 >     * Removes the last occurrence of the specified element in this
621 >     * deque (when traversing the deque from head to tail).  If the deque
622 >     * does not contain the element, it is unchanged.
623 >     *
624 >     * @param o element to be removed from this deque, if present
625 >     * @return <tt>true</tt> if the deque contained the specified element
626 >     * @since 1.6
627 >     */
628 >    public boolean removeLastOccurrence(Object o) {
629 >        if (o==null) {
630 >            for (Entry e = header.previous; e != header; e = e.previous) {
631 >                if (e.element==null) {
632 >                    remove(e);
633 >                    return true;
634 >                }
635 >            }
636 >        } else {
637 >            for (Entry e = header.previous; e != header; e = e.previous) {
638 >                if (o.equals(e.element)) {
639 >                    remove(e);
640 >                    return true;
641 >                }
642 >            }
643 >        }
644 >        return false;
645      }
646  
647      /**
# Line 582 | Line 730 | public class LinkedList<E>
730  
731          public void remove() {
732              checkForComodification();
733 +            Entry<E> lastNext = lastReturned.next;
734              try {
735                  LinkedList.this.remove(lastReturned);
736              } catch (NoSuchElementException e) {
737                  throw new IllegalStateException();
738              }
739              if (next==lastReturned)
740 <                next = lastReturned.next;
740 >                next = lastNext;
741              else
742                  nextIndex--;
743              lastReturned = header;
# Line 637 | Line 786 | public class LinkedList<E>
786          return newEntry;
787      }
788  
789 <    private void remove(Entry<E> e) {
789 >    private E remove(Entry<E> e) {
790          if (e == header)
791              throw new NoSuchElementException();
792  
793 +        E result = e.element;
794          e.previous.next = e.next;
795          e.next.previous = e.previous;
796 +        e.next = e.previous = null;
797 +        e.element = null;
798          size--;
799          modCount++;
800 +        return result;
801      }
802  
803      /**

Diff Legend

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