Getting the Item Itself

Our get operation returns the value stored at an index. But sometimes what we want is the item at that index, the ListItem object itself, not just the value inside it. For example, we may want to get the last item so we can add a new item after it.

public static ListItem getListItem(ListItem head, int index) {
  ListItem current = head;
  for (int i = 0; i < index; i++) {
    current = current.next;
  }
  return current;
}

This is the same traversal we used in get. The only difference is the last line: get returns current.value, while getListItem returns current itself. In fact, once we have getListItem, our get can call it:

public static int get(ListItem head, int index) {
  return getListItem(head, index).value;
}

So why return the item instead of its value? Because a reference to an item lets us work on the list at that position directly.

Look back at insertAfter. It takes an index, and the first thing it does is traverse to the item at that index. Then it splices. But that traversal is not part of the insertion. It is there only to find the item to insert after. If we are given that item directly, say one we got from getListItem, we do not need the traversal at all.

Let’s rewrite insertAfter so it takes the ListItem to insert after, instead of the head and an index. The traversal is gone, and only the splice is left:

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

This version is $O(1)$ in time. It creates one item and sets two references, so it is constant time, no matter how long the list is.

Two smaller things changed as well. The method no longer takes the head, because item is all it needs. And it returns nothing, because inserting after an existing item can never displace the first item.