C Data Structures: Singly, Doubly & Circular Linked Lists Masterclass
Welcome to Phase 18 (Chapter 47): C Data Structures — Singly, Doubly & Circular Linked Lists Masterclass! A linked list is a chain of heap-allocated Node structs, each holding data and a pointer to the next node. Unlike arrays, linked lists support O(1) head insertion and deletion without shifting elements.
| Operation | Array | Linked List |
|---|---|---|
| Random Access (arr[i]) | O(1) — Direct index | O(n) — Must traverse from head |
| Head Insert | O(n) — Shift all elements | O(1) — Reroute head pointer |
| Middle Insert | O(n) — Shift right half | O(n) traversal + O(1) rewire |
| Delete by value | O(n) shift | O(n) find + O(1) rewire |
| Memory | Contiguous (cache-friendly) | Scattered (heap fragmentation, pointer overhead) |
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *next;
} Node;
/* Insert at head — O(1) */
Node *push_front(Node *head, int value) {
Node *n = malloc(sizeof(Node));
if (!n) { perror("malloc"); exit(1); }
n->data = value;
n->next = head;
return n;
}
/* Insert at tail — O(n) */
Node *push_back(Node *head, int value) {
Node *n = malloc(sizeof(Node));
if (!n) { perror("malloc"); exit(1); }
n->data = value;
n->next = NULL;
if (!head) return n;
Node *cur = head;
while (cur->next) cur = cur->next;
cur->next = n;
return head;
}
/* Delete first node with given value — O(n) */
Node *delete_value(Node *head, int value) {
if (!head) return NULL;
if (head->data == value) {
Node *next = head->next;
free(head);
return next;
}
Node *cur = head;
while (cur->next && cur->next->data != value)
cur = cur->next;
if (cur->next) {
Node *to_del = cur->next;
cur->next = to_del->next;
free(to_del);
}
return head;
}
/* Reverse in-place — O(n) */
Node *reverse(Node *head) {
Node *prev = NULL, *curr = head, *next = NULL;
while (curr) {
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
return prev;
}
void print_list(const Node *head) {
for (const Node *n = head; n; n = n->next)
printf("%d -> ", n->data);
printf("NULL\n");
}
void free_list(Node *head) {
while (head) { Node *tmp = head->next; free(head); head = tmp; }
}
int main(void) {
Node *list = NULL;
list = push_back(list, 10);
list = push_back(list, 20);
list = push_back(list, 30);
list = push_front(list, 5);
printf("Original: "); print_list(list);
list = delete_value(list, 20);
printf("Deleted 20: "); print_list(list);
list = reverse(list);
printf("Reversed: "); print_list(list);
free_list(list);
return 0;
}Q1: What is a sentinel/dummy head node?
A dummy head node at index -1 simplifies insert/delete code by eliminating special-case handling for empty lists and head deletions.
Q2: How do you detect a cycle in a linked list?
Use Floyd's Cycle Detection (Tortoise & Hare): two pointers, slow moves 1 step, fast moves 2 steps. If they meet, a cycle exists. Time O(n), Space O(1).
Q3: What is a doubly linked list advantage?
Each node has both next and prev pointers, enabling O(1) backward traversal and O(1) deletion when given a pointer directly to the node.
Q4: When is a circular linked list useful?
In Round-Robin scheduling (OS process queues), music playlists that loop, and buffer ring implementations where the tail always connects back to the head.
Q5: How do you find the middle of a linked list?
Use the two-pointer technique: slow moves 1 step, fast moves 2 steps. When fast reaches the end, slow is at the middle. O(n) time, O(1) space.