Linked-list updates, deletion and storage reuse
Objectives and representation contracts
Extend front insertion to insertion after a known predecessor, deletion at all positions, and reuse of storage. We compare two representations of the same singly linked list: heap-allocated nodes connected by pointers, and a bounded array of slots connected by integer indices. This is sequential execution, with distinct live nodes and no cycles. Search is by position or key as specified. Nodes own their successor chain only under an explicit exclusive-ownership contract; shared-list deallocation is outside these examples.
For the bounded model, valid slots are 0..N−1 and NIL=−1 denotes no node. Arrays value[i] and next[i] describe slot i. head points to the first live slot; freeHead points to a disjoint free list of unused slots. Every slot is either reachable exactly once from head or exactly once from freeHead. Never index the arrays with NIL. In the pointer model, NULL plays the absent-link role, and malloc/free replace free-list acquisition/release.
1. Insert after a known live predecessor
Suppose logical list A→B→C and predecessor p denotes B. A new node X must point to C before B is redirected to X:
new.next = p.next p.next = new
The final list is A→B→X→C. Reversing these two assignments makes new.next point to new and disconnects the old suffix unless its address was separately saved. Allocation and field initialization must succeed before the live structure is changed. With a known predecessor, rewiring is O(1); finding the predecessor may take O(n). Insertion at position k in a zero-based length-n list allows 0≤k≤n. k=0 updates head; for k>0 find position k−1, including the old tail for append. A tail pointer makes append O(1) if it is maintained, but does not make arbitrary predecessor search O(1).
Worked bounded trace: N=5, head=2, live links 2→0→4→NIL with values A,B,C. Free links are 1→3→NIL. Insert X after slot 0. Pop slot 1 by freeHead=next[1]=3. Set value[1]=X and next[1]=next[0]=4; then next[0]=1. Live links become 2→0→1→4, freeHead=3. Physical order 0,1,2,3,4 is unrelated to logical traversal order. If freeHead=NIL, report full and preserve the existing list; this is the bounded equivalent of allocation failure.
2. Delete by predecessor; handle the head separately
To delete the successor of a known live predecessor p, first check p.next is not absent. Save victim=p.next, save successor=victim.next, set p.next=successor, then release victim. A tail deletion simply installs the absent link. Deleting head has no ordinary predecessor. If head is absent, leave the empty list unchanged; otherwise save victim=head, set head=head.next, then release victim. For a singleton, this makes head absent. If a tail pointer is used, deleting its node must update tail to the predecessor; deleting the sole node sets both head and tail absent.
Worked continuation: delete B at slot 0 in the previous trace. Its predecessor is slot 2 and its successor is slot 1. Set next[2]=1, then push freed slot 0 onto the free list by next[0]=freeHead=3 and freeHead=0. Live traversal is 2→1→4 (A,X,C), free traversal 0→3. The former link 0→1 is no longer a live link; its next field now serves the free-list structure. Reading a pointer node after free is undefined in C; in the bounded model, reading a released slot may be physically in bounds but logically accesses someone else's/free storage.
Deleting the first node equal to a key requires tracking prev and cur during traversal. Initially prev=absent,cur=head. Move prev=cur then cur=cur.next until found or absent. If not found, leave the list unchanged. If prev is absent, update head; otherwise update prev.next. Duplicate values do not identify unique nodes, so “first matching key” is an important policy.
3. Release and reuse without stale aliases
Continue the bounded example: acquire slot 0 from freeHead to append Y after C at slot 4. freeHead becomes 3; value[0]=Y, next[0]=NIL, next[4]=0. Live links now 2→1→4→0 (A,X,C,Y). The integer 0 previously denoted B and now denotes Y. A saved external index 0 is not a stable node identity across deletion and reuse. In the pointer model, allocator address reuse likewise does not make a dangling pointer valid again. Algorithms needing long-lived handles require an additional validity scheme; this lesson merely invalidates all external handles to a released node.
To clear a pointer list safely, save next before free at each iteration. To clear a bounded list, save the live successor before repurposing next for the free list. Releasing a slot twice can create cycles in the free list; freeing a heap node twice is undefined behavior. A stale next link or a missing head update can make nodes unreachable (a leak) even when array indices are individually in bounds.
4. What O(1) deletion really assumes
A pointer/index to the predecessor permits O(1) unlinking its successor. A pointer to the target alone does not generally permit O(1) deletion in a singly linked list because the incoming link must be found. The “copy successor value into target, then remove successor” trick cannot remove the tail, changes which physical node survives, and can violate identity/ownership requirements. It is not a general replacement for predecessor-aware deletion. A doubly linked list supports local unlinking from a known node because it stores the previous link, but it must also repair both neighbors and head/tail.
Invariant checklist and costs
After each operation, traverse the live chain to check order, termination and exact count. In a bounded pool, also verify live/free disjointness and that counts sum to N. Search takes O(n) worst case; update after a supplied predecessor takes O(1), excluding allocator cost. Total storage is O(n) live nodes in the pointer model or O(N) slots in the fixed pool. Logical position, key value, physical index and object identity are four different things.
Original practice: six single-correct MCQs
These original teaching questions are not previous-year questions. Choose one answer.
P01. To insert new after p while preserving the suffix, use:
A. p.next=new; new.next=p.next; B. new.next=p.next; p.next=new; C. new.next=p; p.next=NULL; D. head=new; new.next=NULL;
Answer: B
A: The second assignment makes new point to itself.
B: Save the old successor in new before redirecting p.
C: This loses the required successor and reverses a link.
D: This discards the previous list rather than inserting after p.
P02. Live slots 2→0→4 and free slots 1→3. Insert slot 1 after slot 0. New live order?
A. 0→1→2→4 B. 2→1→0→4 C. 2→0→1→4 D. 2→0→4→1
Answer: C
A: Physical indices do not prescribe list order.
B: This inserts before slot 0, not after.
C: The old 0→4 link becomes 0→1→4.
D: This appends at the tail instead.
P03. Deleting the sole node with head and tail maintained must leave:
A. Both head and tail absent B. Only head absent C. Only tail absent D. Both pointing at the released node
Answer: A
A: The empty-list invariant requires both absent.
B: A stale tail violates the invariant.
C: A stale head violates the invariant.
D: Released storage cannot remain a live node.
P04. Worst-case search for a predecessor in an n-node singly linked list without auxiliary indexing costs:
A. O(1) B. O(log n) C. O(n²) D. O(n)
Answer: D
A: Only rewiring after a known predecessor is constant time.
B: There is no random midpoint access/search-tree guarantee.
C: A single traversal is enough.
D: The predecessor may require traversing almost the entire list.
P05. A freed bounded slot 0 is reused for a new node. A saved old handle 0:
A. Still identifies the old node B. Is automatically updated to a different index C. Is stale as an identity handle despite being in bounds D. Proves the allocator is incorrect
Answer: C
A: The old logical node no longer exists.
B: Plain integers are not automatically rewritten.
C: Storage position can be reused for a different identity.
D: Reuse is intended behavior; clients must invalidate old handles.
P06. The successor-copy deletion trick for a known singly linked target fails generally because:
A. It always takes O(n²) B. It cannot delete a tail and may violate node identity C. It requires a sorted list D. It never changes stored values
Answer: B
A: The local copying work can be constant.
B: There is no successor at the tail; elsewhere a different physical node is removed.
C: Sorting is unrelated to this limitation.
D: The trick explicitly overwrites the target value.
Sources and scope
GATE CS 2026 bounded extension of existing foundations. Not a whole-subject completion claim. Examples and questions are original.
Sign in to keep your progress. Sign in