IndexedLinkedList.java - A fast list data structure for large data, Take I/V (public API)

Question

Intro

I have this Java implementation of a list data structure that outperforms on a benchmark even the Apache Commons Collection4 TreeList by a factor of 8.

This post is about public API of the IndexedLinkedList.

Code

public class IndexedLinkedList<E> implements Deque<E>, 
 List<E>, 
 Cloneable, 
 java.io.Serializable {
 /**
 * The serial version UID.
 */
 private static final long serialVersionUID = 54170828611556733L;
 
 /**
 * The cached number of elements in this list.
 */
 int size;
 
 /**
 * The modification counter. Used to detect state changes during concurrent
 * modifications.
 */
 transient int modCount;
 
 /**
 * The head node of the list.
 */
 transient Node<E> head;
 
 /**
 * The tail node of the list.
 */
 transient Node<E> tail;
 
 /**
 * The actual finger list. Without {@code private} keyword since it is 
 * accessed in unit tests.
 */
 transient FingerList<E> fingerList;
 
 /**
 * Caches the start node of the range to remove.
 */
 private transient Node<E> removeRangeStartNode;
 
 /**
 * Caches the end node of the range to remove.
 */
 private transient Node<E> removeRangeEndNode;
 
 /**
 * Caches the number of fingers covering in the prefix.
 */
 transient int numberOfCoveringFingersToPrefix;
 
 /**
 * Caches the number of fingers covering in the suffix.
 */
 transient int numberOfCoveringFingersToSuffix;
 
 /**
 * Constructs an empty list.
 */
 public IndexedLinkedList() {
 this.fingerList = new FingerList<>(this);
 }
 
 /**
 * Constructs a new list and copies the data in {@code c} to it. Runs in
 * \(\mathcal{O}(m + \sqrt{m})\) time, where \(m = |c|\).
 * 
 * @param c the collection to copy. 
 */
 public IndexedLinkedList(Collection<? extends E> c) {
 this();
 addAll(c);
 }
 
 /**
 * Appends the specified element to the end of this list. Runs in amortized 
 * constant time.
 *
 * <p>This method is equivalent to {@link #addLast}.
 *
 * @param e element to be appended to this list.
 * @return {@code true} (as specified by {@link Collection#add}).
 */
 @Override
 public boolean add(E e) {
 linkLast(e);
 return true;
 }
 
 /**
 * Inserts the specified element at the specified position in this list.
 * The affected finger indices will be incremented by one. A finger 
 * {@code F} is <i>affected</i>, if {@code F.index >= index}. Runs in
 * \(\mathcal{O}(\sqrt{\mathrm{size}})\) time.
 *
 * @param index index at which the specified element is to be inserted.
 * @param element element to be inserted.
 * @throws IndexOutOfBoundsException if index is outside of the valid range.
 */
 @Override
 public void add(int index, E element) {
 checkPositionIndex(index);
 
 if (index == size) { // Check push-back first as it is used more often.
 linkLast(element);
 } else if (index == 0) {
 linkFirst(element);
 } else {
 linkBefore(element, index, getNode(index));
 }
 }
 
 /**
 * Appends all of the elements in the specified collection to the end of
 * this list, in the order they are returned by the specified collection's
 * iterator. The behavior of this operation is undefined if 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.) Runs in \(\mathcal{O}(m + \sqrt{m + n} - \sqrt{n})\), where
 * \(m = |c|\) and \(n\) is the size of this list.
 *
 * @param c collection containing elements to be added to this list.
 * @return {@code true} if this list changed as a result of the call.
 * @throws NullPointerException if the specified collection is null.
 */
 @Override
 public boolean addAll(Collection<? extends E> c) {
 return addAll(size, c);
 }
 
 /**
 * Inserts all of the elements in the specified collection into this list, 
 * starting at the specified position. For each finger {@code F} with 
 * {@code F.index >= index} will increment {@code F.index} by 1. Runs in 
 * \(\Theta(m + \sqrt{m + n} - \sqrt{n}) + \mathcal{O}(\sqrt{n})\), where 
 * \(m = |c|\) and \(n\) is the size of this list.
 *
 * @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 {@code true} if this list changed as a result of the call.
 * @throws IndexOutOfBoundsException if the index is outside of the valid
 * range.
 * @throws NullPointerException if the specified collection is null
 */
 @Override
 public boolean addAll(int index, Collection<? extends E> c) {
 checkPositionIndex(index);
 
 if (c.isEmpty()) {
 return false;
 }
 if (size == 0) {
 setAll(c);
 } else if (index == size) {
 appendAll(c);
 } else if (index == 0) {
 prependAll(c);
 } else {
 insertAll(c, getNode(index), index);
 }
 
 return true;
 }
 
 /**
 * Adds the element {@code e} before the head of this list. Runs in 
 * \(\mathcal{O}(\sqrt{n})\) time.
 * 
 * @param e the element to add.
 */
 @Override
 public void addFirst(E e) {
 linkFirst(e);
 }
 
 /**
 * Adds the element {@code e} after the tail of this list. Runs in constant
 * time.
 * 
 * @param e the element to add.
 */
 @Override
 public void addLast(E e) {
 linkLast(e);
 }
 
 /**
 * Checks the data structure invariant. Throws 
 * {@link java.lang.IllegalStateException} on invalid invariant. The 
 * invariant is valid if:
 * <ol>
 * <li>All the fingers in the finger list are sorted by indices.</li>
 * <li>There is no duplicate indices.</li>
 * <li>The index of the leftmost finger is no less than zero.</li>
 * <li>There must be an end-of-list sentinel finger {@code F}, such that 
 * {@code F.index = } <i>size of linked list</i> and {@code F.node} is 
 * {@code null}.
 * </li>
 * <li>Each finger {@code F} points to the {@code i}th linked list node,
 * where {@code i = F.index}.</li>
 * </ol>
 * Runs in worst case \(\mathcal{O}(n)\) time.
 */
 public void checkInvarant() {
 // The first finger spot can never be 'null':
 if (fingerList.getFinger(0) == null) {
 throw new IllegalStateException(
 "fingerList[0] is null. " + 
 "Must be at least the end-of-finger-list sentinel.");
 }
 
 if (fingerList.isEmpty()) {
 // Here the finger list is empty (apart from the end-of-finger-list
 // sentinel):
 if (!this.isEmpty()) {
 // This indexed list cannot be here empty:
 throw new IllegalStateException(
 "fingerList.size() === "
 + fingerList.size()
 + ", this.size() == " 
 + this.size()
 + " != 0");
 }
 
 if (head != null) {
 // The finger and actual lists are empty. 'head' must be 'null':
 throw new IllegalStateException("head != null");
 }
 
 if (tail != null) {
 // The finger and actual lists are empty. 'tail' must be 'null':
 throw new IllegalStateException("tail != null");
 }
 }
 
 if (fingerList.getFinger(0).index < 0) {
 // Negative initial finger index:
 throw new IllegalStateException(
 "First finger index is negative: "
 + fingerList.getFinger(0).index);
 }
 
 // Check the fingers:
 for (int i = 0; i < fingerList.size() - 1; ++i) {
 Finger<E> left = fingerList.getFinger(i);
 Finger<E> right = fingerList.getFinger(i + 1);
 
 // First left will be checked in the very beginning of this method:
 if (right == null) {
 // 'right' cannot be 'null':
 throw new IllegalStateException(
 "fingerList[" + (i + 1) + "] is null.");
 }
 
 if (left.index >= right.index) {
 // Here, indices are in opposite relative order:
 throw new IllegalStateException(
 "FingerList failed: fingerList[" 
 + i
 + "].index = " 
 + left.index 
 + " >= " 
 + right.index 
 + " = fingerList[" 
 + (i + 1) 
 + "].index");
 }
 }
 
 if (getRecommendedNumberOfFingers() != fingerList.size()) {
 // The required and actual number of fingers mismatch:
 throw new IllegalStateException(
 "Number of fingers mismatch: required = " 
 + getRecommendedNumberOfFingers() 
 + ", actual = " 
 + fingerList.size());
 }
 
 Finger<E> sentinelFinger = fingerList.getFinger(fingerList.size());
 
 if (sentinelFinger == null) {
 // Here, the end-of-finger-list sentinel is 'null':
 throw new IllegalStateException(
 "No sentinel finger (number of fingers = " 
 + fingerList.size() 
 + ").");
 }
 
 if (sentinelFinger.index != this.size) {
 // Size mismatch:
 throw new IllegalStateException(
 "sentinelFinger.index != this.size. (" 
 + sentinelFinger.index 
 + " != " 
 + this.size 
 + ")");
 }
 
 if (sentinelFinger.node != null) {
 // The sentinel finger may not have any node associated with it:
 throw new IllegalStateException(
 "sentinelFigner.node != null: " + sentinelFinger);
 }
 
 // Check the finger and element counters:
 Finger<E> finger = fingerList.getFinger(0);
 Node<E> node = head;
 int fingerCount = 0;
 int tentativeSize = 0;
 
 while (node != null) {
 // Count a new 'node':
 tentativeSize++;
 
 if (finger.node == node) {
 // 'node' is pointed by a finger:
 finger = fingerList.getFinger(++fingerCount);
 }
 
 node = node.next;
 }
 
 if (size != tentativeSize) {
 // The size recording in this indexed list and actual counted size
 // do not match:
 throw new IllegalStateException(
 "Number of nodes mismatch: size = " 
 + size 
 + ", tentativeSize = " 
 + tentativeSize);
 }
 
 // Check that there is no junk fingers in the rest of the finger array:
 for (int i = fingerList.size() + 1;
 i < fingerList.fingerArray.length; 
 i++) {
 
 finger = fingerList.getFinger(i);
 
 if (finger != null) {
 // Found a junk finger:
 throw new IllegalStateException(
 "Junk finger " + finger + " at fingerList[" + i + "]");
 }
 }
 
 int length = fingerList.fingerArray.length;
 
 // Finally, check that the finger list cannot be contracted:
 if (length == FingerList.INITIAL_CAPACITY) {
 // Nothing to contract:
 return;
 }
 if (size + 1 < (length / FingerList.THRESHOLD_FACTOR)) {
 // The finger array capacity is too large. Should have contracted.
 throw new IllegalStateException(
 "The list has " 
 + (size() + 1) 
 + " elements in total. Capacity of the "
 + "finger list is "
 + fingerList.size()
 + ". Must be contracted.");
 }
 }
 
 /**
 * Completely clears this list.
 */
 @Override
 public void clear() {
 fingerList.clear();
 size = 0;
 
 // Help GC:
 for (Node<E> node = head; node != null;) {
 // Unlink 'node':
 node.prev = null;
 node.item = null;
 Node<E> next = node.next;
 node.next = null;
 node = next;
 }
 // Repair the invariant:
 head = tail = null;
 // Signal that state was changed:
 modCount++;
 }
 
 /**
 * Returns a clone list with same content as this list.
 * 
 * @return the clone list.
 */
 @Override
 public Object clone() {
 return new IndexedLinkedList<>(this);
 }
 
 /**
 * Returns {@code true} only if {@code o} is present in this list. Runs in
 * worst-case linear time.
 * 
 * @param o the query object.
 */
 @Override
 public boolean contains(Object o) {
 return indexOf(o) >= 0;
 }
 
 /**
 * Returns {@code true} only if this list contains all the elements 
 * mentioned in the {@code c}. Runs in Runs in \(\mathcal{O}(mn)\) time, 
 * where \(m = |c|\).
 * 
 * @param c the query object collection.
 * @return {@code true} only if this list contains all the elements in
 * {@code c}, or {@code false} otherwise.
 */
 @Override
 public boolean containsAll(Collection<?> c) {
 for (Object o : c) {
 if (!contains(o)) {
 return false;
 }
 }
 
 return true;
 } 
 
 /**
 * Returns a deep copy of this list that mimics both the linked list and the
 * finger list. (Used for unit testing. Normal usage of the class should not
 * rely on this method.)
 * 
 * @return a deep copy of this list.
 */
 public IndexedLinkedList<E> deepCopy() {
 // First, copy the actual content:
 IndexedLinkedList<E> other = new IndexedLinkedList<>(this);
 int fingerIndex = 0;
 
 // Copy the finger list:
 for (int i = 0; i <= this.fingerList.size; i++) {
 // Copy the finger:
 other.fingerList.fingerArray[fingerIndex++] = 
 new Finger<>(fingerList.fingerArray[i]);
 }
 
 return other;
 }
 
 /**
 * Packs half of fingers at the list prefix and the rest of fingers to the
 * suffix of the list. Used for research.
 */
 public void deoptimize() {
 if (fingerList.isEmpty()) {
 // Nothing to deoptimize. Return:
 return;
 }
 
 if (fingerList.size() == 1) {
 // Handles a special case:
 Finger<E> finger = fingerList.getFinger(0);
 finger.index = 0;
 finger.node = head;
 return;
 }
 
 // Packs the fingers:
 int leftFingers = fingerList.size() / 2;
 int rightFingers = fingerList.size() - leftFingers;
 int sz = fingerList.size(); 
 Node<E> node = head;
 
 // Just pack all the fingers at the very beginning.
 for (int i = 0; i < leftFingers; ++i) {
 // Pack the current finger:
 fingerList.getFinger(i).index = i;
 fingerList.getFinger(i).node = node;
 // Grab the reference to the next node:
 node = node.next;
 }
 
 node = tail;
 
 // Pack the remaining fingers at the end of the list:
 for (int i = 0; i < rightFingers; ++i) {
 fingerList.getFinger(sz - 1 - i).index = size - 1 - i;
 fingerList.getFinger(sz - 1 - i).node = node;
 // Grab the reference to the previous node:
 node = node.prev;
 }
 }
 
 /**
 * Returns the descending iterator.
 * 
 * @return the descending iterator pointing to the tail of this list.
 */
 @Override
 public Iterator<E> descendingIterator() {
 return new DescendingIterator();
 }
 
 /**
 * Distributes the fingers over the element list
 * {@code [fromIndex, toIndex)} evenly.
 * 
 * @param fromIndex the leftmost element index in the range over which to 
 * distribute the fingers.
 * @param toIndex the one past the rightmost element index in the range 
 * over which to distribute the fingers.
 */
 public void distributeFingers(int fromIndex, int toIndex) {
 checkFromTo(fromIndex, toIndex);
 
 int rangeLength = toIndex - fromIndex;
 
 if (rangeLength == 0) {
 return;
 }
 
 int fingerPrefixLength = fingerList.getFingerIndexImpl(fromIndex);
 int fingerSuffixLength = fingerList.size() 
 - fingerList.getFingerIndexImpl(toIndex);
 
 int numberOfRangeFingers = fingerList.size()
 - fingerPrefixLength 
 - fingerSuffixLength;
 
 if (numberOfRangeFingers == 0) {
 // Nothing to distribute. Return:
 return;
 }
 
 int numberOfElementsPerFinger = rangeLength / numberOfRangeFingers;
 int index = fromIndex;
 
 // Grab the node:
 Node<E> node = getNode(fromIndex);
 
 for (int i = 0; i < numberOfRangeFingers - 1; ++i) {
 // Grab the ith finger in the range:
 Finger<E> finger = fingerList.getFinger(i + fingerPrefixLength);
 // Update its data:
 finger.node = node;
 finger.index = index;
 // Advance both node and index to the next finger's node:
 node = scrollNodeToRight(node, numberOfElementsPerFinger);
 index += numberOfElementsPerFinger;
 }
 
 // Since we cannot advance node to the right, we need to deal with the
 // last (non-sentinel) finger manually:
 Finger<E> lastFinger =
 fingerList.getFinger(
 numberOfRangeFingers - 1 + fingerPrefixLength);
 
 lastFinger.node = node;
 lastFinger.index = index;
 } 
 
 /**
 * Returns the first element of this list. Runs in constant time.
 * 
 * @return the first element of this list.
 * @throws NoSuchElementException if this list is empty.
 */
 @Override
 public E element() {
 return getFirst();
 }
 
 /**
 * Returns {@code true} only if {@code o} is an instance of 
 * {@link java.util.List} and has the sane contents as this list. Runs in
 * worst-case linear time.
 * 
 * @return {@code true} only if {@code o} is a list with the same contents
 * as this list.
 */
 @Override
 public boolean equals(Object o) {
 if (o == this) {
 return true;
 }
 
 if (!(o instanceof List)) {
 return false;
 }
 
 int expectedModCount = modCount;
 
 List<?> otherList = (List<?>) o;
 boolean equal = equalsRange(otherList, 0, size);
 
 checkForComodification(expectedModCount);
 return equal;
 }
 
 /**
 * Returns {@code index}th element. Runs in the worst-case 
 * \(\mathcal{O}(\sqrt{n})\) time, but may run in \(\mathcal{O}(\sqrt{n})\)
 * if the entropy of this list is high.
 * 
 * @return {@code index}th element.
 * @throws IndexOutOfBoundsException if the index is out of range
 * {@code 0, 1, ..., size - 1}, or if this list is empty.
 */
 @Override
 public E get(int index) {
 checkElementIndex(index);
 return getNode(index).item;
 }
 
 /**
 * Computes and returns the entropy of this list, which is defined as
 * \[
 * H = 1 - \frac{1}{N} \sum_{i = 0}^{n - 1} \Bigg|f_{i + 1} - f_i - \sqrt{N}\Bigg|. 
 * \]
 * The larger the entropy, the faster the single-element operations should
 * run.
 * 
 * @return the entropy of this list.
 */
 public double getEntropy() {
 double sum = 0.0;
 
 for (int i = 0; i < fingerList.size(); i++) {
 double value = fingerList.getFinger(i + 1).index 
 - fingerList.getFinger(i).index 
 - fingerList.size();
 
 value = Math.abs(value);
 sum += value;
 }
 
 sum /= size;
 return Math.max(0.0, 1.0 - sum);
 }
 
 /**
 * Returns the first element of this list. Runs in constant time.
 * 
 * @return the first element of this list.
 * @throws NoSuchElementException if this list is empty.
 */
 @Override
 public E getFirst() {
 if (head == null) {
 throw new NoSuchElementException(
 "Getting the head element from an empty list.");
 }
 
 return head.item;
 }
 
 /**
 * Returns the last element of this list. Runs in constant time.
 * 
 * @return the last element of this list.
 * @throws NoSuchElementException if this list is empty.
 */
 @Override
 public E getLast() {
 if (tail == null) {
 throw new NoSuchElementException(
 "Getting the tail element from an empty list.");
 }
 
 return tail.item;
 }
 
 /**
 * Returns the hash code of this list. Runs in linear time.
 * 
 * @return the hash code of this list.
 */
 @Override
 public int hashCode() {
 int expectedModCount = modCount;
 int hash = hashCodeRange(0, size);
 checkForComodification(expectedModCount);
 return hash;
 }
 
 /**
 * Returns the index of the leftmost {@code obj}, or {@code -1} if 
 * {@code obj} does not appear in this list. Runs in worst-case linear time.
 * 
 * @param obj the object to search.
 * 
 * @return the index of the leftmost {@code obj}, or {@code -1} if 
 * {@code obj} does not appear in this list.
 * 
 * @see IndexedLinkedList#lastIndexOf(java.lang.Object) 
 */
 @Override
 public int indexOf(Object obj) {
 return indexOfRange(obj, 0, size);
 }
 
 /**
 * Returns {@code true} only if this list is empty.
 * 
 * @return {@code true} only if this list is empty.
 */
 @Override
 public boolean isEmpty() {
 return size == 0;
 }
 /**
 * Returns the iterator over this list.
 * 
 * @return the iterator over this list.
 */
 @Override
 public Iterator<E> iterator() {
 return new BasicIterator();
 }
 /**
 * Returns the index of the rightmost {@code obj}, or {@code -1} if 
 * {@code obj} does not appear in this list. Runs in worst-case linear time.
 * 
 * @param obj the object to search.
 * 
 * @return the index of the rightmost {@code obj}, or {@code -1} if
 * {@code obj} does not appear in this list.
 * 
 * @see IndexedLinkedList#lastIndexOf(java.lang.Object) 
 */
 @Override
 public int lastIndexOf(Object obj) {
 return lastIndexOfRange(obj, 0, size);
 }
 
 /**
 * Returns the list iterator pointing to the head element of this list.
 * 
 * @return the list iterator.
 * @see java.util.ListIterator
 */
 @Override
 public ListIterator<E> listIterator() {
 return new EnhancedIterator(0);
 }
 
 /**
 * Returns the list iterator pointing between {@code list[index - 1]} and
 * {@code list[index]}.
 * 
 * @param index the gap index. The value of zero will point before the head 
 * element.
 * 
 * @return the list iterator pointing to the {@code index}th gap.
 */
 @Override
 public ListIterator<E> listIterator(int index) {
 return new EnhancedIterator(index);
 }
 
 /**
 * Adds {@code e} after the tail element of this list. Runs in constant 
 * time.
 * 
 * @param e the element to add.
 * @return always {@code true}.
 */
 @Override
 public boolean offer(E e) {
 return add(e);
 }
 /**
 * Adds {@code e} before the head element of this list. Runs in 
 * \(\mathcal{O}(\sqrt{n})\) time.
 * 
 * @param e the element to add.
 * @return always {@code true}.
 */
 @Override
 public boolean offerFirst(E e) {
 addFirst(e);
 return true;
 }
 /**
 * Adds {@code e} after the tail element of this list. Runs in constant 
 * time.
 * 
 * @param e the element to add.
 * @return always {@code true}.
 */
 @Override
 public boolean offerLast(E e) {
 addLast(e);
 return true;
 }
 
 /**
 * Moves all the fingers such that they are evenly distributed. Runs in 
 * linear time.
 */
 public void optimize() {
 distributeAllFingers();
 }
 
 /**
 * Takes a look at the first element in this list.
 * 
 * @return the head element or {@code null} if this list is empty.
 */
 @Override
 public E peek() {
 return head == null ? null : head.item;
 }
 /**
 * Takes a look at the first element in this list.
 * 
 * @return the head element or {@code null} if this list is empty.
 */
 @Override
 public E peekFirst() {
 return head == null ? null : head.item;
 }
 /**
 * Takes a look at the last element in this list.
 * 
 * @return the tail element or {@code null} if this list is empty.
 */
 @Override
 public E peekLast() {
 return tail == null ? null : tail.item;
 }
 
 /**
 * If this list is empty, does nothing else but return {@code null}. 
 * Otherwise, removes the first element and returns it. Runs in 
 * \(\mathcal{O}(\sqrt{n})\) time.
 * 
 * @return the first element (which was removed due to the call to this 
 * method), or {@code null} if the list is empty.
 */
 @Override
 public E poll() {
 return head == null ? null : removeFirst();
 }
 /**
 * If this list is empty, does nothing else but return {@code null}. 
 * Otherwise, removes the first element and returns it. Runs in 
 * \(\mathcal{O}(\sqrt{n})\) time.
 * 
 * @return the first element (which was removed due to the call to this 
 * method), or {@code null} if the list is empty.
 */
 @Override
 public E pollFirst() {
 return head == null ? null : removeFirst();
 }
 /**
 * If this list is empty, does nothing else but return {@code null}. 
 * Otherwise, removes the last element and returns it. Runs in constant 
 * time.
 * 
 * @return the last element (which was removed due to the call to this 
 * method), or {@code null} if the list is empty.
 */
 @Override
 public E pollLast() {
 return tail == null ? null : removeLast();
 }
 
 /**
 * Removes the first element and returns it.
 * Runs in \(\mathcal{O}(\sqrt{n})\) time.
 * 
 * @return the first element.
 * @throws NoSuchElementException if the list is empty.
 */
 @Override
 public E pop() {
 return removeFirst();
 }
 /**
 * Adds {@code e} before the head of this list. Runs in 
 * \(\mathcal{O}(\sqrt{n})\) time.
 */
 @Override
 public void push(E e) {
 addFirst(e);
 }
 
 /**
 * Randomizes the fingers. Used primarily for research. Uses the current 
 * milliseconds timestamp as the seed.
 */
 public void randomizeFingers() {
 randomizeFingers(System.currentTimeMillis());
 }
 
 /**
 * Randomizes the fingers. Used primarily for research.
 * 
 * @param random the random number generator object.
 */
 public void randomizeFingers(Random random) {
 final Set<Integer> indexFilter = new HashSet<>();
 // Load the set of valid, random integers of size 'fingerList.size()':
 while (indexFilter.size() < fingerList.size) {
 indexFilter.add(random.nextInt(size));
 }
 
 // Sort the finger indices:
 Integer[] newFingerIndexArray = new Integer[fingerList.size];
 newFingerIndexArray = indexFilter.toArray(newFingerIndexArray);
 Arrays.sort(newFingerIndexArray);
 
 // Update the finger list:
 for (int i = 0; i < fingerList.size; i++) {
 Finger finger = fingerList.fingerArray[i];
 finger.index = newFingerIndexArray[i];
 finger.node = getNodeSequentially(finger.index);
 }
 }
 /**
 * Randomizes the fingers. Used primarily for research.
 * 
 * @param seed the random seed.
 */
 public void randomizeFingers(long seed) {
 randomizeFingers(new Random(seed));
 
 }
 
 /**
 * Removes and returns the first element. Runs in 
 * \(\mathcal{O}(\sqrt{n})\) time.
 * 
 * @return the head element of this list.
 * @throws NoSuchElementException if this list is empty.
 */
 @Override
 public E remove() {
 return removeFirst();
 }
 
 /**
 * Removes the element residing at the given index. Runs in worst-case
 * \(\mathcal{O}(\sqrt{n})\) time.
 * 
 * @param index the index of the element to remove.
 * @return the removed element. (The one that resided at the index 
 * {@code index}.)
 */
 @Override
 public E remove(int index) {
 checkElementIndex(index);
 
 // Get the closest finger:
 int closestFingerIndex = fingerList.getClosestFingerIndex(index);
 Finger<E> closestFinger = fingerList.getFinger(closestFingerIndex);
 
 E returnValue;
 Node<E> nodeToRemove;
 
 if (closestFinger.index == index) {
 // Once here, element with index 'index' is pointed by a finger:
 nodeToRemove = closestFinger.node;
 // Move the pointing finger out of the node to be removed:
 moveFingerOutOfRemovalLocation(closestFinger, 
 closestFingerIndex); 
 } else {
 // Keep the fingers at their original position.
 // Find the target node. Effectively, 'steps' communicates how much
 // steps we must do to the left:
 int steps = index - closestFinger.index;
 
 // Once here, the closest finger does not point to the node to be
 // removed. Traverse to the actual removal node:
 nodeToRemove =
 rewindFinger(
 closestFinger,
 steps);
 
 // Shift all the indices starting from 'closestFingerIndex + 1'th 
 // finger o ne position to the left (smaller indices):
 fingerList.shiftFingerIndicesToLeftOnceAll(closestFingerIndex + 1);
 
 if (steps < 0) { 
 // Once here, we need to fix the index also of the 
 // 'closestFingerIndex'th finger:
 fingerList.getFinger(closestFingerIndex).index--;
 }
 }
 
 // Actually unlink the target node:
 returnValue = nodeToRemove.item;
 unlink(nodeToRemove);
 decreaseSize();
 if (mustRemoveFinger()) {
 // Once here, we can safely remove the last finger:
 removeFinger();
 }
 return returnValue;
 }
 /**
 * Removes the leftmost occurrence of {@code o} in this list. Runs in worst-
 * case \(\mathcal{O}(n + \sqrt{n})\) time. \(\mathcal{O}(n)\) for iterating 
 * the list and \(\mathcal{O}(\sqrt{n})\) time for fixing the fingers.
 * 
 * @param o the object to remove.
 * 
 * @return {@code true} only if {@code o} was located in this list and, 
 * thus, removed.
 */
 @Override
 public boolean remove(Object o) {
 int index = 0;
 for (Node<E> x = head; x != null; x = x.next, index++) {
 if (Objects.equals(o, x.item)) {
 removeObjectImpl(x, index);
 return true;
 }
 }
 return false;
 }
 
 /**
 * Removes from this list all the elements mentioned in {@code c}. Runs in
 * \(\mathcal{O}(n\sqrt{n} + fn)\) time, where \(\mathcal{O}(f)\) is the 
 * time of checking for element inclusion in {@code c}.
 * 
 * @param c the collection holding all the elements to remove.
 * @return {@code true} only if at least one element in {@code c} was 
 * located and removed from this list.
 */
 @Override
 public boolean removeAll(Collection<?> c) {
 return batchRemove(c, true, 0, size);
 }
 /**
 * Removes the first element from this list. Runs in 
 * \(\mathcal{O}(\sqrt{n})\) time.
 * 
 * @return the first element.
 */
 @Override
 public E removeFirst() {
 if (size == 0) {
 throw new NoSuchElementException(
 "removeFirst from an empty IndexedLinkedList");
 }
 
 return removeFirstImpl();
 }
 
 /**
 * Removes the leftmost occurrence of {@code o}. Runs in worst-case 
 * \(\mathcal{O}(n)\) time.
 * 
 * @return {@code true} only if {@code o} was present in the list and was 
 * successfully removed.
 */
 @Override
 public boolean removeFirstOccurrence(Object o) {
 int index = 0;
 
 for (Node<E> x = head; x != null; x = x.next, index++) {
 if (Objects.equals(o, x.item)) {
 removeObjectImpl(x, index);
 return true;
 }
 }
 
 return false;
 }
 
 /**
 * Removes from this list all the elements that satisfy the given input
 * predicate. Runs in \(\mathcal{O}(n\sqrt{n})\) time.
 * 
 * @param filter the filtering predicate.
 * @return {@code true} only if at least one element was removed.
 */
 @Override
 public boolean removeIf(Predicate<? super E> filter) {
 return removeIf(filter, 0, size);
 }
 
 /**
 * Removes and returns the last element of this list. Runs in constant time.
 * 
 * @return the removed head element.
 * @throws NoSuchElementException if this list is empty.
 */
 @Override
 public E removeLast() {
 if (size == 0) {
 throw new NoSuchElementException(
 "removeLast on empty IndexedLinkedList");
 }
 
 return removeLastImpl();
 }
 /**
 * Removes the rightmost occurrence of {@code o}. Runs in 
 * \(\mathcal{O}(n)\) time.
 * 
 * @param o the object to remove.
 * @return {@code true} only if an element was actually removed.
 */
 @Override
 public boolean removeLastOccurrence(Object o) {
 int index = size - 1;
 for (Node<E> x = tail; x != null; x = x.prev, index--) {
 if (Objects.equals(o, x.item)) {
 if (index == size - 1) {
 removeLast();
 } else {
 removeObjectImpl(x, index);
 }
 
 return true;
 }
 }
 return false;
 }
 /**
 * Replaces all the elements in this list by applying the given input 
 * operator to each of the elements. Runs in linear time.
 * 
 * @param operator the operator mapping one element to another. 
 */
 @Override
 public void replaceAll(UnaryOperator<E> operator) {
 replaceAllRange(operator, 0, size);
 modCount++;
 }
 
 /**
 * Remove all the elements that <strong>do not</strong> appear in 
 * {@code c}. Runs in worst-case \(\mathcal{O}(nf + n\sqrt{n})\) time, where
 * the inclusion check in {@code c} is run in \(\mathcal{O}(f)\) time.
 * 
 * @param c the collection of elements to retain.
 * @return {@code true} only if at least one element was removed.
 */
 @Override
 public boolean retainAll(Collection<?> c) {
 return batchRemove(c, false, 0, size);
 }
 
 /**
 * Sets the element at index {@code index} to {@code element} and returns
 * the old element. Runs in worst-case \(\mathcal{O}(\sqrt{n})\) time.
 * 
 * @param index the target index.
 * @param element the element to set.
 * @return the previous element at the given index.
 */
 @Override
 public E set(int index, E element) {
 checkElementIndex(index);
 Node<E> node = getNode(index);
 E oldElement = node.item;
 node.item = element;
 return oldElement;
 }
 
 /**
 * Returns the number of elements in this list.
 * 
 * @return the size of this list.
 */
 @Override
 public int size() {
 return size;
 }
 
 /**
 * Sorts stably this list into non-descending order. Runs in 
 * \(\mathcal{O}(n \log n)\).
 * 
 * @param c the element comparator.
 */
 @Override
 public void sort(Comparator<? super E> c) {
 if (size == 0) {
 return;
 }
 
 // Convert to an array and sort the array:
 Object[] array = toArray();
 Arrays.sort((E[]) array, c);
 
 Node<E> node = head;
 
 // Rearrange the items over the linked list nodes:
 for (int i = 0; i < array.length; ++i, node = node.next) {
 E item = (E) array[i];
 node.item = item;
 }
 
 // Distribute all the fingers evenly:
 distributeAllFingers();
 // Update the modification count:
 modCount++;
 }
 
 /**
 * Returns the spliterator over this list.
 */
 @Override
 public Spliterator<E> spliterator() {
 return new LinkedListSpliterator<>(this, head, size, 0, modCount);
 }
 
 /**
 * Verifies that the contents of this indexed list and the {@code otherList}
 * are the same, and their respective fingers lists are identical. Used for
 * debugging.
 * 
 * @param otherList the other indexed list.
 * 
 * @return {@code true} if and only if the both lists are identical in 
 * structure.
 */
 public boolean strongEquals(final IndexedLinkedList<E> otherList) {
 return equals(otherList) && fingerList.equals(otherList.fingerList);
 }
 
 /**
 * Returns a sublist view 
 * {@code list[fromIndex, fromIndex + 1, ..., toIndex - 1]}.
 * 
 * @param fromIndex the smallest index, inclusive.
 * @param toIndex the largest index, exclusive.
 * @return the sublist view.
 */
 @Override
 public List<E> subList(int fromIndex, int toIndex) {
 subListRangeCheck(fromIndex, toIndex, size);
 return new EnhancedSubList(this, fromIndex, toIndex);
 }
 
 /**
 * Returns the {@link Object} array containing all the elements in this 
 * list, in the same order as they appear in the list.
 * 
 * @return the list contents in an {@link Object} array.
 */
 @Override
 public Object[] toArray() {
 Object[] arr = new Object[size];
 int index = 0;
 
 for (Node<E> node = head; node != null; node = node.next) {
 arr[index++] = node.item;
 }
 
 return arr;
 }
 
 /**
 * If {@code a} is sufficiently large, returns the same array holding all
 * the contents of this list. Also, if {@code a} is larger than the input
 * array, sets {@code a[s] = null}, where {@code s} is the size of this
 * list. However, if {@code a} is smaller than this list, allocates a new
 * array of the same length, populates it with the list contents and returns
 * it.
 * 
 * @param <T> the element type.
 * @param a the input array.
 * @return an array holding the contents of this list.
 */
 @SuppressWarnings("unchecked")
 @Override
 public <T> T[] toArray(T[] a) {
 if (a.length < size) {
 // Once here, we need a larger array:
 a = (T[]) Array.newInstance(a.getClass().getComponentType(), size);
 }
 
 int index = 0;
 
 // Copy the contents into the array:
 for (Node<E> node = head; node != null; node = node.next) {
 a[index++] = (T) node.item;
 }
 
 if (a.length > size) {
 // Once here, mark the end of the data as 'null':
 a[size] = null;
 }
 
 return a;
 }
 
 /**
 * Returns the string representation of this list, listing all the elements.
 * 
 * @return the string representation of this list.
 */
 @Override
 public String toString() {
 StringBuilder stringBuilder = new StringBuilder();
 stringBuilder.append("[");
 
 // Indicates that we are before the first iteration:
 boolean firstIteration = true;
 
 for (E element : this) {
 if (firstIteration) {
 firstIteration = false;
 } else {
 // Once here, this iteration is not the first one. Add a comma:
 stringBuilder.append(", ");
 }
 
 stringBuilder.append(element);
 }
 
 return stringBuilder.append("]").toString();
 }
}

Critique request

So what do you think? Is it ready for production use?

Answer 1

Setting aside whether it compiles or not, when the size is 0, the implementation of addAll(int index, Collection<? extends E> c) is inconsistent with the java documentation of the method. For size equals 0, it should add null values until the index argument and then append the c argument.

/**
 * Inserts all of the elements in the specified collection into this list, 
 * starting at the specified position. For each finger {@code F} with 
 * {@code F.index >= index} will increment {@code F.index} by 1. Runs in 
 * \(\Theta(m + \sqrt{m + n} - \sqrt{n}) + \mathcal{O}(\sqrt{n})\), where 
 * \(m = |c|\) and \(n\) is the size of this list.
 *
 * @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 {@code true} if this list changed as a result of the call.
 * @throws IndexOutOfBoundsException if the index is outside of the valid
 * range.
 * @throws NullPointerException if the specified collection is null
 */
@Override
public boolean addAll(int index, Collection<? extends E> c) {
 checkPositionIndex(index);
 if (c.isEmpty()) {
 return false;
 }
 if (size == 0) {
 setAll(c);
 } else if (index == size) {
 appendAll(c);
 } else if (index == 0) {
 prependAll(c);
 } else {
 insertAll(c, getNode(index), index);
 }
 return true;
}

• coderodde: You are wrong. addAll(int index, Collection c) assumes that index == 0 when the list is empty.