Skip to main content

Insert before Kth node in doubly linked list

Short answer

Traverse to the Kth node (p). Allocate new node with info x; set new->next = p and new->prev = p->prev. If p->prev != NULL, set p->prev->next = new; else set start = new. Finally p->prev = new.

Write an algorithm to insert an element before Kth node in doubly linked list.

Using the node (prev, info, next), with start pointing to the first node and positions numbered from 1.

Algorithm INSERT_BEFORE_K(start, k, x)

  1. Allocate a new node new; if NULL print "overflow" and stop. Set new->info = x.
  2. Set p = start; repeat k-1 times: p = p->next. If p is NULL (empty list) or becomes NULL, print "invalid position" and stop. Now p is the K-th node.
  3. Set new->next = p; new->prev = p->prev.
  4. If p->prev != NULL then p->prev->next = new; else start = new (K was 1).
  5. Set p->prev = new.
Before: [a] <-> [p(K)]
After : [a] <-> [new] <-> [p(K)]

The order of the pointer assignments matters: copy p->prev into the new node before overwriting p->prev.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Data Structure and Algorithm chapter 4 questions →