Speedy LinkedList implementation.

LinkedList.java

import java.util.*;

public class LinkedList<T> implements List<T> {
   public class Node {
      T data;
      Node prev, next;
      public Node() {}
      public Node(T data_) {data = data_;}
   }

   public class LinkedListIterator implements ListIterator<T> {
      int ndx;
      Node curr;

      public LinkedListIterator(int ndx_) {
         ndx = ndx_;
         curr = head;
         for (int i = 0; i < ndx; i++) {
            curr = curr.next;
         }
      }

      public boolean hasNext() {
         return curr.next != head;
      }
      public boolean hasPrevious() {
         return curr != head;
      }
      public T next() {
         if (!hasNext()) {
            throw new NoSuchElementException();
         }
         curr = curr.next;
         ndx++;
         return curr.data;
      }
      public int nextIndex() {
         return ndx+1;
      }
      public T previous() {
         if (!hasPrevious()) {
            throw new NoSuchElementException();
         }
         T out = curr.data;
         curr = curr.prev;
         ndx--;
         return out;
      }
      public int previousIndex() {
         return ndx;
      }

      public void add(T e) {
         throw new UnsupportedOperationException();
      }
      public void remove() {
         throw new UnsupportedOperationException();
      }
      public void set(T e) {
         throw new UnsupportedOperationException();
      }
   }

   private Node head = new Node();
   private int size = 0;

   public LinkedList() {
      head.prev = head;
      head.next = head;
   }

   public boolean add(T obj) {
      if (obj == null) {
         throw new IllegalArgumentException();
      }
      head.prev = head.prev.next = new Node(obj);
      size++;
      return true;
   }

   public void add(int ndx, T obj) {
      if (ndx < 0 || ndx >= size) {
         throw new IndexOutOfBoundsException();
      }
      if (obj == null) {
         throw new IllegalArgumentException();
      }
      Node tmp = head;
      for (int i = 0; i < ndx; i++) {
         tmp = tmp.next;
      }
      tmp.next = tmp.next.prev = new Node(obj);
   }

   public boolean addAll(Collection<? extends T> c) {
      for (T tmp : c) {
         add(tmp);
      }
      return true;
   }

   public boolean addAll(int ndx, Collection<? extends T> c) {
      int ndx2 = 0;
      for (T tmp : c) {
         add(ndx+ndx2, tmp);
         ndx2++;
      }
      return true;
   }

   public void clear() {
      head.next = head.prev = head;
   }

   public boolean contains(Object o) {
      Node tmp = head.next;
      while (tmp != head) {
         if (tmp.data.equals(o)) {
            return true;
         }
      }
      return false;
   }

   public boolean containsAll(Collection<?> c) {
      for (Object tmp : c) {
         if (!contains(tmp)) {
            return false;
         }
      }
      return true;
   }

   public boolean equals(Object o) {
      if (!(o instanceof LinkedList)) {
         return false;
      }
      LinkedList lo = (LinkedList)o;
      if (lo.size != size) {
         return false;
      }
      
      Node tmpA = head.next, tmpB = lo.head.next;
      while (tmpA != head) {
         if (!tmpA.data.equals(tmpB.data)) {
            return false;
         }
         tmpA = tmpA.next;
         tmpB = tmpB.next;
      }
      return true;
   }

   public T get(int ndx) {
      if (ndx < 0 || ndx >= size) {
         throw new IndexOutOfBoundsException();
      }
      Node tmp = head.next;
      for (int i = 0; i < ndx; i++) {
         tmp = tmp.next;
      }
      return tmp.data;
   }

   public int hashCode() {
      int code = 0;
      Node tmp = head.next;
      for (int i = 0; i < size; i++) {
         code = code * 31 + tmp.data.hashCode();
         tmp = tmp.next;
      }
      return code;
   }

   public int indexOf(Object o) {
      Node tmp = head.next;
      int ndx = 0;
      while (tmp != head && !tmp.data.equals(o)) {
         ndx++;
         tmp = tmp.next;
      }
      if (ndx == size) {
         return -1;
      }
      return ndx;
   }

   public boolean isEmpty() {
      return head.next == head;
   }

   public Iterator<T> iterator() {
      return listIterator();
   }

   public int lastIndexOf(Object o) {
      Node tmp = head.prev;
      int ndx = 0;
      while (tmp != head && !tmp.data.equals(o)) {
         ndx++;
         tmp = tmp.prev;
      }
      if (ndx == size) {
         return -1;
      }
      return ndx;
   }

   public ListIterator<T> listIterator() {
      return new LinkedListIterator(0);
   }

   public ListIterator<T> listIterator(int ndx) {
      return new LinkedListIterator(ndx);
   }

   private void remove_(Node toRemove) {
      toRemove.prev.next = toRemove.next;
      toRemove.next.prev = toRemove.prev;
   }

   public T remove(int ndx) {
      if (ndx < 0 || ndx >= size) {
         throw new IndexOutOfBoundsException();
      }
      Node toRemove = head.next;
      for (int i = 0; i < ndx; i++) {
         toRemove = toRemove.next;
      }
      remove_(toRemove);
      return toRemove.data;
   }

   public boolean remove(Object o) {
      Node tmp = head.next;
      while (tmp != head && !tmp.data.equals(o)) {
         tmp = tmp.next;
      }
      if (tmp == head) {
         return false;
      }
      remove_(tmp);
      return true;
   }

   public boolean removeAll(Collection<?> c) {
      boolean out = false;
      for (Object tmp : c) {
         out |= remove(tmp);
      }
      return out;
   }

   public boolean retainAll(Collection<?> c) {
      Node tmp = head.next;
      boolean out = false;
      while (tmp != head) {
         if (!c.contains(tmp.data)) {
            remove_(tmp);
            out = true;
         }
         tmp = tmp.next;
      }
      return out;
   }

   public T set(int ndx, T obj) {
      if (ndx < 0 || ndx >= size) {
         throw new IndexOutOfBoundsException();
      }
      Node tmp = head.next;
      for (int i = 0; i < ndx; i++) {
         tmp = tmp.next;
      }
      T out = tmp.data;
      tmp.data = obj;
      return out;
   }

   public int size() {
      return size;
   }

   public List<T> subList(int from, int to) {
      if (from < 0 || to > size || from > to) {
         throw new IndexOutOfBoundsException();
      }
      LinkedList<T> out = new LinkedList<T>();
      Node tmp = head.next;
      for (int i = 0; i < to; i++) {
         if (i >= from) {
            out.add(tmp.data);
         }
         tmp = tmp.next;
      }
      return out;
   }

   private void copyToArray(Object[] a) {
      int ndx = 0;
      Node tmp = head.next;
      while (tmp != head) {
         a[ndx++] = tmp.data;
         tmp = tmp.next;
      }
   }

   public Object[] toArray() {
      Object[] out = new Object[size];
      copyToArray(out);
      return out;
   }

   public <E> E[] toArray(E[] a) {
      if (a.length < size) {
         a = Arrays.copyOf(a, size);
      }
      copyToArray(a);
      throw new UnsupportedOperationException();
   }
}