Singly & Doubly Linked Lists — Ananta Code Academy

◀◀ Part 1 | Singly Linked List ▶▶

🔗 What is a Linked List?

Dynamic chain of nodes — each node holds data and a pointer to the next

Concept

An array stores elements in a single contiguous block of memory — size fixed at declaration. A linked list stores elements as individual nodes scattered anywhere in memory, each connected to the next via a pointer. The list can grow or shrink at runtime — no wasted reserved space, no need to know the size upfront.

Every node has two things: the data it holds, and a pointer to the next node. The first node is called the head. The last node's pointer is NULL — that's how you know the list has ended.

singly linked list — 4 nodes in memory

Feature	Array	Singly Linked List
Size	Fixed at compile time	Dynamic — grows/shrinks at runtime
Memory	Contiguous block	Scattered nodes anywhere in heap
Access by index	O(1) — direct	O(n) — must traverse
Insert at head	O(n) — shift elements	O(1) — redirect pointer
Delete from middle	O(n) — shift elements	O(1) after finding node
Extra memory	None	One pointer per node

Think of it as a treasure hunt. Each clue (node) tells you the value and where the next clue is. The hunt ends when the next clue says NULL. You can only move forward — that's what makes it singly linked.

singly — node and insert

🛠️ Singly — Define Node, Insert at Head & Tail

struct Node with data + next pointer — insertHead O(1), insertTail O(n)

Insert

A singly linked list node is a struct with exactly two fields: data and a pointer next that points to the same struct type — making it self-referential. Every new node is allocated on the heap with malloc. Insert at Head is O(1): the new node's next points to the old head, then head is updated. Insert at Tail is O(n): walk to the last node first, then attach.

1
Define struct Node with int data and struct Node *next.
2
createNode(val): malloc one node, set data = val, set next = NULL, return pointer.
3
insertHead(&head, val): new node's next = *head, then *head = newNode. Pass Node** so caller's head updates.
4
insertTail(&head, val): if list empty, new node becomes head. Otherwise walk to cur->next == NULL, then cur->next = newNode.

singly_insert.c

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

typedef struct Node {
    int          data;
    struct Node *next;   /* self-referential pointer */
} Node;

Node* createNode(int val) {
    Node *n = (Node*)malloc(sizeof(Node));
    n->data = val;
    n->next = NULL;
    return n;
}

/* O(1) — redirect two pointers only */
void insertHead(Node **head, int val) {
    Node *n = createNode(val);
    n->next  = *head;   /* new node → old head */
    *head    = n;       /* head → new node     */
}

/* O(n) — walk to last node */
void insertTail(Node **head, int val) {
    Node *n = createNode(val);
    if (!*head) { *head = n; return; }
    Node *cur = *head;
    while (cur->next) cur = cur->next;  /* walk to tail */
    cur->next = n;
}

void print(Node *h) {
    printf("HEAD");
    while (h) { printf(" -> %d", h->data); h = h->next; }
    printf(" -> NULL\n");
}

int main() {
    Node *head = NULL;

    insertHead(&head, 20);
    insertHead(&head, 10);
    printf("After insertHead(20,10) : "); print(head);

    insertTail(&head, 30);
    insertTail(&head, 40);
    printf("After insertTail(30,40) : "); print(head);
    return 0;
}

output

After insertHead(20,10) : HEAD -> 10 -> 20 -> NULL
After insertTail(30,40) : HEAD -> 10 -> 20 -> 30 -> 40 -> NULL

Why Node **head? We pass a pointer to the head pointer. Without the double pointer, changes to head inside the function stay local — the caller never sees the new head. Node** gives the function permission to change where head points.

singly — traverse and delete

🔎 Singly — Traverse, Search and Delete by Value

Always use a temp pointer — never move head. prev+cur two-pointer deletion

Traverse & Delete

Traversal golden rule: always use a temporary pointer (cur = head) and move that — never move head itself. If head moves, you permanently lose everything before the new position.

Deletion needs two pointers walking together — prev trails one step behind cur. When the target is found: set prev->next = cur->next to bypass it, then free(cur). Three edge cases: empty list, deleting the head, deleting middle/tail.

1
Traverse: cur = head. Loop while(cur) — print, then cur = cur->next.
2
Search: same loop, but return index when cur->data == val. Return -1 if not found.
3
Delete — find target with prev + cur. If prev == NULL, target is head: *head = cur->next.
4
Otherwise: prev->next = cur->next. Then free(cur) — always re-link before freeing.

singly_traverse_delete.c

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

typedef struct Node { int data; struct Node *next; } Node;
Node* createNode(int v){Node*n=(Node*)malloc(sizeof(Node));n->data=v;n->next=NULL;return n;}

/* Traverse — print every node */
void traverse(Node *head) {
    Node *cur = head;              /* temp pointer — never move head */
    printf("HEAD");
    while (cur) {
        printf(" -> %d", cur->data);
        cur = cur->next;
    }
    printf(" -> NULL\n");
}

/* Search — returns 0-based index, -1 if not found */
int search(Node *head, int val) {
    int idx = 0;
    while (head) {
        if (head->data == val) return idx;
        head = head->next; idx++;
    }
    return -1;
}

/* Delete first occurrence of val */
void deleteNode(Node **head, int val) {
    Node *cur = *head, *prev = NULL;

    while (cur && cur->data != val) {   /* find target */
        prev = cur; cur = cur->next;
    }
    if (!cur) { printf("%d not found\n", val); return; }

    if (!prev) *head = cur->next;       /* deleting head  */
    else prev->next = cur->next;        /* bypass cur     */

    printf("Deleted %d\n", val);
    free(cur);                           /* AFTER re-link  */
}

int main() {
    Node *head = NULL;
    /* Build: 10 -> 20 -> 30 -> 40 -> 50 */
    Node *t = createNode(10); head = t;
    t->next = createNode(20);
    t->next->next = createNode(30);
    t->next->next->next = createNode(40);
    t->next->next->next->next = createNode(50);

    traverse(head);
    printf("Search 30: index %d\n", search(head, 30));
    printf("Search 99: index %d\n\n", search(head, 99));

    deleteNode(&head, 30);   /* middle */
    traverse(head);
    deleteNode(&head, 10);   /* head   */
    traverse(head);
    deleteNode(&head, 50);   /* tail   */
    traverse(head);
    return 0;
}

output

HEAD -> 10 -> 20 -> 30 -> 40 -> 50 -> NULL
Search 30: index 2
Search 99: index -1

Deleted 30
HEAD -> 10 -> 20 -> 40 -> 50 -> NULL
Deleted 10
HEAD -> 20 -> 40 -> 50 -> NULL
Deleted 50
HEAD -> 20 -> 40 -> NULL

Re-link before free. Always do prev->next = cur->next before free(cur). If you free first, cur->next becomes undefined garbage — you've lost the rest of the list.

singly — reverse

↻ Singly — Reverse In-Place

Three-pointer technique — flip every link with no extra memory

Reverse

Reversing a singly linked list is a classic interview question. The trick is three pointers: prev, cur, and next. At each step: (1) save cur->next, (2) flip cur->next to point backward at prev, (3) slide both prev and cur one step forward. When cur reaches NULL, prev is the new head. This is O(n) time and O(1) space — one pass, no extra array.

three-pointer reversal — step by step

        Before:  1 → 2 → 3 → 4 → NULL

        Step 1:  NULL ← 1    cur=2   (flip 1's link)

        Step 2:  NULL ← 1 ← 2    cur=3   (flip 2's link)

        Step 3:  NULL ← 1 ← 2 ← 3    cur=4   (flip 3's link)

        Step 4:  NULL ← 1 ← 2 ← 3 ← 4    cur=NULL  →  prev=new head

        After:   4 → 3 → 2 → 1 → NULL

singly_reverse.c

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

typedef struct Node { int data; struct Node *next; } Node;
Node* createNode(int v){Node*n=(Node*)malloc(sizeof(Node));n->data=v;n->next=NULL;return n;}
void print(Node*h){printf("HEAD");while(h){printf(" -> %d",h->data);h=h->next;}printf(" -> NULL\n");}

/* Reverse in-place — O(n) time, O(1) space */
Node* reverse(Node *head) {
    Node *prev = NULL;
    Node *cur  = head;
    Node *next = NULL;

    while (cur) {
        next       = cur->next;   /* 1. save next */
        cur->next  = prev;        /* 2. flip link */
        prev       = cur;         /* 3. advance prev */
        cur        = next;        /* 4. advance cur  */
    }
    return prev;   /* prev is the new head */
}

int main() {
    Node *head = createNode(1);
    Node *c = head;
    int v[] = {2,3,4,5};
    for(int i=0;i<4;i++){c->next=createNode(v[i]);c=c->next;}

    printf("Original : "); print(head);
    head = reverse(head);
    printf("Reversed : "); print(head);
    head = reverse(head);
    printf("Original : "); print(head);
    return 0;
}

output

Original : HEAD -> 1 -> 2 -> 3 -> 4 -> 5 -> NULL
Reversed : HEAD -> 5 -> 4 -> 3 -> 2 -> 1 -> NULL
Original : HEAD -> 1 -> 2 -> 3 -> 4 -> 5 -> NULL

The four-line loop body is the entire algorithm. Save next, flip cur->next backward, advance prev, advance cur. Memorise these four lines and you can write reversal in any interview without hesitation.

singly — complete program

🎓 Singly Linked List — Complete Mini App

Insert, traverse, search, delete, reverse, length, free — all together

Full Program

All singly linked list operations in one self-contained program — a complete reference you can study and run. It builds a list of student marks, performs every operation, and ends by freeing all memory cleanly.

singly_complete.c

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

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

Node* createNode(int v) {
    Node *n=(Node*)malloc(sizeof(Node)); n->data=v; n->next=NULL; return n;
}
void insertHead(Node **h, int v) { Node *n=createNode(v); n->next=*h; *h=n; }
void insertTail(Node **h, int v) {
    Node *n=createNode(v);
    if(!*h){*h=n;return;}
    Node *c=*h; while(c->next) c=c->next; c->next=n;
}
void deleteNode(Node **h, int v) {
    Node *c=*h,*p=NULL;
    while(c&&c->data!=v){p=c;c=c->next;}
    if(!c){printf("  %d not found\n",v);return;}
    if(!p)*h=c->next; else p->next=c->next;
    free(c); printf("  Deleted %d\n",v);
}
Node* reverse(Node *h){
    Node *p=NULL,*c=h,*nx=NULL;
    while(c){nx=c->next;c->next=p;p=c;c=nx;}
    return p;
}
int length(Node *h){int n=0;while(h){n++;h=h->next;}return n;}
int maxVal(Node *h){int m=h->data;while(h){if(h->data>m)m=h->data;h=h->next;}return m;}
void freeList(Node *h){Node *t;while(h){t=h->next;free(h);h=t;}}
void print(Node *h){printf("  HEAD");while(h){printf(" -> %d",h->data);h=h->next;}printf(" -> NULL\n");}

int main() {
    Node *head = NULL;

    printf("=== Build list (tail inserts) ===\n");
    int marks[] = {85, 92, 78, 96, 88};
    for(int i=0;i<5;i++) insertTail(&head, marks[i]);
    print(head);

    printf("\n=== insertHead(100) ===\n");
    insertHead(&head, 100);
    print(head);

    printf("\n=== Stats ===\n");
    printf("  Length : %d\n", length(head));
    printf("  Maximum: %d\n", maxVal(head));

    printf("\n=== Delete 78 and 100 ===\n");
    deleteNode(&head, 78);
    deleteNode(&head, 100);
    print(head);

    printf("\n=== Reverse ===\n");
    head = reverse(head);
    print(head);

    printf("\n=== Free all nodes ===\n");
    freeList(head);
    printf("  Done.\n");
    return 0;
}

output

=== Build list (tail inserts) ===
  HEAD -> 85 -> 92 -> 78 -> 96 -> 88 -> NULL

=== insertHead(100) ===
  HEAD -> 100 -> 85 -> 92 -> 78 -> 96 -> 88 -> NULL

=== Stats ===
  Length : 6
  Maximum: 100

=== Delete 78 and 100 ===
  Deleted 78
  Deleted 100
  HEAD -> 85 -> 92 -> 96 -> 88 -> NULL

=== Reverse ===
  HEAD -> 88 -> 96 -> 92 -> 85 -> NULL

=== Free all nodes ===
  Done.

◀◀ Part 2 | Doubly Linked List ▶▶

🔗🔗 Doubly — Node Structure and Insert

Each node has TWO pointers — next AND prev — traverse in both directions

Node & Insert

A doubly linked list node has three fields instead of two: data, next (points forward), and prev (points backward). This allows bidirectional traversal — you can move both forward and backward through the list. The head->prev is always NULL. The tail->next is always NULL. Every pointer update during insert or delete must handle both next and prev.

doubly linked list — 4 nodes, forward and backward pointers

doubly_insert.c

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

typedef struct Node {
    int          data;
    struct Node *next;  /* forward  pointer */
    struct Node *prev;  /* backward pointer */
} Node;

Node* createNode(int val) {
    Node *n = (Node*)malloc(sizeof(Node));
    n->data = val; n->next = NULL; n->prev = NULL;
    return n;
}

/* Insert at HEAD — update 4 pointers */
void insertHead(Node **head, int val) {
    Node *n = createNode(val);
    if (*head) (*head)->prev = n;  /* old head's prev -> new node */
    n->next = *head;               /* new node's next -> old head */
    *head   = n;                   /* head -> new node           */
    /* n->prev stays NULL — new node is the head */
}

/* Insert at TAIL */
void insertTail(Node **head, int val) {
    Node *n = createNode(val);
    if (!*head) { *head = n; return; }
    Node *cur = *head;
    while (cur->next) cur = cur->next;   /* walk to tail */
    cur->next = n;                        /* tail -> new  */
    n->prev   = cur;                      /* new's prev -> old tail */
}

void printForward(Node *h) {
    printf("  FWD: NULL <- ");
    while (h) { printf("%d",h->data); if(h->next)printf(" <-> "); h=h->next; }
    printf(" -> NULL\n");
}

int main() {
    Node *head = NULL;
    insertTail(&head, 10);
    insertTail(&head, 20);
    insertTail(&head, 30);
    printf("After insertTail(10,20,30):\n");
    printForward(head);

    insertHead(&head, 5);
    printf("\nAfter insertHead(5):\n");
    printForward(head);
    return 0;
}

output

After insertTail(10,20,30):
  FWD: NULL <- 10 <-> 20 <-> 30 -> NULL

After insertHead(5):
  FWD: NULL <- 5 <-> 10 <-> 20 <-> 30 -> NULL

Doubly linked insert touches more pointers than singly. Insert at head: set n->next = *head, set (*head)->prev = n, then *head = n. That's three pointer assignments vs two in singly. More work per operation — but you gain the ability to go backwards.

doubly — traverse both ways

⇄ Doubly — Traverse Forward and Backward

Walk forward with next — find tail — walk backward with prev

Traversal

The biggest advantage of a doubly linked list over singly is bidirectional traversal. Forward traversal is identical to singly — follow next from head until NULL. Backward traversal: first walk to the tail (where next == NULL), then follow prev pointers back to the head. If you maintain a separate tail pointer, backward traversal starts immediately — no need to find the tail first.

doubly_traverse.c

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

typedef struct Node { int data; struct Node *next, *prev; } Node;
Node* createNode(int v){Node*n=(Node*)malloc(sizeof(Node));n->data=v;n->next=n->prev=NULL;return n;}
void insertTail(Node**h,int v){
    Node*n=createNode(v);
    if(!*h){*h=n;return;}
    Node*c=*h;while(c->next)c=c->next;
    c->next=n;n->prev=c;
}

/* Forward — follow next from head */
void traverseForward(Node *head) {
    printf("  Forward  : HEAD");
    while (head) {
        printf(" -> %d", head->data);
        head = head->next;
    }
    printf(" -> NULL\n");
}

/* Backward — walk to tail, then follow prev */
void traverseBackward(Node *head) {
    if (!head) return;
    Node *tail = head;
    while (tail->next) tail = tail->next;  /* find the tail */

    printf("  Backward : TAIL");
    while (tail) {
        printf(" -> %d", tail->data);
        tail = tail->prev;                  /* move backward */
    }
    printf(" -> NULL\n");
}

/* Print prev pointers to verify integrity */
void verifyPrev(Node *head) {
    printf("  Prev ptrs: ");
    while (head) {
        if (head->prev)
            printf("%d.prev=%d  ", head->data, head->prev->data);
        else
            printf("%d.prev=NULL  ", head->data);
        head = head->next;
    }
    printf("\n");
}

int main() {
    Node *head = NULL;
    int vals[] = {10, 20, 30, 40, 50};
    for(int i=0;i<5;i++) insertTail(&head, vals[i]);

    traverseForward(head);
    traverseBackward(head);
    printf("\n");
    verifyPrev(head);
    return 0;
}

output

  Forward  : HEAD -> 10 -> 20 -> 30 -> 40 -> 50 -> NULL
  Backward : TAIL -> 50 -> 40 -> 30 -> 20 -> 10 -> NULL

  Prev ptrs: 10.prev=NULL  20.prev=10  30.prev=20  40.prev=30  50.prev=40

Maintaining a tail pointer alongside head makes backward traversal start in O(1). Without it, you must walk forward to find the tail first — O(n). Most real doubly linked list implementations (like Linux kernel's list_head) keep both head and tail.

doubly — delete node

🗑️ Doubly — Delete a Node

Update four pointers — no prev pointer needed unlike singly

Delete

Deletion in a doubly linked list is actually simpler than singly in one key way: you don't need a prev pointer variable because every node already knows its predecessor via node->prev. Once you find the target node, you can re-link in both directions immediately. Update target->prev->next and target->next->prev to bypass the target, then free it.

deleting node 20 from [10 <-> 20 <-> 30]

        Before: 10 <-> 20 <-> 30

        Step 1: 20.prev (=10).next = 20.next (=30)    [10 -> 30]

        Step 2: 20.next (=30).prev = 20.prev (=10)    [10 <- 30]

        Step 3: free(20)

        After:  10 <-> 30

doubly_delete.c

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

typedef struct Node { int data; struct Node *next, *prev; } Node;
Node* createNode(int v){Node*n=(Node*)malloc(sizeof(Node));n->data=v;n->next=n->prev=NULL;return n;}
void insertTail(Node**h,int v){Node*n=createNode(v);if(!*h){*h=n;return;}Node*c=*h;while(c->next)c=c->next;c->next=n;n->prev=c;}
void print(Node*h){printf("  ");while(h){printf("%d",h->data);if(h->next)printf(" <-> ");h=h->next;}printf("\n");}

/* Delete — no prev variable needed; node knows its own predecessor */
void deleteNode(Node **head, int val) {
    Node *cur = *head;
    while (cur && cur->data != val) cur = cur->next;  /* find target */
    if (!cur) { printf("  %d not found\n", val); return; }

    /* Re-link the predecessor */
    if (cur->prev)
        cur->prev->next = cur->next;    /* prev node skips cur  */
    else
        *head = cur->next;              /* cur was head         */

    /* Re-link the successor */
    if (cur->next)
        cur->next->prev = cur->prev;   /* next node's prev fixed */

    printf("  Deleted %d\n", val);
    free(cur);
}

int main() {
    Node *head = NULL;
    int v[] = {10,20,30,40,50};
    for(int i=0;i<5;i++) insertTail(&head, v[i]);

    printf("Original: "); print(head);

    deleteNode(&head, 30);   /* middle node */
    print(head);

    deleteNode(&head, 10);   /* head node   */
    print(head);

    deleteNode(&head, 50);   /* tail node   */
    print(head);

    deleteNode(&head, 99);   /* not found   */
    return 0;
}

output

Original:   10 <-> 20 <-> 30 <-> 40 <-> 50
  Deleted 30
  10 <-> 20 <-> 40 <-> 50
  Deleted 10
  20 <-> 40 <-> 50
  Deleted 50
  20 <-> 40
  99 not found

Doubly deletion requires no prev tracking variable because cur->prev is already there. The trade-off: every insert and delete must maintain both next and prev — double the pointer work, but much cleaner deletion logic.

doubly — complete program

🎓 Doubly Linked List — Complete Mini App

Insert head/tail, forward/backward traverse, delete, search, length

Full Program

All doubly linked list operations in one complete program. Demonstrates why doubly linked lists are preferred for scenarios that require traversal in both directions, or efficient deletion when you already have a pointer to the node.

doubly_complete.c

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

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

Node* newNode(int v){Node*n=(Node*)malloc(sizeof(Node));n->data=v;n->next=n->prev=NULL;return n;}

void insertHead(Node **h, int v) {
    Node *n=newNode(v);
    if(*h) (*h)->prev=n;
    n->next=*h; *h=n;
}
void insertTail(Node **h, int v) {
    Node *n=newNode(v);
    if(!*h){*h=n;return;}
    Node *c=*h; while(c->next)c=c->next;
    c->next=n; n->prev=c;
}
void deleteVal(Node **h, int v) {
    Node *c=*h;
    while(c&&c->data!=v) c=c->next;
    if(!c){printf("  %d not found\n",v);return;}
    if(c->prev) c->prev->next=c->next; else *h=c->next;
    if(c->next) c->next->prev=c->prev;
    free(c); printf("  Deleted %d\n",v);
}
int search(Node *h, int v) {
    int i=0; while(h){if(h->data==v)return i;h=h->next;i++;} return -1;
}
int length(Node *h){int n=0;while(h){n++;h=h->next;}return n;}
void fwd(Node*h){printf("  FWD  : ");while(h){printf("%d",h->data);if(h->next)printf("<->");h=h->next;}printf("\n");}
void bwd(Node*h){if(!h)return;Node*t=h;while(t->next)t=t->next;printf("  BWD  : ");while(t){printf("%d",t->data);if(t->prev)printf("<->");t=t->prev;}printf("\n");}
void freeAll(Node*h){Node*t;while(h){t=h->next;free(h);h=t;}}

int main() {
    Node *head = NULL;

    printf("=== Build list ===\n");
    int v[] = {20,30,40,50};
    for(int i=0;i<4;i++) insertTail(&head, v[i]);
    insertHead(&head, 10);
    fwd(head);
    bwd(head);

    printf("\n=== Stats ===\n");
    printf("  Length : %d\n", length(head));
    printf("  Search 30: index %d\n", search(head, 30));
    printf("  Search 99: index %d\n", search(head, 99));

    printf("\n=== Delete 30 (middle), 10 (head), 50 (tail) ===\n");
    deleteVal(&head, 30);
    deleteVal(&head, 10);
    deleteVal(&head, 50);
    fwd(head);
    bwd(head);

    freeAll(head);
    printf("\n=== Memory freed ===\n");
    return 0;
}

output

=== Build list ===
  FWD  : 10<->20<->30<->40<->50
  BWD  : 50<->40<->30<->20<->10

=== Stats ===
  Length : 5
  Search 30: index 2
  Search 99: index -1

=== Delete 30 (middle), 10 (head), 50 (tail) ===
  Deleted 30
  Deleted 10
  Deleted 50
  FWD  : 20<->40
  BWD  : 40<->20

=== Memory freed ===

singly vs doubly — full comparison

CMP

⚖ Singly vs Doubly — Complete Comparison

Memory, operations, use cases — when to pick which

Summary

Choosing between singly and doubly linked lists is a trade-off between memory and convenience. Singly uses less memory per node. Doubly uses more memory but gives you bidirectional traversal and simpler deletion code. The right choice depends on your use case.

Feature	Singly Linked List	Doubly Linked List
Node structure	data + next	data + next + prev
Memory per node	Smaller (1 pointer)	Larger (2 pointers)
Traversal direction	Forward only	Forward AND backward
Insert at head	O(1) — 2 pointer updates	O(1) — 3 pointer updates
Insert at tail	O(n) — walk to end	O(n) without tail ptr / O(1) with tail ptr
Delete known node	O(n) — need prev pointer (must search from head)	O(1) — cur->prev is right there
Delete by value	O(n) — two pointer walk	O(n) to find, then O(1) to unlink
Implementation	Simpler — fewer pointers to manage	More complex — must maintain prev on every op
Reverse traversal	Not possible without reversing	Built-in via prev pointer
Typical use cases	Stacks, simple queues, hash chaining, memory-tight systems	Browsers (back/forward), undo/redo, LRU cache, deques

Decision guide — which one to pick?

➤ Memory is tight? Singly — one fewer pointer per node.
➤ Only need forward traversal? Singly — simpler, less overhead.
➤ Need to traverse both ways? Doubly — singly can't do it natively.
➤ Implement a stack or queue? Singly — head insert/delete is all you need.
➤ Implement a deque (both ends)? Doubly — efficient push/pop from both ends.
➤ Deletion given a node pointer? Doubly — O(1) because you have prev. Singly requires O(n) search.
➤ Browser history / undo? Doubly — you need to go back and forward.
➤ LRU Cache? Doubly + HashMap — the standard solution for O(1) get and put.

Real-world doubly linked lists: The Linux kernel's struct list_head is a doubly linked list embedded inside other structs. Python's collections.deque is a doubly linked list of fixed-size blocks. C++'s std::list is a doubly linked list. Java's LinkedList is doubly linked. Singly linked lists appear in hash table chaining and stack implementations.

checklist

S1 — Concept: Linked list = chain of nodes. Each node has data + pointer. Head = first. Last node's next = NULL. Dynamic size.
S2 — Singly Insert: struct Node {data; *next}. insertHead O(1): redirect 2 pointers. insertTail O(n): walk to last, attach. Pass Node** to modify head.
S3 — Traverse & Delete: Always use temp pointer cur = head — never move head. Delete: prev+cur walk, re-link before free. Three cases: empty, head, middle/tail.
S4 — Reverse: Three pointers: prev, cur, next. Save next, flip cur->next, advance both. When cur==NULL, prev is new head. O(n) time, O(1) space.
S5 — Complete singly: insertHead, insertTail, deleteNode, reverse, length, maxVal, freeList — all work together.
D1 — Doubly Node: struct Node {data; *next; *prev}. insertHead: 3 pointer updates. insertTail: link forward AND backward (n->prev = cur).
D2 — Bidirectional: Forward = follow next. Backward = walk to tail first, then follow prev. Maintain separate tail pointer for O(1) backward start.
D3 — Doubly Delete: No prev tracking variable needed — use cur->prev directly. Update both cur->prev->next and cur->next->prev before freeing.
D4 — Complete doubly: All ops in one program. Both forward and backward traversal work after every deletion.
CMP — Singly vs Doubly: Singly = less memory, forward only. Doubly = more memory, bidirectional, O(1) delete-by-pointer. Use doubly for browser history, undo, deques, LRU cache.

Linked Lists in C —Singly & Doubly Explained

Linked Lists in C —
Singly & Doubly Explained