Structural Operations by Index

A linked list here is a sequence of ListItem objects connected by next references:

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

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

Operations that change the front of the list can change which item is head. head is the caller’s variable, and the operation cannot reassign it from inside. So an operation that can change the front returns the head, and the caller reassigns it: head = addFirst(head, value).

Solution

public static ListItem addFirst(ListItem head, int value) {
  ListItem newItem = new ListItem(value);
  newItem.next = head;
  return newItem;
}

Solution

addFirst is $O (1)$ : it creates one item, sets one reference, and returns. Prepending to an array is $O (n)$ , since every existing element has to shift one slot to make room.

Solution

public static ListItem addLast(ListItem head, int value) {
  if (head == null) {
    return new ListItem(value);
  }
  ListItem current = head;
  while (current.next != null) {
    current = current.next;
  }
  current.next = new ListItem(value);
  return head;
}

Solution

addLast is $O (n)$ : finding the last item takes a full traversal, since there is no direct reference to it. addFirst is $O (1)$ because the head is already known; addLast has no equivalent shortcut to the last item.

Solution

addLast could attach the new item directly to tail.next and move tail forward, with no traversal — $O (1)$ instead of $O (n)$ . Without a stored tail reference, the only way to find the last item is to walk the whole list from the head.

Solution

public static ListItem remove(ListItem head, int index) {
  if (index == 0) {
    return head.next;
  }
  ListItem previous = head;
  for (int i = 0; i < index - 1; i++) {
    previous = previous.next;
  }
  previous.next = previous.next.next;
  return head;
}

Solution

Best case is $O (1)$ , removing index 0 with no traversal. Worst case is $O (n)$ , traversing to the predecessor of the last item. Removing from an array is also $O (n)$ worst case, but for a different reason: there is no traversal, but every element after the removed one has to shift left to close the gap.

Solution

head.next is null in a one-item list, so remove returns null. The caller reassigns head = null, and the list is empty.

Solution

addFirst, addLast on an empty list, and remove at index 0 can each change which item is first: addFirst always makes a new item first, addLast on an empty list makes the one new item both first and last, and removing index 0 removes the current first item. insertAfter always attaches after an existing item, so the item that was first stays first; the head never changes, and there is no new head to return.