Getting by Index

The previous chapter reused the traversal pattern in several operations. Let’s pull that pattern into a private helper method that returns the node at a given index.

private Node<T> node(int index) {
  Node<T> current = head;
  for (int i = 0; i < index; i++) {
    current = current.next;
  }
  return current;
}

Suppose we ask for index 2 in this list. current starts at the head:

          ┌────┐      ┌────┐      ┌────┐      ┌────┐
head ───▶ │ 10 │ ◀──▶ │ 20 │ ◀──▶ │ 30 │ ◀──▶ │ 40 │ ◀─── tail
          └────┘      └────┘      └────┘      └────┘
             ▲
             │
          current

After one step, current advances to index 1:

          ┌────┐      ┌────┐      ┌────┐      ┌────┐
head ───▶ │ 10 │ ◀──▶ │ 20 │ ◀──▶ │ 30 │ ◀──▶ │ 40 │ ◀─── tail
          └────┘      └────┘      └────┘      └────┘
                         ▲
                         │
                      current

After the second step, current reaches index 2 and the loop stops:

          ┌────┐      ┌────┐      ┌────┐      ┌────┐
head ───▶ │ 10 │ ◀──▶ │ 20 │ ◀──▶ │ 30 │ ◀──▶ │ 40 │ ◀─── tail
          └────┘      └────┘      └────┘      └────┘
                                     ▲
                                     │
                                  current   (found)

Now get traverses to the node and returns its value:

public T get(int index) {
  return node(index).value;
}

We must guard against an invalid index:

public T get(int index) {
  if (index < 0 || index >= size) {
    throw new IndexOutOfBoundsException();
  }
  return node(index).value;
}

Because the list stores size, we can reject a too-large index right away.

get is $O(n)$ because it traverses the list one node at a time. The number of nodes we visit grows with the size of the list. In contrast, DynamicArray.get(index) is $O(1)$ because it jumps straight to the slot without visiting any other elements.

Starting from the closer end

node(index) always starts at the head and follows next forward. But this is a doubly linked list. Every node has a prev, and the list holds a tail. So for an index near the back, going forward from the head is the longer traversal. We could start at the tail and follow prev backward instead.

This version implements that idea:

private Node<T> node(int index) {
  Node<T> current;
  if (index < size / 2) {
    current = head;
    for (int i = 0; i < index; i++) {
      current = current.next;
    }
  } else {
    current = tail;
    for (int i = size - 1; i > index; i--) {
      current = current.prev;
    }
  }
  return current;
}

Asking for index 2 now takes the back-half branch. current starts at the tail, index 3:

          ┌────┐      ┌────┐      ┌────┐      ┌────┐
head ───▶ │ 10 │ ◀──▶ │ 20 │ ◀──▶ │ 30 │ ◀──▶ │ 40 │ ◀─── tail
          └────┘      └────┘      └────┘      └────┘
                                                 ▲
                                                 │
                                              current

One backward step along prev reaches index 2, the same node the forward traversal found, but in one step instead of two:

          ┌────┐      ┌────┐      ┌────┐      ┌────┐
head ───▶ │ 10 │ ◀──▶ │ 20 │ ◀──▶ │ 30 │ ◀──▶ │ 40 │ ◀─── tail
          └────┘      └────┘      └────┘      └────┘
                                     ▲
                                     │
                                  current   (found)

Cutting the work in half does not change the complexity. Half of $n$ is still proportional to $n$, so node is still $O(n)$, and so is get.