Prepend Operation

Let’s add an item to the front of a linked list, which is called prepending.

Here is the list we start with:

         ┌───┐     ┌───┐     ┌───┐
head ──▶ │ 3 │ ──▶ │ 5 │ ──▶ │ 7 │ ──▶ null
         └───┘     └───┘     └───┘

Say we want to prepend the value 9. The first step is to create a new item to hold it:

ListItem newItem = new ListItem(value);

Here is the schematic:

            ┌───┐     ┌───┐     ┌───┐
   head ──▶ │ 3 │ ──▶ │ 5 │ ──▶ │ 7 │ ──▶ null
            └───┘     └───┘     └───┘

            ┌───┐
newItem ──▶ │ 9 │ ──▶ null
            └───┘

For the new item to be in front of the list, its next must point to the item that is currently first (the one with value 3). That item is what head points to, so we set:

newItem.next = head;

Here is the schematic after that assignment:

            ┌───┐     ┌───┐     ┌───┐
   head ──▶ │ 3 │ ──▶ │ 5 │ ──▶ │ 7 │ ──▶ null
            └───┘     └───┘     └───┘
              ▲
              │
            ┌───┐
newItem ──▶ │ 9 │
            └───┘

Notice that head still points to the item with value 3. The item with value 9 is the new first item, so newItem should be the new head:

head = newItem;

Here is the final schematic:

             ┌───┐     ┌───┐     ┌───┐     ┌───┐
    head ──▶ │ 9 │ ──▶ │ 3 │ ──▶ │ 5 │ ──▶ │ 7 │ ──▶ null
             └───┘     └───┘     └───┘     └───┘
               ▲
               │
            newItem

Let’s put this together into a method called addFirst that takes the current head and a value to prepend, and returns the new head:

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

The caller uses it like this, reassigning head to the returned item:

head = addFirst(head, 9);

This is different from get, set, and contains. Those operations do not change the head, so the caller passes head in and never has to update it. addFirst does change the head, so it returns the new head and the caller must capture it. If you forget to write head = ..., the new item is created and linked but head still points at the old first item, so the new item is not in the caller’s list. A class that owns the head field internally would avoid this by updating its own field instead of returning.

addFirst is $O(1)$ in time. It does the same small amount of work no matter how long the list is: create one item, set one next reference, and return. There is no traversal. It is also $O(1)$ in auxiliary space, since we allocate exactly one new item.

Prepending to an array is more expensive, as you already know. To put a value at index 0, every existing element has to move one slot to the right to make room, and that shifting is $O(n)$ work. If the array is already full, we also have to allocate a larger array and copy everything over.

Note this implementation works even if the list is empty. In that case, head is null, so the new item’s next is set to null. The new item becomes the only item in the list, and we return it as the new head.