Linked List Structure Modification and Pointer Logic: Worked Insertions, Deletions and Exam Traces

Trace one address-labelled linked list through insertion, deletion, reversal, and head changes. Each operation shows which link must be saved and what can go wrong.

KnowledgeGate Team

Exam prep & CS education

Updated 5 Nov 20265 min read
Linked List Structure Modification and Pointer Logic: Worked Insertions, Deletions and Exam Traces

A linked-list update may contain two pointer assignments, yet reversing them can lose the remaining list, create a self-loop, or leave the caller's head unchanged. Address labels make reachability, insertion, deletion, reversal, and head modification traceable. Linear singly linked lists isolate link-rewrite order, head changes, and reversal. Doubly and Circular Linked Lists Explained adds backward-link and ring invariants.

A singly linked-list node contains data and a next pointer. Structure modification changes links, and sometimes head. Unlike an array insertion, it does not shift values.

Treat these addresses as symbolic labels, not as locations a program can choose:

head = 100

[100|8] -> [240|14] -> [360|21] -> NULL

Their fields give 100.next = 240, 240.next = 360, and 360.next = NULL. The reachable data sequence is 8 -> 14 -> 21.

After every modification, check three invariants:

  1. Every intended node is reachable from head.

  2. The last intended node points to NULL.

  3. No address is visited twice, unless a cycle was deliberately created.

Use these checks across linked structures in CS Fundamentals.

Insert a new node [520|17] immediately after node 240. Let p = 240 and new = 520. The safe order is:

  1. new->next = p->next, so 520.next = 360.

  2. p->next = new, so 240.next = 520.

The result is [100|8] -> [240|14] -> [520|17] -> [360|21] -> NULL, representing 8 -> 14 -> 17 -> 21.

Now reverse those assignments. After p->next = new, node 240 already points to 520. The next statement, new->next = p->next, therefore assigns 520 to 520.next. Traversal becomes 100 -> 240 -> 520 -> 520 -> ..., while node 360 is unreachable from head.

Copy the link that must survive before overwriting its owner. If p, new, p->next, and new->next blur together, revise Pointers in C for GATE.

Correct versus incorrect insertion of node 520 after node 240, and the self-loop the reversed order creates.

Deletion: Bypass First, Free Last

Continue from the correctly inserted four-node list and delete node 520. With predecessor p = 240:

  1. Set victim = p->next, so victim = 520.

  2. Read victim->next, which is 360.

  3. Set p->next = victim->next, so 240.next = 360.

  4. Call free(victim).

The restored chain is [100|8] -> [240|14] -> [360|21] -> NULL.

Calling free(p->next) first is invalid because finding 360 would then require dereferencing freed storage. Any separate pointer storing 520 becomes dangling, even though traversal from head is correct.

If p = 240 is available, bypassing its successor is O(1). Searching from head for 17 or its predecessor is O(n). Deleting the head is a separate case because it has no predecessor.

Linked List Reversal: A Complete Three-Pointer Trace

Reverse the restored chain 100 -> 240 -> 360 -> NULL. Initialise prev = NULL and curr = 100. Repeat these statements in order:

next = curr->next; curr->next = prev; prev = curr; curr = next;

Temporary next preserves the unprocessed suffix before the outgoing edge changes.

State

Saved next

Changed edge

prev after step

curr after step

Initial

not set

none

NULL

100

Iteration 1

240

100.next = NULL

100

240

Iteration 2

360

240.next = 100

240

360

Iteration 3

NULL

360.next = 240

360

NULL

Finally, assign head = prev. The list becomes [360|21] -> [240|14] -> [100|8] -> NULL, and its data sequence is 21 -> 14 -> 8.

The loop invariant is this: nodes at and behind prev form the reversed prefix, while curr begins the untouched suffix. Each node belongs to exactly one part. At curr = NULL, the suffix is empty and prev is the new head.

Four stages of reversing the list 100, 240, 360, with prev, curr and the saved next value at each step.

Head-Changing Operations and Pointer-to-Pointer Parameters

Return to the original list with head = 100. To insert [80|5] at the front, first set 80.next = 100, then update the caller's head to 80. The result is [80|5] -> [100|8] -> [240|14] -> [360|21] -> NULL.

C offers two correct interfaces: return a new Node * for the caller to assign, or accept Node **head_ref and assign *head_ref = 80.

A function receiving only Node *head gets a copy. Rebinding local head to 80 does not change the caller's variable. Changing head->next instead mutates a reached node.

To delete the new first node through a pointer-to-pointer, set victim = *head_ref, giving 80; set *head_ref = victim->next, giving the caller head = 100; then free 80.

Structure Modification Traps and a Mechanical Repair Method

Pair each failure with a repair:

  • About to overwrite the only link to a suffix? Save that link first.

  • About to access p->next? Check that p is not NULL.

  • Finished free(520)? Stop using or clear every alias that stores 520.

  • Changing the first node? Return the new head or pass Node **.

  • Nodes contain equal values? Compare node identity when identity matters.

Three defects need different checks. A lost node such as 360 exists but is unreachable. A dangling pointer stores 520 after that node's lifetime ends. A cycle revisits an address, as in 520 -> 520.

For any trace, draw five columns: statement number, head, named pointer values, changed next field, and reachable chain from head. Fill one row immediately after each assignment. Never mentally combine two pointer writes.

How Exams Test Linked List Pointer Traces

Start again with [100|8] -> [240|14] -> [360|21] -> NULL and execute:

  1. p = head->next, so p = 240.

  2. q = p->next, so q = 360.

  3. p->next = head, creating edge 240 -> 100.

  4. head->next = q, keeping edge 100 -> 360.

  5. head = p, so head = 240.

The final reachable chain is [240|14] -> [100|8] -> [360|21] -> NULL. The printed data sequence is 14 8 21; q still points to 360; no address repeats, so there is no cycle.

Questions may ask for the output, final head, unreachable nodes, cycles, dangling aliases, link changes, safe assignment order, or O(1) modification versus O(n) search. Use structural reasoning, never compiler-dependent address arithmetic. There are about ten practice questions on structure modification and pointer logic. Continue with Data Structures MCQs for focused practice.

The Short Version and the Next Practice Step

Keep five rules close: draw addresses, save links before overwriting them, bypass before freeing, update the caller's head when the first node changes, and walk from head until NULL or a repeated address.

For a 15-minute exercise, start with [610|4] -> [725|9] -> [880|12] -> NULL. Insert [790|10] after 725, delete node 610 by updating head, then reverse the remaining list. Record every saved pointer and changed next field before checking your work.

Checkpoints are 610 -> 725 -> 790 -> 880, then 725 -> 790 -> 880, then 880 -> 790 -> 725 -> NULL. The final data is 12 -> 10 -> 9.

To place data structures beside the rest of GATE CS, continue with GATE Guidance by Sanchit Sir.