Operating on a ListItem Directly

A linked list here is a sequence of ListItem objects:

public class ListItem {
  public int value;
  public ListItem next;

  public ListItem(int value) {
    this.value = value;
  }
}

The operations in this section take a ListItem directly, rather than a head and an index.

Solution

public static void insertAfter(ListItem item, int value) {
  ListItem newItem = new ListItem(value);
  newItem.next = item.next;
  item.next = newItem;
}

Solution

The index-based version has to traverse from the head to reach the item at index before it can splice. This version is given the item directly, so it can splice without traversing first.

Solution

No. Removing item means setting its predecessor’s next to item.next, but the predecessor’s next is not reachable from item, since next only points forward. Finding the predecessor means traversing from the head until reaching the item whose next is item, which is $O (n)$ , even though item itself was already given.