8.8. Linked List Add Operation

A linked list can grow by allocating a new node and updating links. The snapshots below illustrate the steps needed for myList.add(2, "F") in a list containing "A", "B", and "C". The list initially has size 3, and index 2 is a valid insertion index.

Each snapshot shows the state after the described step is completed. Construction of the initial list is hidden, and the models show only the fields needed for this example. String values use a compact display: each item field stores a reference value, and the corresponding String object exists separately from the node. An arrow connects each string reference box to a literal beside it.

1. Create a node whose item field stores a reference to the string "F" and whose next field stores null. Initialize temp with a copy of the reference value stored in myList.head. Both temp and head refer to the node at index 0, whose item is "A". The new node is not yet part of the list, so the size is still 3.

   

   The new F node is separate from the three-item list; temp and head refer to A. [download] [open]

2. Follow one link by copying the reference value in temp.next into temp. Now temp refers to the node at index 1, whose item is "B". This is the node immediately before the insertion index. Reassigning temp leaves head and all links unchanged.

   

   temp refers to B, the predecessor of the insertion position; head still refers to A. [download] [open]

3. Copy the reference value in temp.next into newNode.next. The new node now links to the node whose item is "C". The node whose item is "B" still links directly to that same node. Save this successor reference before replacing temp.next; reversing these two assignments would make the new node link to itself and disconnect the original successor from the list.

   

   Both B and the new F node link to C; the list size remains 3. [download] [open]

4. Copy the reference value in newNode into temp.next, then increment the list's size. The node whose item is "B" now links to the new node, which links to the node whose item is "C". The list contains "A", "B", "F", and "C", in that order, and its size is 4. Its head still refers to the first node.

   

   After insertion and the size update, the list contains A, B, F, C and has size 4. [download] [open]

5. The final snapshot shows the same completed list without the traversal variables temp and newNode. No further link changes are needed. The new item is at index 2, and the item previously at index 2 is now at index 3; the existing nodes have not moved in memory.

   

   The completed list: A, B, F, C, with size 4 and no traversal variables. [download] [open]

This example inserts after an existing node. Inserting at index 0 requires updating head because there is no predecessor node.

Compare these steps to insertion in an array-based list. Finding the predecessor in a linked list requires traversal. Once that node is known, inserting the new node requires a fixed number of reference assignments and a size update, regardless of the list's length. An array-based list may need to shift items to make room even when its array has spare capacity. If the array is full, it also needs a larger array and must copy the existing items. The relative cost therefore depends on the insertion position and available capacity; neither implementation is always faster.