Chapter 5: Linked Lists

Introduction

A linked list is a linear data structure where elements are stored in nodes, and each node points to the next node in the sequence. Unlike arrays with contiguous memory, linked lists use scattered memory locations connected by pointers. This fundamental difference makes linked lists excel at dynamic insertions and deletions while sacrificing random access.

Why This Matters

Linked lists solve problems that arrays struggle with:

• Dynamic size without reallocation
• Efficient insertion/deletion at any position (O(1) if you have the node)
• No wasted memory from pre-allocation
• Foundation for other structures (stacks, queues, graphs)

Real-world applications:

• Music playlists (next/previous song)
• Browser history (back/forward)
• Undo functionality in applications
• Memory management in operating systems
• Polynomial arithmetic
• Image viewers (next/previous image)

How to Study This Chapter

1. Draw everything - Visualize node connections on paper
2. Trace pointer changes - Follow how pointers update during operations
3. Implement from scratch - Build without looking at solutions
4. Handle edge cases - Empty list, single node, operations at boundaries
5. Compare with arrays - Understand when to use each

What is a Linked List?

A linked list consists of nodes where each node contains:

• Data: The value stored
• Next: Pointer to the next node (NULL for last node)

Memory Layout Comparison

Array:

Memory: [10][20][30][40][50]
Address: 1000-1004-1008-1012-1016 (contiguous)

Linked List:

Node 1        Node 2        Node 3        Node 4        Node 5
[10|1500] -> [20|2000] -> [30|1200] -> [40|3000] -> [50|NULL]
Addr:1000    Addr:1500    Addr:2000    Addr:1200    Addr:3000
(scattered in memory, connected by pointers)

Types of Linked Lists

1. Singly Linked List - One pointer (next)
2. Doubly Linked List - Two pointers (next, prev)
3. Circular Linked List - Last node points to first

Singly Linked List

Node Structure

C:

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

C++:

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

Java:

class Node {
    int data;
    Node next;

    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

Creating a Linked List

C Implementation:

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

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

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

void printList(struct Node* head) {
    struct Node* current = head;
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

int main() {
    struct Node* head = createNode(10);
    head->next = createNode(20);
    head->next->next = createNode(30);

    printList(head);  // Output: 10 -> 20 -> 30 -> NULL

    return 0;
}

C++ Implementation:

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* next;

    Node(int data) : data(data), next(nullptr) {}
};

class LinkedList {
private:
    Node* head;

public:
    LinkedList() : head(nullptr) {}

    void printList() {
        Node* current = head;
        while (current != nullptr) {
            cout << current->data << " -> ";
            current = current->next;
        }
        cout << "NULL" << endl;
    }

    void insertAtEnd(int data) {
        Node* newNode = new Node(data);

        if (head == nullptr) {
            head = newNode;
            return;
        }

        Node* current = head;
        while (current->next != nullptr) {
            current = current->next;
        }
        current->next = newNode;
    }
};

int main() {
    LinkedList list;
    list.insertAtEnd(10);
    list.insertAtEnd(20);
    list.insertAtEnd(30);

    list.printList();  // Output: 10 -> 20 -> 30 -> NULL

    return 0;
}

Java Implementation:

class Node {
    int data;
    Node next;

    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

class LinkedList {
    private Node head;

    public void insertAtEnd(int data) {
        Node newNode = new Node(data);

        if (head == null) {
            head = newNode;
            return;
        }

        Node current = head;
        while (current.next != null) {
            current = current.next;
        }
        current.next = newNode;
    }

    public void printList() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " -> ");
            current = current.next;
        }
        System.out.println("NULL");
    }

    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        list.insertAtEnd(10);
        list.insertAtEnd(20);
        list.insertAtEnd(30);

        list.printList();  // Output: 10 -> 20 -> 30 -> NULL
    }
}

Linked List Operations

1. Insertion at Beginning - O(1)

C:

struct Node* insertAtBeginning(struct Node* head, int data) {
    struct Node* newNode = createNode(data);
    newNode->next = head;
    return newNode;
}

Visualization:

Before: HEAD -> [10] -> [20] -> [30] -> NULL
After:  HEAD -> [5] -> [10] -> [20] -> [30] -> NULL

2. Insertion at End - O(n)

C:

struct Node* insertAtEnd(struct Node* head, int data) {
    struct Node* newNode = createNode(data);

    if (head == NULL) {
        return newNode;
    }

    struct Node* current = head;
    while (current->next != NULL) {
        current = current->next;
    }
    current->next = newNode;

    return head;
}

3. Insertion After a Node - O(1) if node is given

C:

void insertAfter(struct Node* prevNode, int data) {
    if (prevNode == NULL) {
        printf("Previous node cannot be NULL\n");
        return;
    }

    struct Node* newNode = createNode(data);
    newNode->next = prevNode->next;
    prevNode->next = newNode;
}

4. Deletion at Beginning - O(1)

C:

struct Node* deleteAtBeginning(struct Node* head) {
    if (head == NULL) {
        return NULL;
    }

    struct Node* temp = head;
    head = head->next;
    free(temp);

    return head;
}

5. Deletion at End - O(n)

C:

struct Node* deleteAtEnd(struct Node* head) {
    if (head == NULL) {
        return NULL;
    }

    if (head->next == NULL) {
        free(head);
        return NULL;
    }

    struct Node* current = head;
    while (current->next->next != NULL) {
        current = current->next;
    }

    free(current->next);
    current->next = NULL;

    return head;
}

6. Deletion by Value - O(n)

C:

struct Node* deleteByValue(struct Node* head, int key) {
    if (head == NULL) {
        return NULL;
    }

    // If head node holds the key
    if (head->data == key) {
        struct Node* temp = head;
        head = head->next;
        free(temp);
        return head;
    }

    // Search for the key
    struct Node* current = head;
    while (current->next != NULL && current->next->data != key) {
        current = current->next;
    }

    if (current->next == NULL) {
        printf("Key not found\n");
        return head;
    }

    struct Node* temp = current->next;
    current->next = current->next->next;
    free(temp);

    return head;
}

7. Search - O(n)

C:

struct Node* search(struct Node* head, int key) {
    struct Node* current = head;

    while (current != NULL) {
        if (current->data == key) {
            return current;
        }
        current = current->next;
    }

    return NULL;
}

8. Reverse Linked List - O(n)

Iterative Approach:

C:

struct Node* reverse(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;        // Move prev forward
        current = next;        // Move current forward
    }

    return prev;
}

Visualization:

Original: [10] -> [20] -> [30] -> NULL

Step 1: NULL <- [10]    [20] -> [30] -> NULL
Step 2: NULL <- [10] <- [20]    [30] -> NULL
Step 3: NULL <- [10] <- [20] <- [30]

Recursive Approach:

C++:

Node* reverseRecursive(Node* head) {
    if (head == nullptr || head->next == nullptr) {
        return head;
    }

    Node* newHead = reverseRecursive(head->next);
    head->next->next = head;
    head->next = nullptr;

    return newHead;
}

9. Find Middle Element - O(n)

Two Pointer Technique:

C:

struct Node* findMiddle(struct Node* head) {
    if (head == NULL) {
        return NULL;
    }

    struct Node* slow = head;
    struct Node* fast = head;

    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }

    return slow;
}

10. Detect Cycle - O(n)

Floyd's Cycle Detection (Tortoise and Hare):

C:

int hasCycle(struct Node* head) {
    struct Node* slow = head;
    struct Node* fast = head;

    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;

        if (slow == fast) {
            return 1;  // Cycle detected
        }
    }

    return 0;  // No cycle
}

Doubly Linked List

Node Structure

C:

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

Implementation

C:

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

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

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

struct DNode* insertAtBeginning(struct DNode* head, int data) {
    struct DNode* newNode = createDNode(data);

    if (head != NULL) {
        head->prev = newNode;
    }

    newNode->next = head;
    return newNode;
}

void printForward(struct DNode* head) {
    struct DNode* current = head;
    while (current != NULL) {
        printf("%d <-> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

void printBackward(struct DNode* head) {
    if (head == NULL) return;

    // Go to end
    struct DNode* current = head;
    while (current->next != NULL) {
        current = current->next;
    }

    // Print backward
    while (current != NULL) {
        printf("%d <-> ", current->data);
        current = current->prev;
    }
    printf("NULL\n");
}

int main() {
    struct DNode* head = NULL;

    head = insertAtBeginning(head, 30);
    head = insertAtBeginning(head, 20);
    head = insertAtBeginning(head, 10);

    printf("Forward: ");
    printForward(head);

    printf("Backward: ");
    printBackward(head);

    return 0;
}

Output:

Forward: 10 <-> 20 <-> 30 <-> NULL
Backward: 30 <-> 20 <-> 10 <-> NULL

Circular Linked List

Last node points to first node:

C:

struct Node* insertInCircular(struct Node* head, int data) {
    struct Node* newNode = createNode(data);

    if (head == NULL) {
        newNode->next = newNode;  // Points to itself
        return newNode;
    }

    struct Node* current = head;
    while (current->next != head) {
        current = current->next;
    }

    current->next = newNode;
    newNode->next = head;

    return head;
}

void printCircular(struct Node* head) {
    if (head == NULL) return;

    struct Node* current = head;
    do {
        printf("%d -> ", current->data);
        current = current->next;
    } while (current != head);

    printf("(back to %d)\n", head->data);
}

Common Linked List Problems

1. Remove Nth Node from End

C:

struct Node* removeNthFromEnd(struct Node* head, int n) {
    struct Node* dummy = createNode(0);
    dummy->next = head;

    struct Node* first = dummy;
    struct Node* second = dummy;

    // Move first n+1 steps ahead
    for (int i = 0; i <= n; i++) {
        if (first == NULL) return head;
        first = first->next;
    }

    // Move both until first reaches end
    while (first != NULL) {
        first = first->next;
        second = second->next;
    }

    // Remove node
    struct Node* temp = second->next;
    second->next = second->next->next;
    free(temp);

    struct Node* newHead = dummy->next;
    free(dummy);
    return newHead;
}

2. Merge Two Sorted Lists

C:

struct Node* mergeSorted(struct Node* l1, struct Node* l2) {
    if (l1 == NULL) return l2;
    if (l2 == NULL) return l1;

    struct Node* result = NULL;

    if (l1->data <= l2->data) {
        result = l1;
        result->next = mergeSorted(l1->next, l2);
    } else {
        result = l2;
        result->next = mergeSorted(l1, l2->next);
    }

    return result;
}

3. Check Palindrome

C:

int isPalindrome(struct Node* head) {
    if (head == NULL || head->next == NULL) return 1;

    // Find middle
    struct Node* slow = head;
    struct Node* fast = head;

    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }

    // Reverse second half
    struct Node* secondHalf = reverse(slow);

    // Compare
    struct Node* p1 = head;
    struct Node* p2 = secondHalf;

    while (p2 != NULL) {
        if (p1->data != p2->data) {
            return 0;
        }
        p1 = p1->next;
        p2 = p2->next;
    }

    return 1;
}

Arrays vs Linked Lists

Complexity Summary

*With tail pointer

Common Mistakes

1. Memory leaks - Not freeing deleted nodes in C/C++
2. Losing head reference - Modifying head without saving
3. NULL pointer dereference - Not checking for NULL before accessing
4. Off-by-one errors - Wrong loop conditions
5. Circular references - Creating cycles accidentally
6. Forgetting edge cases - Empty list, single node
7. Wrong pointer updates - Incorrect order of assignments

Debugging Tips

1. Draw diagrams - Visualize pointer changes
2. Check NULL - Always verify before dereferencing
3. Test edge cases - Empty, single node, two nodes
4. Use print statements - Display list after each operation
5. Valgrind for C - Detect memory leaks
6. Watch for cycles - Can cause infinite loops
7. Verify all paths - Test each branch in conditionals

Mini Exercises

1. Implement a function to find the length of a linked list
2. Delete alternate nodes from a linked list
3. Check if two linked lists intersect
4. Remove duplicates from a sorted linked list
5. Rotate a linked list by k positions
6. Find the intersection point of two lists
7. Clone a linked list with random pointers
8. Flatten a multilevel doubly linked list
9. Add two numbers represented by linked lists
10. Swap nodes in pairs

Review Questions

1. Why is accessing the nth element O(n) in a linked list?
2. When would you use a doubly linked list over a singly linked list?
3. How does Floyd's cycle detection algorithm work?
4. What are the advantages of a circular linked list?
5. How can you optimize insertion at the end to O(1)?

Reference Checklist

By the end of this chapter, you should be able to:

• Implement singly linked list operations
• Understand doubly and circular linked lists
• Reverse a linked list iteratively and recursively
• Detect and remove cycles
• Find middle element using two pointers
• Merge sorted lists
• Implement complex list manipulations
• Choose between arrays and linked lists

Next Steps

Now that you understand linked lists, Chapter 6 explores stacks—a Last-In-First-Out (LIFO) data structure that can be implemented using arrays or linked lists. You'll learn stack operations, applications like expression evaluation, and real-world use cases.

---

Key Takeaway: Linked lists trade random access speed for insertion/deletion flexibility. Understanding pointers and edge cases is crucial. They're the foundation for many advanced data structures and are essential for dynamic memory management scenarios.