Refactors LinkedList to not use circular list.

The new implementation is using double pivot instead of
single.

This is to make LinkedList safer when preconditions are
not enabled and iterator is not used properly.
For example, with a circular list, if you keep calling
next/remove you might never hit an NPE because it will
eventually come back to beginning and start iterating
again.

This might be a little bit on the paranoid side but given
the new implementation is no more complex, it is a good
trade-off.

Change-Id: I4915d5c7b3a6a0e48b96c14be4ce0d64bf3b0de2
Review-Link: https://gwt-review.googlesource.com/#/c/9363/

user/super/com/google/gwt/emul/java/util/LinkedList.java

diff --git a/user/super/com/google/gwt/emul/java/util/LinkedList.java b/user/super/com/google/gwt/emul/java/util/LinkedList.java
index ae82156..a276656 100644
--- a/user/super/com/google/gwt/emul/java/util/LinkedList.java
+++ b/user/super/com/google/gwt/emul/java/util/LinkedList.java
@@ -15,8 +15,9 @@
  */
 package java.util;
 
-import static com.google.gwt.core.shared.impl.GwtPreconditions.checkCriticalElement;
+import static com.google.gwt.core.shared.impl.GwtPreconditions.checkElement;
 import static com.google.gwt.core.shared.impl.GwtPreconditions.checkPositionIndex;
+import static com.google.gwt.core.shared.impl.GwtPreconditions.checkState;
 
 import java.io.Serializable;
 
@@ -30,13 +31,13 @@
 public class LinkedList<E> extends AbstractSequentialList<E> implements
     Cloneable, List<E>, Deque<E>, Serializable {
   /*
-   * This implementation uses a doubly-linked circular list with a header node.
+   * This implementation uses a doubly-linked list with a header/tail node.
    * 
    * TODO(jat): add more efficient subList implementation.
    */
 
   private final class DescendingIteratorImpl implements Iterator<E> {
-    private final ListIterator<E> itr = new ListIteratorImpl(size, header);
+    private final ListIterator<E> itr = new ListIteratorImpl(size, tail);
 
     @Override
     public boolean hasNext() {
@@ -84,70 +85,73 @@
       currentIndex = index;
     }
 
+    @Override
     public void add(E o) {
-      addBefore(o, currentNode);
+      addNode(o, currentNode.prev, currentNode);
       ++currentIndex;
       lastNode = null;
     }
 
+    @Override
     public boolean hasNext() {
-      return currentNode != header;
+      return currentNode != tail;
     }
 
+    @Override
     public boolean hasPrevious() {
       return currentNode.prev != header;
     }
 
+    @Override
     public E next() {
-      if (!hasNext()) {
-        throw new NoSuchElementException();
-      }
+      checkElement(hasNext());
+
       lastNode = currentNode;
       currentNode = currentNode.next;
       ++currentIndex;
       return lastNode.value;
     }
 
+    @Override
     public int nextIndex() {
       return currentIndex;
     }
 
+    @Override
     public E previous() {
-      if (!hasPrevious()) {
-        throw new NoSuchElementException();
-      }
+      checkElement(hasPrevious());
+
       lastNode = currentNode = currentNode.prev;
       --currentIndex;
       return lastNode.value;
     }
 
+    @Override
     public int previousIndex() {
       return currentIndex - 1;
     }
 
+    @Override
     public void remove() {
-      verifyCurrentElement();
+      checkState(lastNode != null);
+
+      Node<E> nextNode = lastNode.next;
+      removeNode(lastNode);
       if (currentNode == lastNode) {
         // We just did a previous().
-        currentNode = lastNode.next;
+        currentNode = nextNode;
       } else {
         // We just did a next().
         --currentIndex;
       }
-      lastNode.remove();
       lastNode = null;
-      --size;
     }
 
+    @Override
     public void set(E o) {
-      verifyCurrentElement();
-      lastNode.value = o;
-    }
+      checkState(lastNode != null);
 
-    protected void verifyCurrentElement() {
-      if (lastNode == null) {
-        throw new IllegalStateException();
-      }
+      lastNode.value = o;
     }
   }
 
@@ -160,38 +164,6 @@
     public Node<E> next;
     public Node<E> prev;
     public E value;
-
-    public Node() {
-      next = prev = this;
-    }
-
-    public Node(E value) {
-      this.value = value;
-    }
-
-    /**
-     * Construct a node containing a value and add it before the specified node.
-     * 
-     * @param value
-     * @param nextNode
-     */
-    public Node(E value, Node<E> nextNode) {
-      this(value);
-      this.next = nextNode;
-      this.prev = nextNode.prev;
-      nextNode.prev.next = this;
-      nextNode.prev = this;
-    }
-
-    /**
-     * Remove this node from any list it is in, leaving it with circular
-     * references to itself.
-     */
-    public void remove() {
-      this.next.prev = this.prev;
-      this.prev.next = this.next;
-      this.next = this.prev = this;
-    }
   }
 
   /**
@@ -202,11 +174,14 @@
   private E exposeElement;
 
   /**
-   * Header node - header.next is the first element of the list, and header.prev
-   * is the last element of the list. If the list is empty, the header node will
-   * point to itself.
+   * Header node - header.next is the first element of the list.
    */
-  private Node<E> header;
+  private final Node<E> header = new Node<E>();
+
+  /**
+   * Tail node - tail.prev is the last element of the list.
+   */
+  private final Node<E> tail = new Node<E>();
 
   /**
    * Number of nodes currently present in the list.
@@ -214,11 +189,11 @@
   private int size;
 
   public LinkedList() {
-    clear();
+    reset();
   }
 
   public LinkedList(Collection<? extends E> c) {
-    this();
+    reset();
     addAll(c);
   }
 
@@ -228,19 +203,25 @@
     return true;
   }
 
+  @Override
   public void addFirst(E o) {
-    new Node<E>(o, header.next);
-    ++size;
+    addNode(o, header, header.next);
   }
 
+  @Override
   public void addLast(E o) {
-    new Node<E>(o, header);
-    ++size;
+    addNode(o, tail.prev, tail);
   }
 
   @Override
   public void clear() {
-    header = new Node<E>();
+    reset();
+  }
+
+  private void reset() {
+    header.next = tail;
+    tail.prev = header;
+    header.prev = tail.next = null;
     size = 0;
   }
 
@@ -253,20 +234,23 @@
     return new DescendingIteratorImpl();
   }
 
+  @Override
   public E element() {
     return getFirst();
   }
 
+  @Override
   public E getFirst() {
-    checkCriticalElement(size != 0);
+    checkElement(size != 0);
 
     return header.next.value;
   }
 
+  @Override
   public E getLast() {
-    checkCriticalElement(size != 0);
+    checkElement(size != 0);
 
-    return header.prev.value;
+    return tail.prev.value;
   }
 
   @Override
@@ -276,7 +260,7 @@
     Node<E> node;
     // start from the nearest end of the list
     if (index >= size >> 1) {
-      node = header;
+      node = tail;
       for (int i = size; i > index; --i) {
         node = node.prev;
       }
@@ -290,6 +274,7 @@
     return new ListIteratorImpl(index, node);
   }
 
+  @Override
   public boolean offer(E o) {
     return offerLast(o);
   }
@@ -306,48 +291,34 @@
     return true;
   }
 
+  @Override
   public E peek() {
     return peekFirst();
   }
 
   @Override
   public E peekFirst() {
-    if (size == 0) {
-      return null;
-    } else {
-      return getFirst();
-    }
+    return size == 0 ? null : getFirst();
   }
 
   @Override
   public E peekLast() {
-    if (size == 0) {
-      return null;
-    } else {
-      return getLast();
-    }
+    return size == 0 ? null : getLast();
   }
 
+  @Override
   public E poll() {
     return pollFirst();
   }
 
   @Override
   public E pollFirst() {
-    if (size == 0) {
-      return null;
-    } else {
-      return removeFirst();
-    }
+    return size == 0 ? null : removeFirst();
   }
 
   @Override
   public E pollLast() {
-    if (size == 0) {
-      return null;
-    } else {
-      return removeLast();
-    }
+    return size == 0 ? null : removeLast();
   }
 
   @Override
@@ -360,13 +331,16 @@
     addFirst(e);
   }
 
+  @Override
   public E remove() {
     return removeFirst();
   }
 
+  @Override
   public E removeFirst() {
-    Node<E> node = removeNode(header.next);
-    return node.value;
+    checkElement(size != 0);
+
+    return removeNode(header.next);
   }
 
   @Override
@@ -374,14 +348,16 @@
     return remove(o);
   }
 
+  @Override
   public E removeLast() {
-    Node<E> node = removeNode(header.prev);
-    return node.value;
+    checkElement(size != 0);
+
+    return removeNode(tail.prev);
   }
 
   @Override
   public boolean removeLastOccurrence(Object o) {
-    for (Node<E> e = header.prev; e != header; e = e.prev) {
+    for (Node<E> e = tail.prev; e != header; e = e.prev) {
       if (Objects.equals(e.value, o)) {
         removeNode(e);
         return true;
@@ -395,16 +371,22 @@
     return size;
   }
 
-  private void addBefore(E o, Node<E> target) {
-    new Node<E>(o, target);
+  private void addNode(E o, Node<E> prev, Node<E> next) {
+    Node<E> node = new Node<E>();
+    node.value = o;
+    node.prev = prev;
+    node.next = next;
+    next.prev = prev.next = node;
     ++size;
   }
 
-  private Node<E> removeNode(Node<E> node) {
-    checkCriticalElement(size != 0);
-
+  private E removeNode(Node<E> node) {
+    E oldValue = node.value;
+    node.next.prev = node.prev;
+    node.prev.next = node.next;
+    node.next = node.prev = null;
+    node.value = null;
     --size;
-    node.remove();
-    return node;
+    return oldValue;
   }
 }