Traversal and Read-Only Operations

A linked list here is built from ListItem objects:

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

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

The operations below traverse the list with a current reference, starting at head.

Solution

public static int size(ListItem head) {
  int count = 0;
  ListItem current = head;
  while (current != null) {
    count++;
    current = current.next;
  }
  return count;
}

Solution

size is $O (n)$ for a linked list, since it has to visit every item to count them. An array stores its length as a single number, so reading it is $O (1)$ .

Solution

public static boolean contains(ListItem head, int target) {
  ListItem current = head;
  while (current != null) {
    if (current.value == target) {
      return true;
    }
    current = current.next;
  }
  return false;
}

Solution

current.next != null. With current != null, the loop keeps advancing until current itself becomes null, which is one step past the last item. With current.next != null, the loop stops as soon as current.next is null, which happens while current is still on the last item, so addLast can change its next.

Exercise

Here is get for a linked list, with no validation:

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

Trace what happens on a call with a negative index, and separately on a call where index is past the end of the list. In neither case does the result tell the caller that the index was invalid — why not?

Solution

With a negative index, the loop condition i < index is false immediately, so current stays at head and get returns the head’s value, a plausible-looking result with no error at all. With an index past the end, current walks off the list and becomes null; the next step in the loop, or the final current.value, throws a NullPointerException. Neither outcome flags the index itself as the problem: the negative case fails silently, and the too-large case’s exception comes from chasing a null reference, not from a check on the index.

Solution

Best case is $O (1)$ , when index is 0 and no steps are needed. Worst case is $O (n)$ , when index is the last position and the traversal has to visit every item in the list.