UNIT 05Prerequisite: Unit 04 — Pointers90 min read
Arrays are powerful but they have one big weakness — their size is fixed. Once you declare int arr[10], you get exactly 10 slots. You cannot grow or shrink it while the program runs. Linked lists solve this completely — they grow and shrink dynamically, one node at a time, using the pointers you mastered in Unit 04.
In this unit we build linked lists completely from scratch in C — singly, doubly, and circular. We implement every operation, understand every edge case, and solve the classic interview problems that come from this topic.
// Section 1
What is a Linked List?
A linked list is a collection of nodes where each node holds two things: a piece of data, and a pointer to the next node. The nodes do not need to be next to each other in memory — they can be scattered anywhere in RAM, connected only by their pointers.
🚂 Think of a train
Each train coach is a node. It carries passengers (data) and is coupled to the next coach (next pointer). The last coach has no coupling — it points to nothing (NULL). You always start from the engine (HEAD) and move forward coach by coach. You cannot jump directly to coach 5 — you must pass through 1, 2, 3, 4 first.
data field
Holds the actual value — 10, 20, 30, 40. Could be any type: int, float, string.
next field
Pointer to the next node. The last node's next is NULL — meaning "chain ends here."
💡 Note
Array vs Linked List — the core tradeoff: Arrays give O(1) access by index but O(n) insertion/deletion. Linked lists give O(1) insertion/deletion at the head but O(n) access — you must walk from the start every time. Neither is better overall. The right choice depends on what your program does most.
// Section 2
Building a Node in C — The struct
In C, we group data together using a struct. Think of a struct as a custom box that can hold multiple values of different types under one name. A linked list node needs exactly two things in its box: an integer (the data) and a pointer to the next node.
/* Define the structure of one node */
struct Node {
int data; /* the value this node holds */
struct Node *next; /* pointer to the next node in the chain */
};
/* typedef lets us write Node instead of struct Node everywhere */
typedef struct Node Node;
Now let us create actual nodes using malloc — which allocates memory dynamically at runtime. This is why linked lists can grow: each new node gets fresh memory from the system on demand.
#include <stdio.h>
#include <stdlib.h> /* required for malloc and free */
struct Node {
int data;
struct Node *next;
};
typedef struct Node Node;
/* helper function: create a new node with given data */
Node* createNode(int value) {
Node *newNode = (Node*)malloc(sizeof(Node)); /* ask OS for memory */
if (newNode == NULL) {
printf("Memory allocation failed!\n");
return NULL;
}
newNode->data = value; /* set the data */
newNode->next = NULL; /* next points to nothing yet */
return newNode;
}
int main() {
Node *n1 = createNode(10);
Node *n2 = createNode(20);
Node *n3 = createNode(30);
/* link them together manually */
n1->next = n2; /* 10 → 20 */
n2->next = n3; /* 20 → 30 */
n3->next = NULL; /* 30 → NULL */
/* n1 is our HEAD — the entry point to the whole list */
printf("First node: %d\n", n1->data); /* 10 */
printf("Second node: %d\n", n1->next->data); /* 20 */
printf("Third node: %d\n", n1->next->next->data); /* 30 */
return 0;
}
🎯 Pro Tip
The arrow operator -> is shorthand for dereferencing a pointer and accessing a field. n1->data means the same as (*n1).data — go to the node n1 points to, then read its data field. Always use -> with pointers to structs. It is cleaner and you will see it everywhere.
// Section 3
Traversal — Walking the Chain
To visit every node you start at HEAD and follow the next pointers one by one until you reach NULL. Use a temporary pointer — never move HEAD itself, or you will lose track of the start of the list.
void printList(Node *head) {
Node *current = head; /* temporary pointer — do NOT move head */
while (current != NULL) {
printf("%d", current->data);
if (current->next != NULL) {
printf(" → ");
}
current = current->next; /* move to the next node */
}
printf(" → NULL\n");
}
/* calling it: printList(head); */
/* Output: 10 → 20 → 30 → NULL */
Time Complexity:O(n)
Space Complexity:O(1)
// Section 4
Insertion — Three Cases
Inserting into a linked list has three cases depending on where you insert. Each one has different steps and different complexity. Understand all three.
Case 1 — Insert at the Head
The new node becomes the new HEAD. Point its next to the old head, then update HEAD. This is the fastest insertion — O(1).
// Insert 5 at head — before: 10→20→30 after: 5→10→20→30
Node* insertAtHead(Node *head, int value) {
Node *newNode = createNode(value);
newNode->next = head; /* new node points to old head */
head = newNode; /* head now points to new node */
return head; /* return updated head */
}
/* usage: head = insertAtHead(head, 5); */
Time:O(1)
Case 2 — Insert at the Tail
Walk to the last node (the one whose next is NULL), then attach the new node there. Must traverse the whole list — O(n).
Node* insertAtTail(Node *head, int value) {
Node *newNode = createNode(value);
/* edge case: empty list — new node becomes head */
if (head == NULL) {
return newNode;
}
Node *current = head;
while (current->next != NULL) { /* walk until last node */
current = current->next;
}
current->next = newNode; /* attach new node at the end */
return head;
}
/* usage: head = insertAtTail(head, 40); */
Time:O(n)
Case 3 — Insert at a Specific Position
Walk to the node just before the target position, then rewire the pointers. The key is stopping one node early — at position-1.
// Insert 15 at position 1 — between 10 and 20
Step 1 — new node's next → 20
Step 2 — 10's next → new node
Node* insertAtPosition(Node *head, int value, int pos) {
/* position 0 means insert at head */
if (pos == 0) {
return insertAtHead(head, value);
}
Node *newNode = createNode(value);
Node *current = head;
int i;
/* walk to the node just BEFORE our target position */
for (i = 0; i < pos - 1 && current != NULL; i++) {
current = current->next;
}
if (current == NULL) {
printf("Position out of range\n");
return head;
}
/* rewire: new node points forward, previous node points to new node */
newNode->next = current->next;
current->next = newNode;
return head;
}
/* usage: head = insertAtPosition(head, 15, 1); */
Time:O(n)
// Section 5
Deletion — Three Cases
Deleting a node means rewiring the previous node's pointer to skip the deleted node, then freeing the memory. Three cases again — head, tail, and middle.
Node* deleteNode(Node *head, int value) {
if (head == NULL) {
printf("List is empty\n");
return NULL;
}
/* Case 1: delete the HEAD node */
if (head->data == value) {
Node *temp = head;
head = head->next; /* move head forward */
free(temp); /* release the old head's memory */
return head;
}
/* Case 2 & 3: delete a middle or tail node */
Node *current = head;
/* walk until we find the node BEFORE the one to delete */
while (current->next != NULL && current->next->data != value) {
current = current->next;
}
if (current->next == NULL) {
printf("Value %d not found\n", value);
return head;
}
/* rewire: skip the target node */
Node *temp = current->next; /* save pointer to node being deleted */
current->next = temp->next; /* bypass the deleted node */
free(temp); /* release its memory */
return head;
}
/* usage: head = deleteNode(head, 20); */
// Delete 20 — before: 10→20→30 after: 10→30
10's next skips over 20 and points directly to 30. Memory for 20 is freed.
Time:O(n)(O(1) if deleting head)
// Section 6
Search — Finding a Value
There is no index-based access in a linked list. You must walk from HEAD and check each node one by one until you find the value or reach NULL.
int searchList(Node *head, int target) {
Node *current = head;
int position = 0;
while (current != NULL) {
if (current->data == target) {
return position; /* found — return position */
}
current = current->next;
position++;
}
return -1; /* not found */
}
/* usage:
int pos = searchList(head, 30);
if (pos != -1) printf("Found at position %d\n", pos);
else printf("Not found\n");
*/
Best Case:O(1)(target is HEAD)
Worst Case:O(n)(target at tail or absent)
// Section 7
Reverse a Linked List — The Classic Interview Question
Reversing a linked list is the most frequently asked linked list question in coding interviews. The idea: walk through the list and flip every arrow — each node's next should point to its previous node instead of the next. You need three pointers to do this without losing track of where you are.
// Before: 10→20→30→NULL | After: 30→20→10→NULL
Before reversal:
After reversal:
Node* reverseList(Node *head) {
Node *prev = NULL; /* will become the new next for each node */
Node *current = head; /* the node we are processing right now */
Node *next = NULL; /* saves the next node before we overwrite the pointer */
while (current != NULL) {
next = current->next; /* step 1: save next before we lose it */
current->next = prev; /* step 2: flip the arrow — point backwards */
prev = current; /* step 3: prev moves forward */
current = next; /* step 4: current moves forward */
}
/* when loop ends, current is NULL and prev is the new head */
return prev;
}
/* usage: head = reverseList(head); */
Tracing through the first iteration (current = node 10):
1
next = current->nextnext = node(20) — saved so we don't lose it
2
current->next = prevnode(10)->next = NULL — arrow flipped backward
3
prev = currentprev = node(10)
4
current = nextcurrent = node(20) — move forward
Time:O(n)Space:O(1)(in-place, no extra list)
// Section 8
Doubly Linked List — Two Directions
A singly linked list only goes forward — you can never go back. A doubly linked list gives each node two pointers: next (forward) and prev (backward). You can traverse in both directions. The tradeoff: each node uses more memory, and insert/delete need to update two pointers instead of one.
// NULL ←prev | 10 | next→ ←prev | 20 | next→ ←prev | 30 | next→ NULL
#include <stdio.h>
#include <stdlib.h>
struct DNode {
int data;
struct DNode *prev; /* points to previous node */
struct DNode *next; /* points to next node */
};
typedef struct DNode DNode;
DNode* createDNode(int value) {
DNode *node = (DNode*)malloc(sizeof(DNode));
node->data = value;
node->prev = NULL;
node->next = NULL;
return node;
}
DNode* insertAtHeadDLL(DNode *head, int value) {
DNode *newNode = createDNode(value);
if (head != NULL) {
newNode->next = head; /* new node's next → old head */
head->prev = newNode; /* old head's prev → new node */
}
return newNode; /* new node is the new head */
}
void printForward(DNode *head) {
DNode *current = head;
printf("Forward: ");
while (current != NULL) {
printf("%d ", current->data);
current = current->next;
}
printf("\n");
}
void printBackward(DNode *head) {
if (head == NULL) return;
/* walk to the last node first */
DNode *current = head;
while (current->next != NULL) {
current = current->next;
}
/* now walk backward using prev */
printf("Backward: ");
while (current != NULL) {
printf("%d ", current->data);
current = current->prev;
}
printf("\n");
}
int main() {
DNode *head = NULL;
head = insertAtHeadDLL(head, 30);
head = insertAtHeadDLL(head, 20);
head = insertAtHeadDLL(head, 10);
printForward(head); /* Forward: 10 20 30 */
printBackward(head); /* Backward: 30 20 10 */
return 0;
}
// Section 9
Circular Linked List — No End
In a circular linked list, the last node does not point to NULL — it points back to the HEAD. The list forms a loop with no end. This is useful for things like round-robin scheduling (rotating through tasks endlessly) and implementing circular queues.
// 10 → 20 → 30 → (back to 10) — no NULL
/* Traversal of circular linked list — must stop carefully */
void printCircular(Node *head) {
if (head == NULL) return;
Node *current = head;
do {
printf("%d ", current->data);
current = current->next;
} while (current != head); /* stop when we are back at head */
printf("(back to head)\n");
}
/* Creating a circular list manually */
int main() {
Node *n1 = createNode(10);
Node *n2 = createNode(20);
Node *n3 = createNode(30);
n1->next = n2;
n2->next = n3;
n3->next = n1; /* last node points back to first — circular! */
Node *head = n1;
printCircular(head); /* 10 20 30 (back to head) */
return 0;
}
⚠️ Important
Traversal must use a do-while loop or check for the head pointer as the stop condition — never check for NULL, because in a circular list there is no NULL. Using a regular while loop that checks NULL will run forever.
// Section 10
Detect a Loop — Floyd's Cycle Detection
Sometimes a linked list has a bug — a node's next pointer accidentally points back to an earlier node, creating an infinite loop. Your traversal code would run forever. How do you detect this?
The answer is Floyd's Cycle Detection Algorithm, also called the tortoise and hare algorithm. The idea is beautifully simple: use two pointers. One moves one step at a time (slow). The other moves two steps at a time (fast). If there is a loop, the fast pointer will eventually lap the slow one — they will meet at the same node. If there is no loop, the fast pointer will reach NULL.
// Think of a circular running track — the faster runner always laps the slower one
🐢
slow pointer
moves 1 step at a time
🐇
fast pointer
moves 2 steps at a time
🤝
they meet = loop exists
fast reaches NULL = no loop
int detectLoop(Node *head) {
Node *slow = head; /* tortoise — moves 1 step */
Node *fast = head; /* hare — moves 2 steps */
while (fast != NULL && fast->next != NULL) {
slow = slow->next; /* move 1 step */
fast = fast->next->next; /* move 2 steps */
if (slow == fast) {
return 1; /* they met — loop detected */
}
}
return 0; /* fast reached NULL — no loop */
}
int main() {
/* create a list with a loop: 1→2→3→4→2 (4 points back to 2) */
Node *head = createNode(1);
head->next = createNode(2);
head->next->next = createNode(3);
head->next->next->next = createNode(4);
head->next->next->next->next = head->next; /* create loop: 4→2 */
if (detectLoop(head)) {
printf("Loop detected!\n"); /* Loop detected! */
} else {
printf("No loop\n");
}
return 0;
}
Time:O(n)
Space:O(1)(only two extra pointers)
// Section 11
Array vs Linked List — Side by Side
| Operation | Array | Linked List | Winner |
|---|
| Access by index | O(1) | O(n) | Array |
| Insert at head | O(n) — shift all | O(1) | Linked List |
| Insert at tail | O(1) if space | O(n) — walk to end | Array |
| Insert at middle | O(n) — shift | O(n) — walk + rewire | Tie |
| Delete at head | O(n) — shift all | O(1) | Linked List |
| Search | O(n) | O(n) | Tie |
| Memory | Fixed — may waste | Dynamic — exact fit | Linked List |
| Cache performance | Excellent — contiguous | Poor — scattered RAM | Array |
🎯 Pro Tip
Rule of thumb for interviews: If you need fast access by index — use array. If you need frequent insertions and deletions at the front — use linked list. If you do not know which operations dominate, ask the interviewer what the most common operation will be.
// What's Next
You Are Ready for Unit 06
You now know how to build, traverse, insert into, delete from, reverse, and detect loops in a linked list. Every one of those operations used the pointer knowledge from Unit 04 directly.
In Unit 06 we build Stacks — a data structure built on top of arrays or linked lists that enforces one rule: Last In, First Out. Stacks power undo/redo, function calls, expression evaluation, and much more.
UP NEXT → UNIT 06
Stacks — Last In, First Out
Push, pop, peek — with arrays and linked lists. Balanced brackets and the call stack.
🎯 Key Takeaways
- ✓A linked list is a chain of nodes — each node holds data and a pointer to the next node
- ✓Nodes are created with malloc and can be anywhere in memory — they do not need to be contiguous
- ✓Always use a temporary pointer to traverse — never move HEAD or you lose the start of the list
- ✓Use the -> operator to access struct fields through a pointer: node->data, node->next
- ✓Insert at head is O(1). Insert at tail or middle requires walking the list — O(n)
- ✓Delete a node by rewiring the previous node's next to skip it, then free the deleted node
- ✓Reverse a linked list using three pointers: prev, current, next — flip each arrow in one pass
- ✓Doubly linked list: each node has prev and next — allows traversal in both directions
- ✓Circular linked list: last node points back to head — use do-while to traverse, never check NULL
- ✓Floyd's cycle detection: slow moves 1 step, fast moves 2 — if they meet, a loop exists