Intermediate

Linked Lists

A chain of nodes where each one points to the next. More flexible than arrays, a favourite in interviews, and the foundation of stacks, queues, and trees.

90 min Updated Sep 10, 2026 Suggest a fix

Quick answer

A linked list is a chain of nodes, each holding data and a pointer to the next node, ending in NULL. Nodes can live anywhere in memory, so inserting at the front is O(1), but reaching the k-th element means walking the chain, which is O(n).

Create nodes with malloc and free them when done.
Traverse with a temporary pointer; moving head loses the list.
node->next reads a field through a pointer.

Build a list by inserting at the front, then walk it

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

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

Node *push_front(Node *head, int value) {
    Node *n = malloc(sizeof *n);
    n->data = value;
    n->next = head;
    return n;
}

int main(void) {
    Node *head = NULL;
    for (int v = 1; v <= 3; v++) head = push_front(head, v);
    for (Node *cur = head; cur; cur = cur->next) printf("%d -> ", cur->data);
    printf("NULL\n");
    while (head) { Node *next = head->next; free(head); head = next; }
    return 0;
}

Output

3 -> 2 -> 1 -> NULL

Prerequisite: Lesson 5 — Pointers

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 Lesson 5.

In this lesson 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.

HEAD

→

TAIL

→

NULL

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

HEAD

→

NULL

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

HEAD

→

NULL

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.

HEAD

→

NULL

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:

HEAD

→

TAIL

→

NULL

After reversal:

HEAD

→

TAIL

→

NULL

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):

next = current->next

next = node(20) — saved so we don't lose it

current->next = prev

node(10)->next = NULL — arrow flipped backward

prev = current

prev = node(10)

current = next

current = 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

NULL

⇄

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

HEAD

→

→ back to HEAD

/* 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 Lesson 7

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 Lesson 5 directly.

In Lesson 7 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 → LESSON 7

Stacks — Last In, First Out

Push, pop, peek — with arrays and linked lists. Balanced brackets and the call stack.

Coming Soon →

🎯 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

Quick check

What is the cost of reading the 1,000th element of a linked list?

HELP US IMPROVE

How was this lesson?

Your note is shared with the Chaduvuko team for review. Please don’t include personal or sensitive information.

What to learn next

Spotted a mistake or something unclear? Suggest a fix on GitHub or email us. Select the text first and it is quoted for you.

Pointers

Stacks

Discussion

Have a better approach? Found something outdated? Share it — your knowledge helps everyone learning here.

Continue with GitHub