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.19 by dl, Tue Mar 1 01:27:15 2005 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, {@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.
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 73 | Line 71 | package java.util;
71  
72   public class LinkedList<E>
73      extends AbstractSequentialList<E>
74 <    implements List<E>, Queue<E>, Cloneable, java.io.Serializable
74 >    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
75   {
76      private transient Entry<E> header = new Entry<E>(null, null, null);
77      private transient int size = 0;
# Line 131 | Line 129 | public class LinkedList<E>
129       * @throws    NoSuchElementException if this list is empty.
130       */
131      public E removeFirst() {
132 <        E first = header.next.element;
135 <        remove(header.next);
136 <        return first;
132 >        return remove(header.next);
133      }
134  
135      /**
# Line 143 | Line 139 | public class LinkedList<E>
139       * @throws    NoSuchElementException if this list is empty.
140       */
141      public E removeLast() {
142 <        E last = header.previous.element;
147 <        remove(header.previous);
148 <        return last;
142 >        return remove(header.previous);
143      }
144  
145      /**
# Line 289 | Line 283 | public class LinkedList<E>
283       * Removes all of the elements from this list.
284       */
285      public void clear() {
286 <        modCount++;
286 >        Entry<E> e = header.next;
287 >        while (e != header) {
288 >            Entry<E> next = e.next;
289 >            e.next = e.previous = null;
290 >            e.element = null;
291 >            e = next;
292 >        }
293          header.next = header.previous = header;
294 <        size = 0;
294 >        size = 0;
295 >        modCount++;
296      }
297  
298  
# Line 303 | Line 304 | public class LinkedList<E>
304       * @param index index of element to return.
305       * @return the element at the specified position in this list.
306       *
307 <     * @throws IndexOutOfBoundsException if the specified index is is out of
307 >     * @throws IndexOutOfBoundsException if the specified index is out of
308       * range (<tt>index &lt; 0 || index &gt;= size()</tt>).
309       */
310      public E get(int index) {
# Line 354 | Line 355 | public class LinkedList<E>
355       *            range (<tt>index &lt; 0 || index &gt;= size()</tt>).
356       */
357      public E remove(int index) {
358 <        Entry<E> e = entry(index);
358 <        remove(e);
359 <        return e.element;
358 >        return remove(entry(index));
359      }
360  
361      /**
# Line 444 | Line 443 | public class LinkedList<E>
443  
444      /**
445       * Retrieves, but does not remove, the head (first element) of this list.
446 <     * @return the head of this queue, or <tt>null</tt> if this queue is empty.
446 >     * @return the head of this list, or <tt>null</tt> if this list is empty.
447       * @since 1.5
448       */
449      public E peek() {
# Line 455 | Line 454 | public class LinkedList<E>
454  
455      /**
456       * Retrieves, but does not remove, the head (first element) of this list.
457 <     * @return the head of this queue.
458 <     * @throws NoSuchElementException if this queue is empty.
457 >     * @return the head of this list.
458 >     * @throws NoSuchElementException if this list is empty.
459       * @since 1.5
460       */
461      public E element() {
# Line 465 | Line 464 | public class LinkedList<E>
464  
465      /**
466       * Retrieves and removes the head (first element) of this list.
467 <     * @return the head of this queue, or <tt>null</tt> if this queue is empty.
467 >     * @return the head of this list, or <tt>null</tt> if this list is empty.
468       * @since 1.5
469       */
470      public E poll() {
# Line 476 | Line 475 | public class LinkedList<E>
475  
476      /**
477       * Retrieves and removes the head (first element) of this list.
478 <     * @return the head of this queue.
479 <     * @throws NoSuchElementException if this queue is empty.
478 >     * @return the head of this list.
479 >     * @throws NoSuchElementException if this list is empty.
480       * @since 1.5
481       */
482      public E remove() {
# Line 487 | Line 486 | public class LinkedList<E>
486      /**
487       * Adds the specified element as the tail (last element) of this list.
488       *
489 <     * @param x the element to add.
489 >     * @param o the element to add.
490       * @return <tt>true</tt> (as per the general contract of
491       * <tt>Queue.offer</tt>)
492       * @since 1.5
493       */
494 <    public boolean offer(E x) {
495 <        return add(x);
494 >    public boolean offer(E o) {
495 >        return add(o);
496 >    }
497 >
498 >    // Deque operations
499 >    /**
500 >     * Inserts the specified element to the front of this list.
501 >     *
502 >     * @param e the element to insert
503 >     * @return <tt>true</tt> (as per the spec for {@link Deque#offerFirst})
504 >     * @since 1.6
505 >     */
506 >    public boolean offerFirst(E e) {
507 >        addFirst(e);
508 >        return true;
509 >    }
510 >
511 >    /**
512 >     * Inserts the specified element to the end of this list.
513 >     *
514 >     * @param e the element to insert
515 >     * @return <tt>true</tt> (as per the spec for {@link Deque#offerLast})
516 >     * @since 1.6
517 >     */
518 >    public boolean offerLast(E e) {
519 >        addLast(e);
520 >        return true;
521 >    }
522 >
523 >    /**
524 >     * Retrieves, but does not remove, the first element of this list,
525 >     * returning <tt>null</tt> if this list is empty.
526 >     *
527 >     * @return the first element of this list, or <tt>null</tt> if
528 >     *     this list is empty
529 >     * @since 1.6
530 >     */
531 >    public E peekFirst() {
532 >        if (size==0)
533 >            return null;
534 >        return getFirst();
535 >    }
536 >
537 >    /**
538 >     * Retrieves, but does not remove, the last element of this list,
539 >     * returning <tt>null</tt> if this list is empty.
540 >     *
541 >     * @return the last element of this list, or <tt>null</tt> if this list
542 >     *     is empty
543 >     * @since 1.6
544 >     */
545 >    public E peekLast() {
546 >        if (size==0)
547 >            return null;
548 >        return getLast();
549 >    }
550 >
551 >    /**
552 >     * Retrieves and removes the first element of this list, or
553 >     * <tt>null</tt> if this list is empty.
554 >     *
555 >     * @return the first element of this list, or <tt>null</tt> if
556 >     *     this list is empty
557 >     * @since 1.6
558 >     */
559 >    public E pollFirst() {
560 >        if (size==0)
561 >            return null;
562 >        return removeFirst();
563 >    }
564 >
565 >    /**
566 >     * Retrieves and removes the last element of this list, or
567 >     * <tt>null</tt> if this list is empty.
568 >     *
569 >     * @return the last element of this list, or <tt>null</tt> if
570 >     *     this list is empty
571 >     * @since 1.6
572 >     */
573 >    public E pollLast() {
574 >        if (size==0)
575 >            return null;
576 >        return removeLast();
577 >    }
578 >
579 >    /**
580 >     * Pushes an element onto the stack represented by this list.  In other
581 >     * words, inserts the element to the front this list.
582 >     *
583 >     * <p>This method is equivalent to {@link #addFirst}.
584 >     *
585 >     * @param e the element to push
586 >     * @since 1.6
587 >     */
588 >    public void push(E e) {
589 >        addFirst(e);
590 >    }
591 >
592 >    /**
593 >     * Pops an element from the stack represented by this list.  In other
594 >     * words, removes and returns the the first element of this list.
595 >     *
596 >     * <p>This method is equivalent to {@link #removeFirst()}.
597 >     *
598 >     * @return the element at the front of this list (which is the top
599 >     *     of the stack represented by this list)
600 >     * @throws NoSuchElementException if this list is empty
601 >     * @since 1.6
602 >     */
603 >    public E pop() {
604 >        return removeFirst();
605 >    }
606 >
607 >    /**
608 >     * Removes the first occurrence of the specified element in this
609 >     * list (when traversing the list from head to tail).  If the list
610 >     * does not contain the element, it is unchanged.
611 >     *
612 >     * @param e element to be removed from this list, if present
613 >     * @return <tt>true</tt> if the list contained the specified element
614 >     * @since 1.6
615 >     */
616 >    public boolean removeFirstOccurrence(Object e) {
617 >        return remove(e);
618 >    }
619 >
620 >    /**
621 >     * Removes the last occurrence of the specified element in this
622 >     * list (when traversing the list from head to tail).  If the list
623 >     * does not contain the element, it is unchanged.
624 >     *
625 >     * @param o element to be removed from this list, if present
626 >     * @return <tt>true</tt> if the list contained the specified element
627 >     * @since 1.6
628 >     */
629 >    public boolean removeLastOccurrence(Object o) {
630 >        if (o==null) {
631 >            for (Entry e = header.previous; e != header; e = e.previous) {
632 >                if (e.element==null) {
633 >                    remove(e);
634 >                    return true;
635 >                }
636 >            }
637 >        } else {
638 >            for (Entry e = header.previous; e != header; e = e.previous) {
639 >                if (o.equals(e.element)) {
640 >                    remove(e);
641 >                    return true;
642 >                }
643 >            }
644 >        }
645 >        return false;
646      }
647  
648      /**
# Line 582 | Line 731 | public class LinkedList<E>
731  
732          public void remove() {
733              checkForComodification();
734 +            Entry<E> lastNext = lastReturned.next;
735              try {
736                  LinkedList.this.remove(lastReturned);
737              } catch (NoSuchElementException e) {
738                  throw new IllegalStateException();
739              }
740              if (next==lastReturned)
741 <                next = lastReturned.next;
741 >                next = lastNext;
742              else
743                  nextIndex--;
744              lastReturned = header;
# Line 637 | Line 787 | public class LinkedList<E>
787          return newEntry;
788      }
789  
790 <    private void remove(Entry<E> e) {
790 >    private E remove(Entry<E> e) {
791          if (e == header)
792              throw new NoSuchElementException();
793  
794 +        E result = e.element;
795          e.previous.next = e.next;
796          e.next.previous = e.previous;
797 +        e.next = e.previous = null;
798 +        e.element = null;
799          size--;
800          modCount++;
801 +        return result;
802      }
803  
804      /**

Diff Legend

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