Doubly linked list

Prerequisites

• Singly linked list.
• Pointers and NULL.
• Drawing boxes and arrows for pointer changes.

The analogy

How it works

Start with a sequence of operations by hand

The list is 4 ⇄ 6 ⇄ 9; each node has prev and next. Predict which pointers change, then open "Check".

Finish the picture: the ends of the list

Keep both head and tail. Work on 4 ⇄ 5 ⇄ 9.

• Delete the head, 4. Predict what changes.
  Check

  head becomes 5, and 5.prev becomes NULL. No walk needed.

• Delete the tail, 9. Predict the cost, and compare with a singly linked list.
  Check

  $O(1)$: tail becomes 9.prev, which is 5. A singly linked list needs $O(n)$ here, because it must find the node before the tail.

The rule in plain words

Each node stores a value, prev and next. The first node's prev and the last node's next are NULL.

To insert or delete next to a node you hold, rewire the links on both sides. Check for NULL neighbours at the ends.

The code

Read this code after you have done the operations by hand. It will make more sense.

typedef struct Node { int val; struct Node *prev, *next; } Node;

void insert_after(Node *p, int v) {           /* p must not be NULL */
    Node *n = malloc(sizeof(Node));
    n->val = v;
    n->prev = p;
    n->next = p->next;
    if (p->next) p->next->prev = n;           /* right neighbour points back */
    p->next = n;
}

Node *remove_node(Node *head, Node *x) {     /* O(1): x knows its neighbours */
    if (x->prev) x->prev->next = x->next;
    else head = x->next;                      /* x was the head */
    if (x->next) x->next->prev = x->prev;
    free(x);
    return head;
}

flowchart LR
  A["4"] <--> B["5"]
  B <--> C["6"]
  C <--> D["9"]
          

How fast is it?

Memory is the price of the backward link. With values of $v$ bytes and pointers of $p$ bytes, $n$ nodes take:

On a 64-bit machine with 4-byte ints, that's about 20 bytes per node instead of 12 (before padding).

Common mistakes

• Updating only the next pointers and forgetting the matching prev ones.
• Not handling the ends: x->prev or x->next may be NULL.
• Overwriting p->next before using it to set the new node's next.

Try it yourself

Did you know?

Key points to remember

If you remember one thing from each line, remember the because.

• Deleting a known node is $O(1)$ because it stores pointers to both neighbours.
• pop_back is $O(1)$ because the tail's prev gives the new tail without walking.
• Every insert writes four pointers because each link exists in both directions.
• Search is still $O(n)$ because extra links don't give an address formula.
• It uses more memory because each node carries a second pointer.

Self-check questions

Answer these in order, out loud. They follow the page, so your answers become the script of your video.

1. How is a doubly linked list like a train?
   Sample answer

   Each carriage is coupled to the one in front and the one behind, so you can walk either way and remove a carriage by joining its two neighbours.

2. Walk through inserting 5 after 4 in 4 ⇄ 6 ⇄ 9.
   Sample answer

   The new node gets prev = 4 and next = 6; then 6.prev = 5 and 4.next = 5, giving 4 ⇄ 5 ⇄ 6 ⇄ 9.

3. Why does insert_after set n->next = p->next before changing p->next?

   A good answer says what would be lost.

   Sample answer

   Once p->next is overwritten, the old right neighbour can no longer be reached, so it must be copied into the new node first.

4. So what is a doubly linked list, in one sentence?
   Sample answer

   A chain of nodes where each node points to both its next and its previous node.

5. Why is deleting a known node $O(1)$ here but $O(n)$ in a singly linked list?

   A good answer names the missing information.

   Sample answer

   Deletion must change the predecessor's next. A doubly linked node stores its predecessor; a singly linked node doesn't, so you'd have to walk from the head to find it.

6. What do the main operations cost?
   Sample answer

   Push and pop at both ends, insert next to a known node and delete a known node are all $O(1)$; search and access by position are $O(n)$.

7. When is the extra memory not worth it?
   Sample answer

   When you only ever add and remove at the front or only walk forward, as in a simple stack; a singly linked list does that with less memory.

8. If you had to teach this to a friend in 2 minutes, what would you leave out, and why?
   Sample answer

   I'd leave out the memory formula and the order-of-writes detail. I'd keep the train analogy, the insert and delete pictures, and "$O(1)$ delete of a known node, costs an extra pointer".

External resources

• VisuAlgo: Linked list: choose "Doubly Linked List" and animate inserts and removals.
• GeeksforGeeks: Doubly linked list: operations with code and diagrams.
• Wikipedia: Doubly linked list: variants, sentinels and circular versions.

Videos

• YouTube search: doubly linked list explained: pick a walkthrough of insert and delete.