Access and Search

These questions are about LinkedList<T>, a private doubly linked, generic node type with head, tail, and size fields:

public class LinkedList<T> {
  private Node<T> head;
  private Node<T> tail;
  private int size;

  private static class Node<T> {
    T value;
    Node<T> next;
    Node<T> prev;
  }
}

Solution

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

Solution

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

$O (n)$ : reaching the node takes up to index steps, unlike an array, which computes the slot directly in $O (1)$ .

Solution

get returns the value stored at the index, not the node holding it, so overwriting that returned value would only change a local copy. The list itself would be untouched. set needs the node itself so it can overwrite the node’s value field directly:

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

Solution

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

This cuts the number of steps roughly in half. The worst case moves from the last index to the middle index. It does not change the complexity: half of $n$ is still proportional to $n$ , so node, and everything built on it, is still $O (n)$ . It is a constant-factor speedup, not an improvement in order of growth.

Solution

public int indexOf(T value) {
  Node<T> current = head;
  int index = 0;
  while (current != null) {
    if (Objects.equals(current.value, value)) {
      return index;
    }
    current = current.next;
    index++;
  }
  return -1;
}

== compares references, so two distinct objects that are equal in content, such as two separate String objects both holding "cat", would not match. Objects.equals compares contents by calling .equals, and it is null-safe on both sides, so it also handles a null value already in the list or a null search target without throwing.

Solution

public boolean contains(T value) {
  return indexOf(value) != -1;
}