Skip to main content

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

No comments to display

Back to top