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.

    Java program memory state. 1 stack frame; 5 heap objects.Stack frame: main:9 LinkedBasedList myList: reference to object 537 Node newNode: reference to object 538 Node temp: reference to object 539 Heap object 539: Node@539 String item: reference to object 541, "A" Node next: reference to object 542 Heap object 542: Node@542 String item: reference to object 545, "B" Node next: reference to object 546 Heap object 546: Node@546 String item: reference to object 548, "C" Node next: null Heap object 537: LinkedBasedList@537 int size: 3 Node head: reference to object 539 Heap object 538: Node@538 String item: reference to object 540, "F" Node next: null{"summary":"Java program memory state. 1 stack frame; 5 heap objects.","sections":[{"heading":"Stack frame: main:9","items":["LinkedBasedList myList: reference to object 537","Node newNode: reference to object 538","Node temp: reference to object 539"]},{"heading":"Heap object 539: Node@539","items":["String item: reference to object 541, \"A\"","Node next: reference to object 542"]},{"heading":"Heap object 542: Node@542","items":["String item: reference to object 545, \"B\"","Node next: reference to object 546"]},{"heading":"Heap object 546: Node@546","items":["String item: reference to object 548, \"C\"","Node next: null"]},{"heading":"Heap object 537: LinkedBasedList@537","items":["int size: 3","Node head: reference to object 539"]},{"heading":"Heap object 538: Node@538","items":["String item: reference to object 540, \"F\"","Node next: null"]}]}main:9LinkedBasedListmyList537NodenewNode538Nodetemp539Node@539Stringitem541"A"Nodenext542Node@542Stringitem545"B"Nodenext546Node@546Stringitem548"C"NodenextnullLinkedBasedList@537intsize3Nodehead539Node@538Stringitem540"F"Nodenextnull

    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.

    Java program memory state. 1 stack frame; 5 heap objects.Stack frame: main:10 LinkedBasedList myList: reference to object 562 Node newNode: reference to object 563 Node temp: reference to object 564 Heap object 565: Node@565 String item: reference to object 541, "A" Node next: reference to object 564 Heap object 564: Node@564 String item: reference to object 545, "B" Node next: reference to object 566 Heap object 566: Node@566 String item: reference to object 548, "C" Node next: null Heap object 562: LinkedBasedList@562 int size: 3 Node head: reference to object 565 Heap object 563: Node@563 String item: reference to object 540, "F" Node next: null{"summary":"Java program memory state. 1 stack frame; 5 heap objects.","sections":[{"heading":"Stack frame: main:10","items":["LinkedBasedList myList: reference to object 562","Node newNode: reference to object 563","Node temp: reference to object 564"]},{"heading":"Heap object 565: Node@565","items":["String item: reference to object 541, \"A\"","Node next: reference to object 564"]},{"heading":"Heap object 564: Node@564","items":["String item: reference to object 545, \"B\"","Node next: reference to object 566"]},{"heading":"Heap object 566: Node@566","items":["String item: reference to object 548, \"C\"","Node next: null"]},{"heading":"Heap object 562: LinkedBasedList@562","items":["int size: 3","Node head: reference to object 565"]},{"heading":"Heap object 563: Node@563","items":["String item: reference to object 540, \"F\"","Node next: null"]}]}main:10LinkedBasedListmyList562NodenewNode563Nodetemp564Node@565Stringitem541"A"Nodenext564Node@564Stringitem545"B"Nodenext566Node@566Stringitem548"C"NodenextnullLinkedBasedList@562intsize3Nodehead565Node@563Stringitem540"F"Nodenextnull

    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.

    Java program memory state. 1 stack frame; 5 heap objects.Stack frame: main:11 LinkedBasedList myList: reference to object 550 Node newNode: reference to object 551 Node temp: reference to object 552 Heap object 553: Node@553 String item: reference to object 557, "A" Node next: reference to object 552 Heap object 552: Node@552 String item: reference to object 556, "B" Node next: reference to object 555 Heap object 555: Node@555 String item: reference to object 559, "C" Node next: null Heap object 550: LinkedBasedList@550 int size: 3 Node head: reference to object 553 Heap object 551: Node@551 String item: reference to object 554, "F" Node next: reference to object 555{"summary":"Java program memory state. 1 stack frame; 5 heap objects.","sections":[{"heading":"Stack frame: main:11","items":["LinkedBasedList myList: reference to object 550","Node newNode: reference to object 551","Node temp: reference to object 552"]},{"heading":"Heap object 553: Node@553","items":["String item: reference to object 557, \"A\"","Node next: reference to object 552"]},{"heading":"Heap object 552: Node@552","items":["String item: reference to object 556, \"B\"","Node next: reference to object 555"]},{"heading":"Heap object 555: Node@555","items":["String item: reference to object 559, \"C\"","Node next: null"]},{"heading":"Heap object 550: LinkedBasedList@550","items":["int size: 3","Node head: reference to object 553"]},{"heading":"Heap object 551: Node@551","items":["String item: reference to object 554, \"F\"","Node next: reference to object 555"]}]}main:11LinkedBasedListmyList550NodenewNode551Nodetemp552Node@553Stringitem557"A"Nodenext552Node@552Stringitem556"B"Nodenext555Node@555Stringitem559"C"NodenextnullLinkedBasedList@550intsize3Nodehead553Node@551Stringitem554"F"Nodenext555

    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.

    Java program memory state. 1 stack frame; 5 heap objects.Stack frame: main:13 LinkedBasedList myList: reference to object 575 Node newNode: reference to object 576 Node temp: reference to object 577 Heap object 578: Node@578 String item: reference to object 557, "A" Node next: reference to object 577 Heap object 577: Node@577 String item: reference to object 556, "B" Node next: reference to object 576 Heap object 576: Node@576 String item: reference to object 554, "F" Node next: reference to object 579 Heap object 579: Node@579 String item: reference to object 559, "C" Node next: null Heap object 575: LinkedBasedList@575 int size: 4 Node head: reference to object 578{"summary":"Java program memory state. 1 stack frame; 5 heap objects.","sections":[{"heading":"Stack frame: main:13","items":["LinkedBasedList myList: reference to object 575","Node newNode: reference to object 576","Node temp: reference to object 577"]},{"heading":"Heap object 578: Node@578","items":["String item: reference to object 557, \"A\"","Node next: reference to object 577"]},{"heading":"Heap object 577: Node@577","items":["String item: reference to object 556, \"B\"","Node next: reference to object 576"]},{"heading":"Heap object 576: Node@576","items":["String item: reference to object 554, \"F\"","Node next: reference to object 579"]},{"heading":"Heap object 579: Node@579","items":["String item: reference to object 559, \"C\"","Node next: null"]},{"heading":"Heap object 575: LinkedBasedList@575","items":["int size: 4","Node head: reference to object 578"]}]}main:13LinkedBasedListmyList575NodenewNode576Nodetemp577Node@578Stringitem557"A"Nodenext577Node@577Stringitem556"B"Nodenext576Node@576Stringitem554"F"Nodenext579Node@579Stringitem559"C"NodenextnullLinkedBasedList@575intsize4Nodehead578

    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.

    Java program memory state. 1 stack frame; 5 heap objects.Stack frame: main:7 LinkedBasedList myList: reference to object 579 Heap object 580: Node@580 String item: reference to object 541, "A" Node next: reference to object 581 Heap object 581: Node@581 String item: reference to object 545, "B" Node next: reference to object 582 Heap object 582: Node@582 String item: reference to object 540, "F" Node next: reference to object 583 Heap object 583: Node@583 String item: reference to object 548, "C" Node next: null Heap object 579: LinkedBasedList@579 int size: 4 Node head: reference to object 580{"summary":"Java program memory state. 1 stack frame; 5 heap objects.","sections":[{"heading":"Stack frame: main:7","items":["LinkedBasedList myList: reference to object 579"]},{"heading":"Heap object 580: Node@580","items":["String item: reference to object 541, \"A\"","Node next: reference to object 581"]},{"heading":"Heap object 581: Node@581","items":["String item: reference to object 545, \"B\"","Node next: reference to object 582"]},{"heading":"Heap object 582: Node@582","items":["String item: reference to object 540, \"F\"","Node next: reference to object 583"]},{"heading":"Heap object 583: Node@583","items":["String item: reference to object 548, \"C\"","Node next: null"]},{"heading":"Heap object 579: LinkedBasedList@579","items":["int size: 4","Node head: reference to object 580"]}]}main:7LinkedBasedListmyList579Node@580Stringitem541"A"Nodenext581Node@581Stringitem545"B"Nodenext582Node@582Stringitem540"F"Nodenext583Node@583Stringitem548"C"NodenextnullLinkedBasedList@579intsize4Nodehead580

    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.