Linked List

What is a Linked List?

A Linked List is a linear data structure where elements (called nodes) are connected using pointers. Each node contains:

• Data: The value stored in the node

• Pointer (or reference): Points to the next node in the list

Unlike arrays, linked lists do not store elements in contiguous memory locations.

---

Structure of a Node

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

---

Types of Linked Lists

1. Singly Linked List
   Each node points to the next node. The last node points to NULL.

2. Doubly Linked List
   Each node has two pointers:

   • next → next node

   • prev → previous node

3. Circular Linked List
   The last node points back to the first node, forming a circle.

---

Why Linked Lists Instead of Arrays?

• Dynamic Size: No need to pre-define size like arrays

• Efficient Insertion/Deletion: O(1) at the beginning or end (with pointers)

• No Wasted Memory: Allocate memory as needed

However:

• No Random Access: To access the nth element, you must traverse from the start (O(n))

• Extra Memory: Each node stores an additional pointer

---

Common Operations

1. Traversal

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

Time Complexity: O(n)

---

2. Insertion

• At beginning: O(1)

• At end: O(n) (unless we maintain a tail pointer)

• At specific position: O(n)

---

3. Deletion

• First node: O(1)

• Last node or specific node: O(n)

---

4. Searching

Linear search by traversing the list: O(n)

---

Visual Representation

Imagine a chain:

[10 | next] -> [20 | next] -> [30 | next] -> NULL

---

Advantages

• Dynamic memory allocation

• Efficient insertions and deletions

Disadvantages

• No direct access by index

• Extra memory for pointers

• Slower traversal compared to arrays

---

Real-World Applications

• Dynamic memory management (e.g., malloc/free in OS)

• Undo functionality in text editors

• Navigation systems (Forward and backward links)