Removing by Value

We have an overloaded remove method that takes a value instead of an index. It finds the first occurrence of the value and removes it, returning true if it was found and removed, or false if it was not found. Here is the implementation:

public boolean remove(T value) {
  int index = indexOf(value);
  if (index == -1) {
    return false;  // not in the list, nothing removed
  }
  remove(index);  // reuse the index-based removal
  return true;
}

This is $O(n)$ but it does two traversals of the list. The first is indexOf, which searches for the value, and the second is remove(index), which searches for the node at that index. We could avoid the second traversal by overloading the node method to take a value and return the first node with that value.

private Node<T> node(T value) {
  Node<T> current = head;
  while (current != null) {
    if (Objects.equals(current.value, value)) {
      return current;
    }
    current = current.next;
  }
  return null;  // not found
}

Now we can implement remove(value) without a second traversal:

public boolean remove(T value) {
  Node<T> target = node(value);
  if (target == null) {
    return false;  // not in the list, nothing removed
  }
  if (target.prev == null) {
    head = target.next;
  } else {
    target.prev.next = target.next;
  }
  if (target.next != null) {
    target.next.prev = target.prev;
  } else {
    tail = target.prev;
  }
  size--;
  return true;
}

Notice the removal code is the same as in remove(index). Let’s refactor that into a private helper method that takes a node and unlinks it from the list. Then both remove(index) and remove(value) can call that helper.

// target is guaranteed to be in the list
private void unlink(Node<T> target) {
  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--;
}

Now remove(index) and remove(value) can be simplified:

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

public boolean remove(T value) {
  Node<T> target = node(value);
  if (target == null) {
    return false;  // not in the list, nothing removed
  }
  unlink(target);
  return true;
}