Adding and Removing

These questions are about LinkedList<T>, a 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;

    Node(T value) {
      this.value = value;
    }
  }

  // node(index), indexOf(value), and the rest of the class exist too.
}

Solution

public void add(T value) {
  Node<T> newNode = new Node<>(value);
  if (head == null) {
    head = newNode;
    tail = newNode;
  } else {
    newNode.prev = tail;
    tail.next = newNode;
    tail = newNode;
  }
  size++;
}

$O (1)$ : tail already points at the last node, so there is no traversal, just a fixed number of reference assignments and an increment.

Solution

target.prev.next = target.next;
target.next.prev = target.prev;

Solution

If target is the first node, target.prev is null, so target.prev.next throws a NullPointerException; symmetrically, if target is the last node, target.next is null. Removing the first node also means head has to move forward to the next node, and removing the last means tail has to move back.

public T remove(int index) {
  if (index < 0 || index >= size) {
    throw new IndexOutOfBoundsException();
  }
  Node<T> target = node(index);
  T removed = target.value;

  if (target.prev == null) {
    head = target.next;
  } else {
    target.prev.next = target.next;
  }

  if (target.next == null) {
    tail = target.prev;
  } else {
    target.next.prev = target.prev;
  }

  size--;
  return removed;
}

Solution

$O (n)$ . Unlinking itself is $O (1)$ : a fixed number of reference reassignments regardless of list length. The $O (n)$ comes entirely from node(index), the traversal needed to reach the target node from an index.

Solution

public boolean remove(T value) {
  int index = indexOf(value);
  if (index == -1) {
    return false;
  }
  remove(index);
  return true;
}

$O (n)$ : indexOf traverses to find the match, which is $O (n)$ , and remove(index) then traverses again to reach that index, also $O (n)$ . Two $O (n)$ passes in a row is still $O (n)$ .

Solution

remove(2) resolves to the remove(int index) overload, removing whatever value sits at index 2. Java matches the int literal to the int parameter before considering autoboxing to Integer. To remove the value 2, pass an Integer explicitly, e.g. remove(Integer.valueOf(2)).