Doubly & Circular Linked Lists · Data Structures

Doubly linked list

Each node in a doubly linked list has two pointers: prev and next. You can walk in both directions, and you can delete a node when you only have a pointer to it.

A doubly linked list. Slashes show NULL: the first node's prev and the last node's next.

#include <stdio.h>
#include <stdlib.h>

typedef struct DNode {
    int data;
    struct DNode *prev, *next;
} DNode;

DNode *head = NULL, *tail = NULL;

void pushBack(int v) {                    // O(1) with a tail pointer
    DNode *n = malloc(sizeof(DNode));
    n->data = v; n->next = NULL; n->prev = tail;
    if (tail) tail->next = n; else head = n;
    tail = n;
}

void pushFront(int v) {
    DNode *n = malloc(sizeof(DNode));
    n->data = v; n->prev = NULL; n->next = head;
    if (head) head->prev = n; else tail = n;
    head = n;
}

void removeNode(DNode *n) {               // O(1): no need to search for the previous node
    if (n->prev) n->prev->next = n->next; else head = n->next;
    if (n->next) n->next->prev = n->prev; else tail = n->prev;
    free(n);
}

void printForward(void)  { for (DNode *p = head; p; p = p->next) printf("%d ", p->data); printf("\n"); }
void printBackward(void) { for (DNode *p = tail; p; p = p->prev) printf("%d ", p->data); printf("\n"); }

int main(void) {
    pushBack(20); pushBack(30); pushBack(40); pushFront(10);
    printf("forward:  "); printForward();
    printf("backward: "); printBackward();
    removeNode(head->next);               // remove 20 using just its pointer
    printf("after removing 20: "); printForward();
    removeNode(tail);
    printf("after removing tail: "); printForward();
    return 0;
}

Output

forward:  10 20 30 40 
backward: 40 30 20 10 
after removing 20: 10 30 40 
after removing tail: 10 30

Try it Yourself

When inserting in the middle of a doubly linked list, four pointers change: the new node's prev and next, the previous node's next and the following node's prev.

Circular linked list

In a circular list, the last node points back to the first instead of NULL. There is no natural end, so traversal stops when you return to the starting node. It is often accessed through a pointer to the last node, because last->next is the first node — giving O(1) insertion at both ends.

A circular singly linked list. The last node's next points back to the first.

#include <stdio.h>
#include <stdlib.h>

typedef struct Node { int data; struct Node *next; } Node;

Node *insertEnd(Node *last, int v) {          // returns the new last node
    Node *n = malloc(sizeof(Node));
    n->data = v;
    if (last == NULL) { n->next = n; return n; }   // one node points to itself
    n->next = last->next;                     // new node points to the first
    last->next = n;
    return n;
}

void print(Node *last) {
    if (!last) return;
    Node *p = last->next;                     // start at the first node
    do { printf("%d ", p->data); p = p->next; } while (p != last->next);
    printf("(back to %d)\n", last->next->data);
}

int main(void) {
    Node *last = NULL;
    for (int v = 10; v <= 40; v += 10) last = insertEnd(last, v);
    print(last);

    // Josephus-style round: remove every 2nd person until one remains
    Node *p = last;
    while (p->next != p) {
        p = p->next;                  // this person survives the round
        Node *out = p->next;          // the next one is removed
        p->next = out->next;
        printf("removed %d\n", out->data);
        free(out);
    }
    printf("survivor: %d\n", p->data);
    return 0;
}

Output

10 20 30 40 (back to 10)
removed 20
removed 40
removed 30
survivor: 10

Try it Yourself

Which list should you use?

	Singly	Doubly	Circular
Pointers per node	1	2	1 (or 2 if doubly circular)
Traverse backwards	no	yes	no
Delete a node given only its pointer	no (needs previous)	O(1)	no
Memory	least	most	least
Natural use	stacks, simple lists	browser history, LRU caches, text editors	round-robin, repeating playlists

Test yourself

4 questions · pick an answer to check it instantly

1
How many pointers change when inserting a node in the middle of a doubly linked list?
2
How do you know you have finished traversing a circular linked list?
3
Why is deleting a known node O(1) in a doubly linked list but not in a singly linked list?
4
Which application suits a circular linked list best?

#Doubly linked list

#Circular linked list

#Which list should you use?

Test yourself

Doubly linked list

Circular linked list

Which list should you use?