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.17 by dl, Tue Dec 28 12:14:07 2004 UTC vs.
Revision 1.25 by jsr166, Mon May 2 06:06:17 2005 UTC

# Line 1 | Line 1
1   /*
2   * %W% %E%
3   *
4 < * Copyright 2004 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  
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 ({@link 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>Deque</tt> interface, providing
21   * first-in-first-out queue operations for <tt>add</tt>,
22 < * <tt>poll</tt>, along with other stack and deque operations.
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 35 | 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 52 | 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 144 | Line 146 | public class LinkedList<E>
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 251 | 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 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 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          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 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 453 | 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 463 | 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 474 | 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 498 | public class LinkedList<E>
498  
499      // Deque operations
500      /**
501 <     * Inserts the specified element to the front this deque.
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})
# Line 508 | Line 510 | public class LinkedList<E>
510      }
511  
512      /**
513 <     * Inserts the specified element to the end this deque.
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})
# Line 520 | Line 522 | public class LinkedList<E>
522      }
523  
524      /**
525 <     * Retrieves, but does not remove, the first element of this deque,
526 <     * returning <tt>null</tt> if this deque is empty.
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 deque, or <tt>null</tt> if
529 <     *     this deque is empty
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 removeFirst();
535 >        return getFirst();
536      }
537  
538      /**
539 <     * Retrieves, but does not remove, the last element of this deque,
540 <     * returning <tt>null</tt> if this deque is empty.
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 deque, or <tt>null</tt> if this deque
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 removeLast();
549 >        return getLast();
550      }
551  
552      /**
553 <     * Retrieves and removes the first element of this deque, or
554 <     * <tt>null</tt> if this deque is empty.
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 deque, or <tt>null</tt> if
557 <     *     this deque is empty
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() {
# Line 562 | Line 564 | public class LinkedList<E>
564      }
565  
566      /**
567 <     * Retrieves and removes the last element of this deque, or
568 <     * <tt>null</tt> if this deque is empty.
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 deque, or <tt>null</tt> if
571 <     *     this deque is empty
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() {
# Line 576 | Line 578 | public class LinkedList<E>
578      }
579  
580      /**
581 <     * Pushes an element onto the stack represented by this deque.  In other
582 <     * words, inserts the element to the front this deque.
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       *
# Line 589 | Line 591 | public class LinkedList<E>
591      }
592  
593      /**
594 <     * Pops an element from the stack represented by this deque.  In other
595 <     * words, removes and returns the the first element of this deque.
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 deque (which is the top
600 <     *     of the stack represented by this deque)
601 <     * @throws NoSuchElementException if this deque is empty
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() {
# Line 605 | Line 607 | public class LinkedList<E>
607  
608      /**
609       * Removes the first occurrence of the specified element in this
610 <     * deque (when traversing the deque from head to tail).  If the deque
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 e element to be removed from this deque, if present
614 <     * @return <tt>true</tt> if the deque contained the specified element
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 e) {
618 <        return remove(e);
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 <     * deque (when traversing the deque from head to tail).  If the deque
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 deque, if present
627 <     * @return <tt>true</tt> if the deque contained the specified element
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) {
# Line 662 | 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) {

Diff Legend

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