# 1. Introduction to Linked Lists

### 1.1 What is a Linked List?

A **linked list** is a linear data structure where elements are not stored in contiguous memory locations. Instead, each element (called a **node**) contains:
1. **Data:** The actual value stored
2. **Pointer(s):** Reference to the next (and possibly previous) node

**Analogy:**
Think of a linked list like a treasure hunt:
- Each clue (node) contains information (data)
- Each clue also tells you where to find the next clue (pointer)
- You start at the first clue (head)
- The last clue says "End of hunt" (NULL pointer)

**Visual Representation:**
```
Array (Contiguous Memory):
┌────┬────┬────┬────┬────┐
│ 10 │ 20 │ 30 │ 40 │ 50 │
└────┴────┴────┴────┴────┘
 [0]  [1]  [2]  [3]  [4]

Linked List (Non-contiguous Memory):
HEAD
 ↓
┌────┬────┐    ┌────┬────┐    ┌────┬────┐    ┌────┬────┐
│ 10 │ ●──┼───→│ 20 │ ●──┼───→│ 30 │ ●──┼───→│ 40 │NULL│
└────┴────┘    └────┴────┘    └────┴────┘    └────┴────┘
 data  next     data  next     data  next     data  next
```

### 1.2 Why Use Linked Lists?

**Advantages:**
1. **Dynamic Size:** Can grow or shrink at runtime
2. **Easy Insertion/Deletion:** No need to shift elements
3. **Memory Efficient:** Allocate memory only when needed
4. **Flexible Structure:** Can implement stacks, queues, graphs

**Disadvantages:**
1. **No Random Access:** Must traverse from beginning
2. **Extra Memory:** Requires space for pointers
3. **Sequential Access:** Slower than arrays for direct access
4. **Cache Performance:** Poor cache locality

### 1.3 Types of Linked Lists

```
1. Singly Linked List
   HEAD → [data|next] → [data|next] → [data|NULL]

2. Doubly Linked List
   HEAD ⇄ [prev|data|next] ⇄ [prev|data|next] ⇄ [prev|data|NULL]

3. Circular Linked List
   HEAD → [data|next] → [data|next] → [data|next] ──┐
    ↑                                                 │
    └─────────────────────────────────────────────────┘

4. Circular Doubly Linked List
   HEAD ⇄ [prev|data|next] ⇄ [prev|data|next] ──┐
    ↑                                            │
    └────────────────────────────────────────────┘
```

### 1.4 Linked List vs Array

| Feature | Array | Linked List |
|---------|-------|-------------|
| Memory Allocation | Contiguous | Non-contiguous |
| Size | Fixed | Dynamic |
| Access Time | O(1) | O(n) |
| Insertion (beginning) | O(n) | O(1) |
| Insertion (end) | O(1) | O(n) or O(1) with tail |
| Deletion (beginning) | O(n) | O(1) |
| Memory Usage | Less (no pointers) | More (pointers) |
| Cache Performance | Better | Worse |
| Random Access | Yes | No |