Append Operation

Prepending adds an item to the front of the list. The opposite is appending: adding an item to the back.

Here is the list we start with:

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

As before, we begin by creating a new item to hold the value (say, 9):

ListItem newItem = new ListItem(value);

Here is the schematic:

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

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

For appending, we need the new item placed after the last item. Unlike prepending, we do not have a direct reference to the last item. The only way to find it is to start at the head and traverse until we reach the item whose next is null. That is the last item.

ListItem current = head;
while (current.next != null) {
  current = current.next;
}

Here is the schematic after the traversal:

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

Now current points to the last item (value 7). We attach the new item by setting the last item’s next to newItem:

current.next = newItem;

And that gives us the appended list:

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

Here is a complete implementation of addLast that returns the head of the list:

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

Returning the head seems unnecessary, since the head does not change. It is consistent with addFirst, which does return the new head. And it is needed in the case of an empty list.

If head is null, there is no last item to attach to, and current.next would throw a NullPointerException. In that case the new item becomes the whole list, so it is the new head.

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;
}

On a single-item list, the implementation needs no special handling: current.next != null is false immediately, so current stays on the head and we attach the new item to it.

addLast is $O (n)$ in time because of the traversal to find the last item. The actual attaching at the end is $O (1)$ , but we cannot get there without traversing the whole list first. Appending to an array is cheaper if the array has enough space.

addLast is $O (1)$ in auxiliary space since it allocates only one new item and uses a constant number of references for the traversal.