N2Insert at tail
Compare traversal without a tail pointer against direct insertion with one.
1#include <cstddef>2struct Node {3int value;4Node* next;5};67Node* insertTail(Node* head, int value) {8Node* newNode = new Node{value, nullptr};9if (head == nullptr) return newNode;10Node* current = head;11while (current->next != nullptr) {12current = current->next;13}14current->next = newNode;15return head;16}
N1nullnullnullnullN5nullnullN3N4nullnullheadN1
tailnull
currentnull
previousnull
nextnull
newNodenull
slownull
fastnull
recursiveDepth0
resultnull
resultIndexnull
nodesN1(12)→N2 · N2(27)→N3 · N3(41)→N4 · N4(56)→null
headN1
tailnull
currentnull
previousnull
nextnull
newNodeN5
slownull
fastnull
recursiveDepth0
resultnull
resultIndexnull
nodesN1(12)→N2 · N2(27)→N3 · N3(41)→N4 · N4(56)→null · N5(73)→null
pointer-newNode.target null → N5 move
N5.node null → {"id":"N5","value":73,"next":null,"status":"allocated"} insert
allocated.value — → N5 highlight
operationCount.value 0 → 3 highlight
cumulativeWork.value {} → {"allocation":1,"write":1,"pointer-write":1} highlight
O(n) time · O(1) space
worstA bounded number of scalar/reference slots is reused, so auxiliary storage stays constant.
- Traverse through the list before changing the terminal next reference.
- The traversal advances through at most n next references.
- Fixed work per visited node sums to O(n), while a fixed pointer set uses O(1) space.
Assumptions behind this claim
- Each node stores one next reference and the list is singly linked.
- The terminal node must be found from head.
- Each displayed pointer read, pointer write, comparison, allocation, call, or return is one counted primitive.
- Trace construction and visualization bookkeeping are excluded from the algorithm count.
Create a terminal candidate containing 73.
About this implementation
A singly linked list reaches each node only through the previous node's next pointer. Inserting at the head is O(1); inserting at the tail is O(n) without a tail pointer but O(1) with one. Reversal rewires every next pointer; Floyd's slow/fast pointers detect a cycle in O(n) with O(1) space.