← DSA I

Pointer execution laboratory

Linked List Lab

0/15 traced

Insert at tail

Compare traversal without a tail pointer against direct insertion with one.

worst case O(n) time O(1) space
1#include <cstddef>
2struct Node {
3 int value;
4 Node* next;
5};
6
7Node* insertTail(Node* head, int value) {
8 Node* newNode = new Node{value, nullptr};
9 if (head == nullptr) return newNode;
10 Node* current = head;
11 while (current->next != nullptr) {
12 current = current->next;
13 }
14 current->next = newNode;
15 return head;
16}
headN1
tailnull
currentnull
previousnull
nextnull
newNodeN5
slownull
fastnull
N1 12
nextN2
→ N2
N2 27
nextN3
→ N3
N3 41
nextN4
→ N4
N4 56
nextnull
→ null
N5 73
nextnull
allocated
→ null
TraversedAllocatedDetachedDeleted Reconnected
Exact work through this line 3 +3 on this line
O(n) time O(1) auxiliary space 0 peak reported values
0comparisons
0reads
1writes
0pointer reads
1pointer writes
0swaps
1allocations
0deallocations
0node visits
0iterations
0calls
0returns
Variables before line

headN1

tailnull

currentnull

previousnull

nextnull

newNodenull

slownull

fastnull

recursiveDepth0

resultnull

resultIndexnull

nodesN1(12)→N2 · N2(27)→N3 · N3(41)→N4 · N4(56)→null

Variables after line

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

Reads, writes, and state changes on this line

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

Why this bound?

O(n) time · O(1) space

worst
node 1node 2node 3node 4 Work can grow once per node → n
Auxiliary memory model
cursortemporarycounter

A bounded number of scalar/reference slots is reused, so auxiliary storage stays constant.

  1. Traverse through the list before changing the terminal next reference.
  2. The traversal advances through at most n next references.
  3. 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.
Step 1 of 11 · insert-tail-allocate Allocate N5

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.

1 / 11