Trace: Building and Changing a List

A linked list here is a sequence of ListItem objects. Each one holds a value and a next reference. Here are the four operations we will use. addFirst(head, value) inserts at the front and returns the new head. addLast(head, value) inserts at the back and returns the head. insertAfter(head, index, value) inserts after the item at index. remove(head, index) deletes the item at index and returns the new head.

Solution

After step 1:

         ┌────┐
head ──▶ │ 11 │ ──▶ null
         └────┘

After step 2:

         ┌────┐     ┌────┐
head ──▶ │ 24 │ ──▶ │ 11 │ ──▶ null
         └────┘     └────┘

After step 3:

         ┌────┐     ┌────┐     ┌────┐
head ──▶ │ 24 │ ──▶ │ 11 │ ──▶ │ 38 │ ──▶ null
         └────┘     └────┘     └────┘

After step 4 (inserting after the item at index 1, the item with value 11):

         ┌────┐     ┌────┐     ┌────┐     ┌────┐
head ──▶ │ 24 │ ──▶ │ 11 │ ──▶ │ 46 │ ──▶ │ 38 │ ──▶ null
         └────┘     └────┘     └────┘     └────┘

After step 5 (removing the item at index 0):

         ┌────┐     ┌────┐     ┌────┐
head ──▶ │ 11 │ ──▶ │ 46 │ ──▶ │ 38 │ ──▶ null
         └────┘     └────┘     └────┘