Setting an Item by Index

The get operation reads the value at a given index. The set operation writes a value at a given index. Let’s write set for a linked list:

public static void set(ListItem head, int index, int value) {
  // TODO
}

This is the same problem we solved for get, except that instead of returning the value at that position, we overwrite it:

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

For an array, set is $O(1)$: we access the index directly and assign the value, regardless of the array’s size. For a linked list, it is $O(n)$ because we have to traverse from the head to reach position index.

Like get, set has to handle invalid indices, but this implementation leaves that out.