Linked Lists

🔗 LINKED LISTS: The Chain of Friends

Imagine a treasure hunt where each clue tells you where to find the next clue. That’s exactly how linked lists work!

🌟 The Big Picture

What is a Linked List?

Think about a group of kids holding hands in a line. Each kid knows who’s next to them, but they don’t need to stand in numbered spots like in an array.

Simple Example:

• In an array: Kids stand in boxes labeled 1, 2, 3, 4…
• In a linked list: Kids just hold hands - each one points to their friend!

Why do we care?

• Adding a new friend? Just grab their hand - no need to shuffle everyone!
• Someone leaves? Just connect the neighbors directly!

graph LR
    A["🧒 Alice"] --> B["👦 Bob"] --> C["👧 Carol"] --> D["🚫 NULL"]

📦 What’s Inside Each Box? (Node Structure)

Every “box” in a linked list is called a node. It holds two things:

1. Data - The actual value (like a number or name)
2. Pointer - The address of the next node

struct Node {
    int data;       // The treasure
    struct Node* next; // Map to next
};

Real World Analogy: Each train car has:

• Passengers (data)
• A hook to the next car (pointer)

🚂 SINGLY LINKED LIST: One-Way Train

What Makes It “Singly”?

Each node can ONLY see the next node. Like a one-way street - you can go forward but not back!

graph TD
    H["HEAD 🚂"] --> A["10"]
    A --> B["20"]
    B --> C["30"]
    C --> N["NULL ⛔"]

Creating Your First Node

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

What’s happening?

1. We ask for memory space (malloc)
2. Store our value in data
3. Set next to NULL (no friend yet!)

Adding Nodes

At the Beginning (Fast! O(1))

void insertAtHead(
    struct Node** head, int value) {
    struct Node* newNode =
        createNode(value);
    newNode->next = *head;
    *head = newNode;
}

Like cutting in line at the front - quick but maybe rude! 😄

At the End (Slower: O(n))

void insertAtEnd(
    struct Node** head, int value) {
    struct Node* newNode =
        createNode(value);
    if (*head == NULL) {
        *head = newNode;
        return;
    }
    struct Node* temp = *head;
    while (temp->next != NULL) {
        temp = temp->next;
    }
    temp->next = newNode;
}

You walk to the end of the line, then add the new friend.

Traversing (Walking Through)

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

Output: 10 -> 20 -> 30 -> NULL

🚃 DOUBLY LINKED LIST: Two-Way Train

The Upgrade: Look Both Ways!

Now each node has TWO pointers:

• next → points to the next node
• prev → points to the previous node

graph LR
    N1["NULL"] <--> A["10"] <--> B["20"] <--> C["30"] <--> N2["NULL"]

Node Structure

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

Like holding hands with BOTH your neighbors!

Why Use Doubly Linked List?

Insert at Head

void insertAtHead(
    struct DNode** head, int value) {
    struct DNode* newNode =
        malloc(sizeof(struct DNode));
    newNode->data = value;
    newNode->prev = NULL;
    newNode->next = *head;

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

Traversing Both Ways

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

// Backward
void printBackward(struct DNode* tail) {
    while (tail != NULL) {
        printf("%d <-> ", tail->data);
        tail = tail->prev;
    }
}

🔄 REVERSE A LINKED LIST: Flip the Chain!

The Challenge

Turn 1 -> 2 -> 3 -> NULL into 3 -> 2 -> 1 -> NULL

The Trick: Three Friends Method

Imagine three people walking together:

• prev: Looks behind
• current: The walker
• next: Remembers who’s ahead

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

    while (current != NULL) {
        next = current->next;  // Remember
        current->next = prev;  // Flip arrow
        prev = current;        // Move prev
        current = next;        // Move current
    }
    return prev;  // New head!
}

Visual Step-by-Step

Start: 1 -> 2 -> 3 -> NULL

graph TD
    subgraph Step 1
    A1["prev=NULL"]
    B1["curr=1"] --> C1["2"] --> D1["3"] --> E1["NULL"]
    end

graph TD
    subgraph Step 2
    A2["1"] --> B2["NULL"]
    C2["prev=1"]
    D2["curr=2"] --> E2["3"] --> F2["NULL"]
    end

graph TD
    subgraph Final
    A3["3"] --> B3["2"] --> C3["1"] --> D3["NULL"]
    end

Result: 3 -> 2 -> 1 -> NULL 🎉

🔍 DETECT LOOP: Find the Cycle!

The Problem

Sometimes a linked list can have a loop - the last node points back to an earlier node instead of NULL!

graph LR
    A["1"] --> B["2"] --> C["3"] --> D["4"]
    D --> B

This is BAD! If you try to traverse, you’ll go forever!

The Solution: Floyd’s Tortoise and Hare 🐢🐰

The Story:

• A slow tortoise takes 1 step at a time
• A fast hare takes 2 steps at a time
• If there’s a loop, they WILL meet!
• If no loop, the hare reaches NULL first

Why Does This Work?

Think of a circular race track:

• The fast runner laps the slow runner
• They MUST meet eventually on a circle!

The Code

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

    while (fast != NULL &&
           fast->next != NULL) {
        slow = slow->next;       // 1 step
        fast = fast->next->next; // 2 steps

        if (slow == fast) {
            return 1;  // Loop found!
        }
    }
    return 0;  // No loop
}

Example Walkthrough

List with loop: 1 → 2 → 3 → 4 → (back to 2)

They meet at 4! 🎯 Loop detected!

🆚 QUICK COMPARISON

*If you keep a tail pointer **If you have the node reference

🎯 WHEN TO USE WHAT?

Use Singly Linked List when:

• You only need forward traversal
• Memory is limited
• Simple implementation preferred

Use Doubly Linked List when:

• You need backward traversal
• Frequent deletions in middle
• Browser history (back/forward buttons!)

Use Arrays when:

• You need random access by index
• Size is known and fixed
• Cache performance matters

🚀 KEY TAKEAWAYS

1. Nodes hold data + pointer(s)
2. Singly = one direction only
3. Doubly = both directions
4. Reverse = flip all arrows using 3 pointers
5. Detect Loop = slow and fast pointer trick

💡 Remember: Linked lists are like treasure hunts - each clue leads to the next adventure!

🧠 MEMORY TIP

Singly → Single direction → Simple Doubly → Dual direction → Delete easy

Floyd’s Algorithm: 🐢 Tortoise = Slow (1 step) 🐰 Hare = Fast (2 steps) 🤝 Meet = LOOP!