Skip to main content

Insert and delete before a node, singly linked

Short answer

To insert before a key node: if key is the first node, make the new node the new start; otherwise, traverse with prev and cur to link the new node between pred and cur. To delete the node before a key: traverse with two trailing pointers to find the predecessor of the target, skip it, and free it. Both take O(n).

Write algorithms to insert and delete a node before a node in a singly linked list.

Let start point to the first node of a singly linked list of nodes (info, next), and let key be the info value of the given node (the one before which we operate).

Insert a new node before the node with value key

  1. Allocate new; set new->info = x; if allocation fails stop.
  2. If start == NULL, print "list empty" and stop.
  3. If start->info == key: new->next = start; start = new; stop. (Insert before first node.)
  4. Set prev = start, cur = start->next.
  5. While cur != NULL and cur->info != key: prev = cur; cur = cur->next.
  6. If cur == NULL, print "key not found" and stop.
  7. new->next = cur; prev->next = new;
Before: [prev] -> [cur(key)]
After : [prev] -> [new] -> [cur(key)]

Delete the node before the node with value key

  1. If start == NULL or start->info == key, print "no node before key" and stop.
  2. If start->next != NULL and start->next->info == key: the node before key is the first node: t = start; start = start->next; free(t); stop.
  3. Set prev = start, cur = start->next.
  4. While cur != NULL and cur->next != NULL and cur->next->info != key: prev = cur; cur = cur->next.
  5. If cur == NULL or cur->next == NULL, print "key not found" and stop.
  6. Now cur is the node before key node, prev is the node before cur: prev->next = cur->next; free(cur);
Before: [prev] -> [cur] -> [key]
After : [prev] -> [key]          (cur freed)

Because a singly list has no prev pointer, we must keep trailing pointers while traversing, so both operations take O(n).

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Data Structure and Algorithm chapter 4 questions →