jdk-sandbox: comparison jdk/src/share/classes/java/util/LinkedList.java

equal deleted inserted replaced

-:0e342cecb3a9
+:66ef929d58f2
 */
 package java.util;
 /**
-* Linked list implementation of the <tt>List</tt> interface.  Implements all
+* Linked list implementation of the {@code List} interface.  Implements all
 * optional list operations, and permits all elements (including
-* <tt>null</tt>).  In addition to implementing the <tt>List</tt> interface,
+* {@code null}).  In addition to implementing the {@code List} interface,
-* the <tt>LinkedList</tt> class provides uniformly named methods to
+* the {@code LinkedList} class provides uniformly named methods to
-* <tt>get</tt>, <tt>remove</tt> and <tt>insert</tt> an element at the
+* {@code get}, {@code remove} and {@code insert} an element at the
 * beginning and end of the list.  These operations allow linked lists to be
 * used as a stack, {@linkplain Queue queue}, or {@linkplain Deque
-* double-ended queue}. <p>
+* double-ended queue}.
 *
-* The class implements the <tt>Deque</tt> interface, providing
+* <p>The class implements the {@code Deque} interface, providing
-* first-in-first-out queue operations for <tt>add</tt>,
+* first-in-first-out queue operations for {@code add},
-* <tt>poll</tt>, along with other stack and deque operations.<p>
+* {@code poll}, along with other stack and deque operations.
 *
-* All of the operations perform as could be expected for a doubly-linked
+* <p>All of the operations perform as could be expected for a doubly-linked
 * list.  Operations that index into the list will traverse the list from
-* the beginning or the end, whichever is closer to the specified index.<p>
+* the beginning or the end, whichever is closer to the specified index.
 *
 * <p><strong>Note that this implementation is not synchronized.</strong>
 * If multiple threads access a linked list concurrently, and at least
 * one of the threads modifies the list structurally, it <i>must</i> be
 * synchronized externally.  (A structural modification is any operation
 * {@link Collections#synchronizedList Collections.synchronizedList}
 * method.  This is best done at creation time, to prevent accidental
 * unsynchronized access to the list:<pre>
 *   List list = Collections.synchronizedList(new LinkedList(...));</pre>
 *
-* <p>The iterators returned by this class's <tt>iterator</tt> and
+* <p>The iterators returned by this class's {@code iterator} and
-* <tt>listIterator</tt> methods are <i>fail-fast</i>: if the list is
+* {@code listIterator} methods are <i>fail-fast</i>: if the list is
 * structurally modified at any time after the iterator is created, in
-* any way except through the Iterator's own <tt>remove</tt> or
+* any way except through the Iterator's own {@code remove} or
-* <tt>add</tt> methods, the iterator will throw a {@link
+* {@code add} methods, the iterator will throw a {@link
 * ConcurrentModificationException}.  Thus, in the face of concurrent
 * modification, the iterator fails quickly and cleanly, rather than
 * risking arbitrary, non-deterministic behavior at an undetermined
 * time in the future.
 *
 * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
 * as it is, generally speaking, impossible to make any hard guarantees in the
 * presence of unsynchronized concurrent modification.  Fail-fast iterators
-* throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
+* throw {@code ConcurrentModificationException} on a best-effort basis.
 * Therefore, it would be wrong to write a program that depended on this
 * exception for its correctness:   <i>the fail-fast behavior of iterators
 * should be used only to detect bugs.</i>
 *
 * <p>This class is a member of the
 * Java Collections Framework</a>.
 *
 * @author  Josh Bloch
 * @see     List
 * @see     ArrayList
-* @see     Vector
 * @since 1.2
 * @param <E> the type of elements held in this collection
 */
 public class LinkedList<E>
 extends AbstractSequentialList<E>
 implements List<E>, Deque<E>, Cloneable, java.io.Serializable
 {
-private transient Entry<E> header = new Entry<E>(null, null, null);
+transient int size = 0;
-private transient int size = 0;
+/**
+* Pointer to first node.
+* Invariant: (first == null && last == null) ||
+*            (first.prev == null && first.item != null)
+*/
+transient Node<E> first;
+/**
+* Pointer to last node.
+* Invariant: (first == null && last == null) ||
+*            (last.next == null && last.item != null)
+*/
+transient Node<E> last;
 /**
 * Constructs an empty list.
 */
 public LinkedList() {
-header.next = header.previous = header;
 }
 /**
 * Constructs a list containing the elements of the specified
 * collection, in the order they are returned by the collection's
 this();
 addAll(c);
 }
 /**
+* Links e as first element.
+*/
+private void linkFirst(E e) {
+final Node<E> f = first;
+final Node<E> newNode = new Node<E>(null, e, f);
+first = newNode;
+if (f == null)
+last = newNode;
+else
+f.prev = newNode;
+size++;
+modCount++;
+}
+/**
+* Links e as last element.
+*/
+void linkLast(E e) {
+final Node<E> l = last;
+final Node<E> newNode = new Node<E>(l, e, null);
+last = newNode;
+if (l == null)
+first = newNode;
+else
+l.next = newNode;
+size++;
+modCount++;
+}
+/**
+* Inserts element e before non-null Node succ.
+*/
+void linkBefore(E e, Node<E> succ) {
+// assert succ != null;
+final Node<E> pred = succ.prev;
+final Node<E> newNode = new Node<E>(pred, e, succ);
+succ.prev = newNode;
+if (pred == null)
+first = newNode;
+else
+pred.next = newNode;
+size++;
+modCount++;
+}
+/**
+* Unlinks non-null first node f.
+*/
+private E unlinkFirst(Node<E> f) {
+// assert f == first && f != null;
+final E element = f.item;
+final Node<E> next = f.next;
+f.item = null;
+f.next = null; // help GC
+first = next;
+if (next == null)
+last = null;
+else
+next.prev = null;
+size--;
+modCount++;
+return element;
+}
+/**
+* Unlinks non-null last node l.
+*/
+private E unlinkLast(Node<E> l) {
+// assert l == last && l != null;
+final E element = l.item;
+final Node<E> prev = l.prev;
+l.item = null;
+l.prev = null; // help GC
+last = prev;
+if (prev == null)
+first = null;
+else
+prev.next = null;
+size--;
+modCount++;
+return element;
+}
+/**
+* Unlinks non-null node x.
+*/
+E unlink(Node<E> x) {
+// assert x != null;
+final E element = x.item;
+final Node<E> next = x.next;
+final Node<E> prev = x.prev;
+if (prev == null) {
+first = next;
+} else {
+prev.next = next;
+x.prev = null;
+}
+if (next == null) {
+last = prev;
+} else {
+next.prev = prev;
+x.next = null;
+}
+x.item = null;
+size--;
+modCount++;
+return element;
+}
+/**
 * Returns the first element in this list.
 *
 * @return the first element in this list
 * @throws NoSuchElementException if this list is empty
 */
 public E getFirst() {
-if (size==0)
+final Node<E> f = first;
+if (f == null)
 throw new NoSuchElementException();
+return f.item;
-return header.next.element;
 }
 /**
 * Returns the last element in this list.
 *
 * @return the last element in this list
 * @throws NoSuchElementException if this list is empty
 */
 public E getLast()  {
-if (size==0)
+final Node<E> l = last;
+if (l == null)
 throw new NoSuchElementException();
+return l.item;
-return header.previous.element;
 }
 /**
 * Removes and returns the first element from this list.
 *
 * @return the first element from this list
 * @throws NoSuchElementException if this list is empty
 */
 public E removeFirst() {
-return remove(header.next);
+final Node<E> f = first;
+if (f == null)
+throw new NoSuchElementException();
+return unlinkFirst(f);
 }
 /**
 * Removes and returns the last element from this list.
 *
 * @return the last element from this list
 * @throws NoSuchElementException if this list is empty
 */
 public E removeLast() {
-return remove(header.previous);
+final Node<E> l = last;
+if (l == null)
+throw new NoSuchElementException();
+return unlinkLast(l);
 }
 /**
 * Inserts the specified element at the beginning of this list.
 *
 * @param e the element to add
 */
 public void addFirst(E e) {
-addBefore(e, header.next);
+linkFirst(e);
 }
 /**
 * Appends the specified element to the end of this list.
 *
 * <p>This method is equivalent to {@link #add}.
 *
 * @param e the element to add
 */
 public void addLast(E e) {
-addBefore(e, header);
+linkLast(e);
 }
 /**
-* Returns <tt>true</tt> if this list contains the specified element.
+* Returns {@code true} if this list contains the specified element.
-* More formally, returns <tt>true</tt> if and only if this list contains
+* More formally, returns {@code true} if and only if this list contains
-* at least one element <tt>e</tt> such that
+* at least one element {@code e} such that
 * <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>.
 *
 * @param o element whose presence in this list is to be tested
-* @return <tt>true</tt> if this list contains the specified element
+* @return {@code true} if this list contains the specified element
 */
 public boolean contains(Object o) {
 return indexOf(o) != -1;
 }
 * Appends the specified element to the end of this list.
 *
 * <p>This method is equivalent to {@link #addLast}.
 *
 * @param e element to be appended to this list
-* @return <tt>true</tt> (as specified by {@link Collection#add})
+* @return {@code true} (as specified by {@link Collection#add})
 */
 public boolean add(E e) {
-addBefore(e, header);
+linkLast(e);
 return true;
 }
 /**
 * Removes the first occurrence of the specified element from this list,
 * if it is present.  If this list does not contain the element, it is
 * unchanged.  More formally, removes the element with the lowest index
-* <tt>i</tt> such that
+* {@code i} such that
 * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>
-* (if such an element exists).  Returns <tt>true</tt> if this list
+* (if such an element exists).  Returns {@code true} if this list
 * contained the specified element (or equivalently, if this list
 * changed as a result of the call).
 *
 * @param o element to be removed from this list, if present
-* @return <tt>true</tt> if this list contained the specified element
+* @return {@code true} if this list contained the specified element
 */
 public boolean remove(Object o) {
-if (o==null) {
+if (o == null) {
-for (Entry<E> e = header.next; e != header; e = e.next) {
+for (Node<E> x = first; x != null; x = x.next) {
-if (e.element==null) {
+if (x.item == null) {
-remove(e);
+unlink(x);
 return true;
 }
 }
 } else {
-for (Entry<E> e = header.next; e != header; e = e.next) {
+for (Node<E> x = first; x != null; x = x.next) {
-if (o.equals(e.element)) {
+if (o.equals(x.item)) {
-remove(e);
+unlink(x);
 return true;
 }
 }
 }
 return false;
 * the specified collection is modified while the operation is in
 * progress.  (Note that this will occur if the specified collection is
 * this list, and it's nonempty.)
 *
 * @param c collection containing elements to be added to this list
-* @return <tt>true</tt> if this list changed as a result of the call
+* @return {@code true} if this list changed as a result of the call
 * @throws NullPointerException if the specified collection is null
 */
 public boolean addAll(Collection<? extends E> c) {
 return addAll(size, c);
 }
 * specified collection's iterator.
 *
 * @param index index at which to insert the first element
 *              from the specified collection
 * @param c collection containing elements to be added to this list
-* @return <tt>true</tt> if this list changed as a result of the call
+* @return {@code true} if this list changed as a result of the call
 * @throws IndexOutOfBoundsException {@inheritDoc}
 * @throws NullPointerException if the specified collection is null
 */
 public boolean addAll(int index, Collection<? extends E> c) {
-if (index < 0 || index > size)
+checkPositionIndex(index);
-throw new IndexOutOfBoundsException("Index: "+index+
-", Size: "+size);
 Object[] a = c.toArray();
 int numNew = a.length;
-if (numNew==0)
+if (numNew == 0)
 return false;
+Node<E> pred, succ;
+if (index == size) {
+succ = null;
+pred = last;
+} else {
+succ = node(index);
+pred = succ.prev;
+}
+for (Object o : a) {
+@SuppressWarnings("unchecked") E e = (E) o;
+Node<E> newNode = new Node<E>(pred, e, null);
+if (pred == null)
+first = newNode;
+else
+pred.next = newNode;
+pred = newNode;
+}
+if (succ == null) {
+last = pred;
+} else {
+pred.next = succ;
+succ.prev = pred;
+}
+size += numNew;
 modCount++;
-Entry<E> successor = (index==size ? header : entry(index));
-Entry<E> predecessor = successor.previous;
-for (int i=0; i<numNew; i++) {
-Entry<E> e = new Entry<E>((E)a[i], successor, predecessor);
-predecessor.next = e;
-predecessor = e;
-}
-successor.previous = predecessor;
-size += numNew;
 return true;
 }
 /**
 * Removes all of the elements from this list.
+* The list will be empty after this call returns.
 */
 public void clear() {
-Entry<E> e = header.next;
+// Clearing all of the links between nodes is "unnecessary", but:
-while (e != header) {
+// - helps a generational GC if the discarded nodes inhabit
-Entry<E> next = e.next;
+//   more than one generation
-e.next = e.previous = null;
+// - is sure to free memory even if there is a reachable Iterator
-e.element = null;
+for (Node<E> x = first; x != null; ) {
-e = next;
+Node<E> next = x.next;
-}
+x.item = null;
-header.next = header.previous = header;
+x.next = null;
+x.prev = null;
+x = next;
+}
+first = last = null;
 size = 0;
 modCount++;
 }
 * @param index index of the element to return
 * @return the element at the specified position in this list
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
 public E get(int index) {
-return entry(index).element;
+checkElementIndex(index);
+return node(index).item;
 }
 /**
 * Replaces the element at the specified position in this list with the
 * specified element.
 * @param element element to be stored at the specified position
 * @return the element previously at the specified position
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
 public E set(int index, E element) {
-Entry<E> e = entry(index);
+checkElementIndex(index);
-E oldVal = e.element;
+Node<E> x = node(index);
-e.element = element;
+E oldVal = x.item;
+x.item = element;
 return oldVal;
 }
 /**
 * Inserts the specified element at the specified position in this list.
 * @param index index at which the specified element is to be inserted
 * @param element element to be inserted
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
 public void add(int index, E element) {
-addBefore(element, (index==size ? header : entry(index)));
+checkPositionIndex(index);
+if (index == size)
+linkLast(element);
+else
+linkBefore(element, node(index));
 }
 /**
 * Removes the element at the specified position in this list.  Shifts any
 * subsequent elements to the left (subtracts one from their indices).
 * @param index the index of the element to be removed
 * @return the element previously at the specified position
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
 public E remove(int index) {
-return remove(entry(index));
+checkElementIndex(index);
-}
+return unlink(node(index));
+}
-/**
-* Returns the indexed entry.
+/**
-*/
+* Tells if the argument is the index of an existing element.
-private Entry<E> entry(int index) {
+*/
-if (index < 0 || index >= size)
+private boolean isElementIndex(int index) {
-throw new IndexOutOfBoundsException("Index: "+index+
+return index >= 0 && index < size;
-", Size: "+size);
+}
-Entry<E> e = header;
+/**
+* Tells if the argument is the index of a valid position for an
+* iterator or an add operation.
+*/
+private boolean isPositionIndex(int index) {
+return index >= 0 && index <= size;
+}
+/**
+* Constructs an IndexOutOfBoundsException detail message.
+* Of the many possible refactorings of the error handling code,
+* this "outlining" performs best with both server and client VMs.
+*/
+private String outOfBoundsMsg(int index) {
+return "Index: "+index+", Size: "+size;
+}
+private void checkElementIndex(int index) {
+if (!isElementIndex(index))
+throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
+}
+private void checkPositionIndex(int index) {
+if (!isPositionIndex(index))
+throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
+}
+/**
+* Returns the (non-null) Node at the specified element index.
+*/
+Node<E> node(int index) {
+// assert isElementIndex(index);
 if (index < (size >> 1)) {
-for (int i = 0; i <= index; i++)
+Node<E> x = first;
-e = e.next;
+for (int i = 0; i < index; i++)
+x = x.next;
+return x;
 } else {
-for (int i = size; i > index; i--)
+Node<E> x = last;
-e = e.previous;
+for (int i = size - 1; i > index; i--)
-}
+x = x.prev;
-return e;
+return x;
 }
+}
 // Search Operations
 /**
 * Returns the index of the first occurrence of the specified element
 * in this list, or -1 if this list does not contain the element.
-* More formally, returns the lowest index <tt>i</tt> such that
+* More formally, returns the lowest index {@code i} such that
 * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>,
 * or -1 if there is no such index.
 *
 * @param o element to search for
 * @return the index of the first occurrence of the specified element in
 *         this list, or -1 if this list does not contain the element
 */
 public int indexOf(Object o) {
 int index = 0;
-if (o==null) {
+if (o == null) {
-for (Entry e = header.next; e != header; e = e.next) {
+for (Node<E> x = first; x != null; x = x.next) {
-if (e.element==null)
+if (x.item == null)
 return index;
 index++;
 }
 } else {
-for (Entry e = header.next; e != header; e = e.next) {
+for (Node<E> x = first; x != null; x = x.next) {
-if (o.equals(e.element))
+if (o.equals(x.item))
 return index;
 index++;
 }
 }
 return -1;
 }
 /**
 * Returns the index of the last occurrence of the specified element
 * in this list, or -1 if this list does not contain the element.
-* More formally, returns the highest index <tt>i</tt> such that
+* More formally, returns the highest index {@code i} such that
 * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>,
 * or -1 if there is no such index.
 *
 * @param o element to search for
 * @return the index of the last occurrence of the specified element in
 *         this list, or -1 if this list does not contain the element
 */
 public int lastIndexOf(Object o) {
 int index = size;
-if (o==null) {
+if (o == null) {
-for (Entry e = header.previous; e != header; e = e.previous) {
+for (Node<E> x = last; x != null; x = x.prev) {
 index--;
-if (e.element==null)
+if (x.item == null)
 return index;
 }
 } else {
-for (Entry e = header.previous; e != header; e = e.previous) {
+for (Node<E> x = last; x != null; x = x.prev) {
 index--;
-if (o.equals(e.element))
+if (o.equals(x.item))
 return index;
 }
 }
 return -1;
 }
 // Queue operations.
 /**
 * Retrieves, but does not remove, the head (first element) of this list.
-* @return the head of this list, or <tt>null</tt> if this list is empty
+*
+* @return the head of this list, or {@code null} if this list is empty
 * @since 1.5
 */
 public E peek() {
-if (size==0)
+final Node<E> f = first;
-return null;
+return (f == null) ? null : f.item;
-return getFirst();
 }
 /**
 * Retrieves, but does not remove, the head (first element) of this list.
+*
 * @return the head of this list
 * @throws NoSuchElementException if this list is empty
 * @since 1.5
 */
 public E element() {
 return getFirst();
 }
 /**
-* Retrieves and removes the head (first element) of this list
+* Retrieves and removes the head (first element) of this list.
-* @return the head of this list, or <tt>null</tt> if this list is empty
+*
+* @return the head of this list, or {@code null} if this list is empty
 * @since 1.5
 */
 public E poll() {
-if (size==0)
+final Node<E> f = first;
-return null;
+return (f == null) ? null : unlinkFirst(f);
-return removeFirst();
 }
 /**
 * Retrieves and removes the head (first element) of this list.
 *
 /**
 * Adds the specified element as the tail (last element) of this list.
 *
 * @param e the element to add
-* @return <tt>true</tt> (as specified by {@link Queue#offer})
+* @return {@code true} (as specified by {@link Queue#offer})
 * @since 1.5
 */
 public boolean offer(E e) {
 return add(e);
 }
 // Deque operations
 /**
 * Inserts the specified element at the front of this list.
 *
 * @param e the element to insert
-* @return <tt>true</tt> (as specified by {@link Deque#offerFirst})
+* @return {@code true} (as specified by {@link Deque#offerFirst})
 * @since 1.6
 */
 public boolean offerFirst(E e) {
 addFirst(e);
 return true;
 /**
 * Inserts the specified element at the end of this list.
 *
 * @param e the element to insert
-* @return <tt>true</tt> (as specified by {@link Deque#offerLast})
+* @return {@code true} (as specified by {@link Deque#offerLast})
 * @since 1.6
 */
 public boolean offerLast(E e) {
 addLast(e);
 return true;
 }
 /**
 * Retrieves, but does not remove, the first element of this list,
-* or returns <tt>null</tt> if this list is empty.
+* or returns {@code null} if this list is empty.
 *
-* @return the first element of this list, or <tt>null</tt>
+* @return the first element of this list, or {@code null}
 *         if this list is empty
 * @since 1.6
 */
 public E peekFirst() {
-if (size==0)
+final Node<E> f = first;
-return null;
+return (f == null) ? null : f.item;
-return getFirst();
+}
-}
 /**
 * Retrieves, but does not remove, the last element of this list,
-* or returns <tt>null</tt> if this list is empty.
+* or returns {@code null} if this list is empty.
 *
-* @return the last element of this list, or <tt>null</tt>
+* @return the last element of this list, or {@code null}
 *         if this list is empty
 * @since 1.6
 */
 public E peekLast() {
-if (size==0)
+final Node<E> l = last;
-return null;
+return (l == null) ? null : l.item;
-return getLast();
 }
 /**
 * Retrieves and removes the first element of this list,
-* or returns <tt>null</tt> if this list is empty.
+* or returns {@code null} if this list is empty.
 *
-* @return the first element of this list, or <tt>null</tt> if
+* @return the first element of this list, or {@code null} if
 *     this list is empty
 * @since 1.6
 */
 public E pollFirst() {
-if (size==0)
+final Node<E> f = first;
-return null;
+return (f == null) ? null : unlinkFirst(f);
-return removeFirst();
 }
 /**
 * Retrieves and removes the last element of this list,
-* or returns <tt>null</tt> if this list is empty.
+* or returns {@code null} if this list is empty.
 *
-* @return the last element of this list, or <tt>null</tt> if
+* @return the last element of this list, or {@code null} if
 *     this list is empty
 * @since 1.6
 */
 public E pollLast() {
-if (size==0)
+final Node<E> l = last;
-return null;
+return (l == null) ? null : unlinkLast(l);
-return removeLast();
 }
 /**
 * Pushes an element onto the stack represented by this list.  In other
 * words, inserts the element at the front of this list.
 * Removes the first occurrence of the specified element in this
 * list (when traversing the list from head to tail).  If the list
 * does not contain the element, it is unchanged.
 *
 * @param o element to be removed from this list, if present
-* @return <tt>true</tt> if the list contained the specified element
+* @return {@code true} if the list contained the specified element
 * @since 1.6
 */
 public boolean removeFirstOccurrence(Object o) {
 return remove(o);
 }
 * Removes the last occurrence of the specified element in this
 * list (when traversing the list from head to tail).  If the list
 * does not contain the element, it is unchanged.
 *
 * @param o element to be removed from this list, if present
-* @return <tt>true</tt> if the list contained the specified element
+* @return {@code true} if the list contained the specified element
 * @since 1.6
 */
 public boolean removeLastOccurrence(Object o) {
-if (o==null) {
+if (o == null) {
-for (Entry<E> e = header.previous; e != header; e = e.previous) {
+for (Node<E> x = last; x != null; x = x.prev) {
-if (e.element==null) {
+if (x.item == null) {
-remove(e);
+unlink(x);
 return true;
 }
 }
 } else {
-for (Entry<E> e = header.previous; e != header; e = e.previous) {
+for (Node<E> x = last; x != null; x = x.prev) {
-if (o.equals(e.element)) {
+if (o.equals(x.item)) {
-remove(e);
+unlink(x);
 return true;
 }
 }
 }
 return false;
 }
 /**
 * Returns a list-iterator of the elements in this list (in proper
 * sequence), starting at the specified position in the list.
-* Obeys the general contract of <tt>List.listIterator(int)</tt>.<p>
+* Obeys the general contract of {@code List.listIterator(int)}.<p>
 *
 * The list-iterator is <i>fail-fast</i>: if the list is structurally
 * modified at any time after the Iterator is created, in any way except
-* through the list-iterator's own <tt>remove</tt> or <tt>add</tt>
+* through the list-iterator's own {@code remove} or {@code add}
 * methods, the list-iterator will throw a
-* <tt>ConcurrentModificationException</tt>.  Thus, in the face of
+* {@code ConcurrentModificationException}.  Thus, in the face of
 * concurrent modification, the iterator fails quickly and cleanly, rather
 * than risking arbitrary, non-deterministic behavior at an undetermined
 * time in the future.
 *
 * @param index index of the first element to be returned from the
-*              list-iterator (by a call to <tt>next</tt>)
+*              list-iterator (by a call to {@code next})
 * @return a ListIterator of the elements in this list (in proper
 *         sequence), starting at the specified position in the list
 * @throws IndexOutOfBoundsException {@inheritDoc}
 * @see List#listIterator(int)
 */
 public ListIterator<E> listIterator(int index) {
+checkPositionIndex(index);
 return new ListItr(index);
 }
 private class ListItr implements ListIterator<E> {
-private Entry<E> lastReturned = header;
+private Node<E> lastReturned = null;
-private Entry<E> next;
+private Node<E> next;
 private int nextIndex;
 private int expectedModCount = modCount;
 ListItr(int index) {
-if (index < 0 || index > size)
+// assert isPositionIndex(index);
-throw new IndexOutOfBoundsException("Index: "+index+
+next = (index == size) ? null : node(index);
-", Size: "+size);
+nextIndex = index;
-if (index < (size >> 1)) {
-next = header.next;
-for (nextIndex=0; nextIndex<index; nextIndex++)
-next = next.next;
-} else {
-next = header;
-for (nextIndex=size; nextIndex>index; nextIndex--)
-next = next.previous;
-}
 }
 public boolean hasNext() {
-return nextIndex != size;
+return nextIndex < size;
 }
 public E next() {
 checkForComodification();
-if (nextIndex == size)
+if (!hasNext())
 throw new NoSuchElementException();
 lastReturned = next;
 next = next.next;
 nextIndex++;
-return lastReturned.element;
+return lastReturned.item;
 }
 public boolean hasPrevious() {
-return nextIndex != 0;
+return nextIndex > 0;
 }
 public E previous() {
-if (nextIndex == 0)
+checkForComodification();
+if (!hasPrevious())
 throw new NoSuchElementException();
-lastReturned = next = next.previous;
+lastReturned = next = (next == null) ? last : next.prev;
 nextIndex--;
-checkForComodification();
+return lastReturned.item;
-return lastReturned.element;
 }
 public int nextIndex() {
 return nextIndex;
 }
 public int previousIndex() {
-return nextIndex-1;
+return nextIndex - 1;
 }
 public void remove() {
 checkForComodification();
-Entry<E> lastNext = lastReturned.next;
+if (lastReturned == null)
-try {
-LinkedList.this.remove(lastReturned);
-} catch (NoSuchElementException e) {
 throw new IllegalStateException();
-}
-if (next==lastReturned)
+Node<E> lastNext = lastReturned.next;
+unlink(lastReturned);
+if (next == lastReturned)
 next = lastNext;
 else
 nextIndex--;
-lastReturned = header;
+lastReturned = null;
 expectedModCount++;
 }
 public void set(E e) {
-if (lastReturned == header)
+if (lastReturned == null)
 throw new IllegalStateException();
 checkForComodification();
-lastReturned.element = e;
+lastReturned.item = e;
 }
 public void add(E e) {
 checkForComodification();
-lastReturned = header;
+lastReturned = null;
-addBefore(e, next);
+if (next == null)
+linkLast(e);
+else
+linkBefore(e, next);
 nextIndex++;
 expectedModCount++;
 }
 final void checkForComodification() {
 if (modCount != expectedModCount)
 throw new ConcurrentModificationException();
 }
 }
-private static class Entry<E> {
+private static class Node<E> {
-E element;
+E item;
-Entry<E> next;
+Node<E> next;
-Entry<E> previous;
+Node<E> prev;
-Entry(E element, Entry<E> next, Entry<E> previous) {
+Node(Node<E> prev, E element, Node<E> next) {
-this.element = element;
+this.item = element;
 this.next = next;
-this.previous = previous;
+this.prev = prev;
 }
-}
-private Entry<E> addBefore(E e, Entry<E> entry) {
-Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);
-newEntry.previous.next = newEntry;
-newEntry.next.previous = newEntry;
-size++;
-modCount++;
-return newEntry;
-}
-private E remove(Entry<E> e) {
-if (e == header)
-throw new NoSuchElementException();
-E result = e.element;
-e.previous.next = e.next;
-e.next.previous = e.previous;
-e.next = e.previous = null;
-e.element = null;
-size--;
-modCount++;
-return result;
 }
 /**
 * @since 1.6
 */
 public Iterator<E> descendingIterator() {
 return new DescendingIterator();
 }
-/** Adapter to provide descending iterators via ListItr.previous */
+/**
-private class DescendingIterator implements Iterator {
+* Adapter to provide descending iterators via ListItr.previous
-final ListItr itr = new ListItr(size());
+*/
+private class DescendingIterator implements Iterator<E> {
+private final ListItr itr = new ListItr(size());
 public boolean hasNext() {
 return itr.hasPrevious();
 }
 public E next() {
 return itr.previous();
 public void remove() {
 itr.remove();
 }
 }
-/**
+@SuppressWarnings("unchecked")
-* Returns a shallow copy of this <tt>LinkedList</tt>. (The elements
+private LinkedList<E> superClone() {
-* themselves are not cloned.)
-*
-* @return a shallow copy of this <tt>LinkedList</tt> instance
-*/
-public Object clone() {
-LinkedList<E> clone = null;
 try {
-clone = (LinkedList<E>) super.clone();
+return (LinkedList<E>) super.clone();
 } catch (CloneNotSupportedException e) {
 throw new InternalError();
 }
+}
+/**
+* Returns a shallow copy of this {@code LinkedList}. (The elements
+* themselves are not cloned.)
+*
+* @return a shallow copy of this {@code LinkedList} instance
+*/
+public Object clone() {
+LinkedList<E> clone = superClone();
 // Put clone into "virgin" state
-clone.header = new Entry<E>(null, null, null);
+clone.first = clone.last = null;
-clone.header.next = clone.header.previous = clone.header;
 clone.size = 0;
 clone.modCount = 0;
 // Initialize clone with our elements
-for (Entry<E> e = header.next; e != header; e = e.next)
+for (Node<E> x = first; x != null; x = x.next)
-clone.add(e.element);
+clone.add(x.item);
 return clone;
 }
 /**
 *         in proper sequence
 */
 public Object[] toArray() {
 Object[] result = new Object[size];
 int i = 0;
-for (Entry<E> e = header.next; e != header; e = e.next)
+for (Node<E> x = first; x != null; x = x.next)
-result[i++] = e.element;
+result[i++] = x.item;
 return result;
 }
 /**
 * Returns an array containing all of the elements in this list in
 * array is allocated with the runtime type of the specified array and
 * the size of this list.
 *
 * <p>If the list fits in the specified array with room to spare (i.e.,
 * the array has more elements than the list), the element in the array
-* immediately following the end of the list is set to <tt>null</tt>.
+* immediately following the end of the list is set to {@code null}.
 * (This is useful in determining the length of the list <i>only</i> if
 * the caller knows that the list does not contain any null elements.)
 *
 * <p>Like the {@link #toArray()} method, this method acts as bridge between
 * array-based and collection-based APIs.  Further, this method allows
 * precise control over the runtime type of the output array, and may,
 * under certain circumstances, be used to save allocation costs.
 *
-* <p>Suppose <tt>x</tt> is a list known to contain only strings.
+* <p>Suppose {@code x} is a list known to contain only strings.
 * The following code can be used to dump the list into a newly
-* allocated array of <tt>String</tt>:
+* allocated array of {@code String}:
 *
 * <pre>
 *     String[] y = x.toArray(new String[0]);</pre>
 *
-* Note that <tt>toArray(new Object[0])</tt> is identical in function to
+* Note that {@code toArray(new Object[0])} is identical in function to
-* <tt>toArray()</tt>.
+* {@code toArray()}.
 *
 * @param a the array into which the elements of the list are to
 *          be stored, if it is big enough; otherwise, a new array of the
 *          same runtime type is allocated for this purpose.
 * @return an array containing the elements of the list
 * @throws ArrayStoreException if the runtime type of the specified array
 *         is not a supertype of the runtime type of every element in
 *         this list
 * @throws NullPointerException if the specified array is null
 */
+@SuppressWarnings("unchecked")
 public <T> T[] toArray(T[] a) {
 if (a.length < size)
 a = (T[])java.lang.reflect.Array.newInstance(
 a.getClass().getComponentType(), size);
 int i = 0;
 Object[] result = a;
-for (Entry<E> e = header.next; e != header; e = e.next)
+for (Node<E> x = first; x != null; x = x.next)
-result[i++] = e.element;
+result[i++] = x.item;
 if (a.length > size)
 a[size] = null;
 return a;
 }
 private static final long serialVersionUID = 876323262645176354L;
 /**
-* Save the state of this <tt>LinkedList</tt> instance to a stream (that
+* Saves the state of this {@code LinkedList} instance to a stream
-* is, serialize it).
+* (that is, serializes it).
 *
 * @serialData The size of the list (the number of elements it
 *             contains) is emitted (int), followed by all of its
 *             elements (each an Object) in the proper order.
 */
 // Write out size
 s.writeInt(size);
 // Write out all elements in the proper order.
-for (Entry e = header.next; e != header; e = e.next)
+for (Node<E> x = first; x != null; x = x.next)
-s.writeObject(e.element);
+s.writeObject(x.item);
 }
 /**
-* Reconstitute this <tt>LinkedList</tt> instance from a stream (that is
+* Reconstitutes this {@code LinkedList} instance from a stream
-* deserialize it).
+* (that is, deserializes it).
 */
+@SuppressWarnings("unchecked")
 private void readObject(java.io.ObjectInputStream s)
 throws java.io.IOException, ClassNotFoundException {
 // Read in any hidden serialization magic
 s.defaultReadObject();
 // Read in size
 int size = s.readInt();
-// Initialize header
-header = new Entry<E>(null, null, null);
-header.next = header.previous = header;
 // Read in all elements in the proper order.
-for (int i=0; i<size; i++)
+for (int i = 0; i < size; i++)
-addBefore((E)s.readObject(), header);
+linkLast((E)s.readObject());
 }
 }

changeset 4184	66ef929d58f2
parent 2	90ce3da70b43
child 5506	202f599c92aa