Learn Linked Lists | Algo Infinity Verse

01

Introduction to Linked Lists

A Linked List is a linear data structure where elements are not stored in contiguous memory. Instead, each element (called a node) holds its data and a pointer to the next node. This chain of pointers is what gives linked lists their power and flexibility.

Why Learn Linked Lists?

Dynamic size — grows and shrinks at runtime without reallocation
Efficient insert/delete — O(1) at the head, no shifting required
Foundation for stacks & queues — used in real OS schedulers
Interview staple — reversal, cycle detection, merge problems are everywhere

10

next →

→

20

next →

→

30

next →

→

NULL

Head → 10 → 20 → 30 → NULL

💡

Unlike arrays, linked list elements are not contiguous in memory. Each node can live anywhere on the heap — the pointer is what connects them. This makes random access O(n) but insertion/deletion at a known node O(1).

02

Node Structure

Every linked list is built from nodes. A node is a simple struct containing the data field and a next pointer that references the following node. The last node's next is always NULL, marking the end of the list.

C — Node Definition

// A single node in the linked list
struct Node {
    int data;           // payload
    struct Node* next;  // pointer to the next node
};

// Helper: create a new node on the heap
struct Node* createNode(int value) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->data = value;
    node->next = NULL;
    return node;
}

Memory Layout

Node at 0x100          Node at 0x200          Node at 0x300
┌────────┬────────┐   ┌────────┬────────┐   ┌────────┬────────┐
│ data:10│ next:  │──▶│ data:20│ next:  │──▶│ data:30│ next:  │──▶ NULL
│        │ 0x200  │   │        │ 0x300  │   │        │ NULL   │
└────────┴────────┘   └────────┴────────┘   └────────┴────────┘

⚡

Always initialize next = NULL when creating a node. A dangling pointer (uninitialized next) is one of the most common causes of segmentation faults in linked list code.

03

Traversal

Traversal visits every node exactly once by following the chain of next pointers from head until we reach NULL. It is the foundation of printing, searching, and computing aggregates.

C

void printList(struct Node* head) {
    struct Node* current = head;   // start at head

    while (current != NULL) {
        printf("%d", current->data);
        if (current->next != NULL)
            printf(" → ");
        current = current->next;   // move to next node
    }
    printf(" → NULL\n");
}

Output

10 → 20 → 30 → NULL

Practice: Traversal

Write a traversal that prints the sum and count of all nodes in the list.

C

void sumAndCount(struct Node* head) {
    int sum = 0, count = 0;
    struct Node* curr = head;

    while (curr != NULL) {
        sum   += curr->data;
        count++;
        curr = curr->next;
    }
    printf("Sum = %d, Count = %d\n", sum, count);
}
// For list 10→20→30: Sum = 60, Count = 3

04

Insertion

Inserting a node into a linked list is O(1) when you already have a pointer to the insertion point — no shifting required. There are three common cases: at the head, at the tail, and at a specific position.

Insert at Head — O(1)

Point the new node's next to the current head, then update head to the new node.

C — Insert at Head

struct Node* insertAtHead(struct Node* head, int value) {
    struct Node* newNode = createNode(value);
    newNode->next = head;  // new node points to old head
    return newNode;        // new node becomes the head
}

// Usage
head = insertAtHead(head, 5);
// Before: 10 → 20 → 30 → NULL
// After :  5 → 10 → 20 → 30 → NULL

Insert at Tail — O(n)

Traverse to the last node (where next == NULL), then attach the new node.

C — Insert at Tail

struct Node* insertAtTail(struct Node* head, int value) {
    struct Node* newNode = createNode(value);

    if (head == NULL) return newNode;  // empty list

    struct Node* curr = head;
    while (curr->next != NULL)
        curr = curr->next;            // reach last node

    curr->next = newNode;             // attach
    return head;
}

// Before: 10 → 20 → 30 → NULL
// After : 10 → 20 → 30 → 40 → NULL

⚠️

Always handle the empty list case (head == NULL) before traversing. Calling curr->next on a NULL pointer is immediate undefined behaviour.

Practice: Insertion

Insert the value 25 after the node that contains 20 in the list: 10 → 20 → 30 → NULL

C

void insertAfter(struct Node* prevNode, int value) {
    if (prevNode == NULL) return;

    struct Node* newNode  = createNode(value);
    newNode->next         = prevNode->next;  // new → 30
    prevNode->next        = newNode;         // 20  → new
}

// Find the node with data == 20, then:
insertAfter(nodeWith20, 25);
// Result: 10 → 20 → 25 → 30 → NULL

05

Deletion

Deletion rewires the next pointer of the predecessor node to skip the target, then frees the target's memory. Handling head deletion separately is essential.

C — Delete by Value

struct Node* deleteNode(struct Node* head, int key) {
    // Case 1: delete the head node
    if (head != NULL && head->data == key) {
        struct Node* temp = head;
        head = head->next;
        free(temp);
        return head;
    }

    // Case 2: find predecessor of the target node
    struct Node* curr = head;
    while (curr != NULL && curr->next != NULL) {
        if (curr->next->data == key) {
            struct Node* temp  = curr->next;
            curr->next         = temp->next;  // bypass target
            free(temp);
            return head;
        }
        curr = curr->next;
    }
    return head;  // key not found
}

// Before: 10 → 20 → 30 → NULL
// Delete 20
// After : 10 → 30 → NULL

⚡

Always free() the deleted node to avoid memory leaks. In C++, use delete. In Java/Python the garbage collector handles it, but you still need to unlink the node first.

Practice: Deletion

Delete the tail node from 5 → 10 → 15 → 20 → NULL and print the resulting list.

C

struct Node* deleteTail(struct Node* head) {
    if (head == NULL) return NULL;
    if (head->next == NULL) { free(head); return NULL; }

    struct Node* curr = head;
    while (curr->next->next != NULL)
        curr = curr->next;        // stop at second-to-last

    free(curr->next);
    curr->next = NULL;
    return head;
}
// Result: 5 → 10 → 15 → NULL

06

Searching

Unlike arrays, linked lists have no random access. Searching always requires traversal from the head — giving it an O(n) worst-case time complexity regardless of the key's position.

C — Search by Value

// Returns the node if found, NULL otherwise
struct Node* search(struct Node* head, int key) {
    struct Node* curr = head;
    int position = 0;

    while (curr != NULL) {
        if (curr->data == key) {
            printf("Found %d at position %d\n", key, position);
            return curr;
        }
        curr = curr->next;
        position++;
    }
    printf("%d not found in list\n", key);
    return NULL;
}

Example

List    : 10 → 20 → 30 → 40 → NULL
Search  : 30
Output  : Found 30 at position 2

🔍

Search is O(n) time, O(1) space. There is no Binary Search on a singly linked list because you cannot jump to the middle in O(1). Use a skip list or convert to an array first if you need faster lookups.

07

Doubly Linked Lists

A Doubly Linked List extends each node with a prev pointer in addition to next. This allows traversal in both directions and O(1) deletion when given any node (no predecessor search needed).

NULL

⇄

10

prev / next

⇄

20

prev / next

⇄

30

prev / next

⇄

NULL

C — Doubly Node

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

struct DNode* createDNode(int value) {
    struct DNode* node = (struct DNode*)malloc(sizeof(struct DNode));
    node->data = value;
    node->prev = NULL;
    node->next = NULL;
    return node;
}

// Insert at head of doubly linked list
struct DNode* insertDHead(struct DNode* head, int value) {
    struct DNode* newNode = createDNode(value);
    newNode->next = head;
    if (head != NULL) head->prev = newNode;
    return newNode;
}

🧩

Doubly linked lists use O(2n) pointer memory vs O(n) for singly linked. The trade-off: you gain O(1) backwards traversal and O(1) deletion at any known node — critical for LRU Cache implementations.

08

Circular Linked Lists

In a Circular Linked List, the last node's next pointer points back to the head instead of NULL. This is useful for round-robin schedulers, media playlists, and buffer implementations.

C — Circular Traversal

// Create circular list: 10 → 20 → 30 → (back to 10)
void makeCircular(struct Node* head) {
    if (head == NULL) return;
    struct Node* curr = head;
    while (curr->next != NULL)
        curr = curr->next;
    curr->next = head;  // tail points to head
}

// Traverse a circular list (stop after one full loop)
void printCircular(struct Node* head) {
    if (head == NULL) return;
    struct Node* curr = head;
    do {
        printf("%d → ", curr->data);
        curr = curr->next;
    } while (curr != head);    // stop when we're back at head
    printf("(head)\n");
}
// Output: 10 → 20 → 30 → (head)

⚠️

A regular while (curr != NULL) loop will run forever on a circular list. Always use a do-while that checks curr != head, or track a visited flag to detect the cycle.

09

Linked Lists vs Arrays

Choosing between a linked list and an array depends on which operations dominate your use case. Neither is universally better.

Operation	Array	Linked List
Access by index	O(1) ✓	O(n) ✗
Search	O(n)	O(n)
Insert at head	O(n) ✗	O(1) ✓
Insert at tail	O(1) ✓	O(n)*
Delete at head	O(n) ✗	O(1) ✓
Delete at tail	O(1) ✓	O(n) ✗
Memory overhead	Low ✓	High (ptrs) ✗
Cache performance	Excellent ✓	Poor ✗

* O(1) with a tail pointer maintained separately.

💡

Use an array when you need fast random access or cache-friendly iteration. Use a linked list when you need frequent insertions and deletions at arbitrary positions without shifting.

10

Linked List Interview Tips

Linked list problems are a favourite in FAANG interviews. They test pointer manipulation, edge-case awareness, and in-place algorithmic thinking.

Must-Know Techniques

Two Pointers (Fast & Slow) — detect cycles, find midpoint
Reverse a Linked List — in-place iterative and recursive
Merge Two Sorted Lists — dummy head pattern
Find Nth from End — two pointers with N gap
Detect Cycle (Floyd's) — hare & tortoise algorithm

Always ask: singly or doubly linked? Head pointer only, or tail too?
Draw the list on paper before writing code — pointer bugs are visual.
Handle edge cases explicitly: empty list, single node, two nodes.
Use a dummy head node to avoid special-casing head deletion.
Don't lose the reference to a node before re-pointing its predecessor.

Classic Interview Problem

Reverse a Singly Linked List in-place (iterative).

Input : 1 → 2 → 3 → 4 → 5 → NULL
Output: 5 → 4 → 3 → 2 → 1 → NULL

C

struct Node* reverseList(struct Node* head) {
    struct Node* prev    = NULL;
    struct Node* current = head;
    struct Node* next    = NULL;

    while (current != NULL) {
        next          = current->next;  // save next
        current->next = prev;           // reverse link
        prev          = current;        // advance prev
        current       = next;           // advance current
    }
    return prev;  // prev is now the new head
}

// Step-by-step trace:
// NULL ← 1    2 → 3 → 4 → 5
// NULL ← 1 ← 2    3 → 4 → 5
// NULL ← 1 ← 2 ← 3    4 → 5
// NULL ← 1 ← 2 ← 3 ← 4    5
// NULL ← 1 ← 2 ← 3 ← 4 ← 5  ← new head

Algo Infinity Verse

Master Data Structures With Linked Lists Chains of Connected Nodes