Introduction to Linked List
What is a Linked List?
A Linked List is a linear data structure used to store a collection of elements, called nodes, where each node contains two parts:
- Data – the value stored in the node
- Pointer (or Reference) – the address of the next node in the sequence
Unlike arrays, linked lists do not store elements in contiguous memory locations. Instead, each node points to the next node, forming a chain-like structure.
Simple Definition
A linked list is a collection of nodes where:
- Each node stores data
- Each node points to the next node
- The last node points to NULL (or the first node in circular lists)
This dynamic nature makes linked lists one of the most important data structures in computer science.
Why Do We Need Linked Lists?
To understand the need for linked lists, we must first look at the limitations of arrays.
Limitations of Arrays
- Fixed size (in static arrays)
- Costly insertion and deletion
- Memory wastage or overflow
- Requires contiguous memory allocation
Linked lists overcome these limitations by:
- Allowing dynamic memory allocation
- Enabling efficient insertion and deletion
- Using memory more flexibly
Linked List vs Array
| Feature | Array | Linked List |
|---|---|---|
| Memory Allocation | Contiguous | Non-contiguous |
| Size | Fixed (or resizing costly) | Dynamic |
| Insertion | Costly | Efficient |
| Deletion | Costly | Efficient |
| Random Access | Allowed | Not allowed |
| Cache Friendly | Yes | No |
Key Insight
- Use arrays when fast access is required
- Use linked lists when frequent insertions/deletions are required
Real-Life Analogy of Linked List
Imagine a train:
- Each coach is a node
- Each coach knows only the next coach
- Coaches are connected via couplings
- Coaches can be added or removed easily
This is exactly how a linked list works.
Node Structure in Linked List
A node is the fundamental building block of a linked list.
Components of a Node
- Data field – stores the actual value
- Next pointer – stores the address of the next node
Example Node Structure (Conceptual)
| Data | Next |
For a doubly linked list:
| Prev | Data | Next |
Memory Allocation in Linked List
Linked lists use dynamic memory allocation, which typically happens in the heap memory.
Heap vs Stack
| Stack | Heap |
|---|---|
| Static allocation | Dynamic allocation |
| Fast | Slightly slower |
| Limited size | Large size |
Each node is created at runtime, making linked lists flexible and memory-efficient.
Types of Linked Lists
Linked lists are classified based on how nodes are connected.
_1772810547.png)
Singly Linked List
Definition
A singly linked list is a linked list where:
- Each node contains data and a pointer to the next node
- Traversal is possible only in one direction
Structure
Head → Node1 → Node2 → Node3 → NULL
Characteristics
- Simple structure
- Less memory usage
- One-directional traversal
Use Cases
- Stack implementation
- Queue implementation
- Hash table chaining
Doubly Linked List
Definition
A doubly linked list is a linked list where:
- Each node has two pointers
- One pointer points to the previous node
- Another pointer points to the next node
Structure
NULL ← Node1 ⇄ Node2 ⇄ Node3 → NULL
Characteristics
- Bidirectional traversal
- More memory usage
- Easier deletion operations
Use Cases
- Browser history
- Undo/Redo functionality
- Music playlists
Circular Linked List
Definition
A circular linked list is a linked list where:
- The last node points back to the first node
- There is no NULL pointer
Types
- Circular Singly Linked List
- Circular Doubly Linked List
Structure
Node1 → Node2 → Node3
↑ ↓
← ← ← ← ← ← ← ←
Characteristics
- No NULL reference
- Efficient traversal from any node
- Useful in cyclic operations
Use Cases
- CPU scheduling
- Multiplayer games
- Round-robin algorithms
Head Pointer in Linked List
The head pointer stores the address of the first node.
Important Notes
- If head is NULL, the list is empty
- All operations start from the head
- Losing the head means losing access to the list
Traversal in Linked List
Traversal means visiting each node one by one.
Key Points
- Always start from the head
- Continue until NULL is reached
- Time complexity: O(n)
Traversal is slower than arrays because random access is not possible.
Advantages of Linked List
- Dynamic size
- Efficient insertion and deletion
- No memory wastage
- Flexible memory allocation
- Useful for implementing other data structures
Disadvantages of Linked List
- Extra memory for pointers
- No random access
- Not cache-friendly
- Reverse traversal difficult in singly lists
- More complex than arrays
Time Complexity Overview
| Operation | Time Complexity |
|---|---|
| Access | O(n) |
| Insertion | O(1)* |
| Deletion | O(1)* |
| Search | O(n) |
* When node position is known
Applications of Linked List
Linked lists are used in:
- Stack implementation
- Queue implementation
- Deque
- Browser history
- Memory management
- Polynomial representation
- Sparse matrices
- LRU cache
Linked List in Competitive Programming
Linked lists appear frequently in:
- Coding interviews
- Competitive programming
- System design problems
Understanding linked lists deeply helps in mastering:
- Trees
- Graphs
- Advanced data structures
Common Beginner Mistakes
- Forgetting to update head
- Losing reference to nodes
- Incorrect pointer assignment
- Not handling empty list cases
- Memory leaks
Summary
A linked list is a fundamental data structure that:
- Stores data dynamically
- Uses nodes connected via pointers
- Comes in multiple forms (singly, doubly, circular)
- Plays a critical role in computer science
Mastering linked lists builds a strong foundation for advanced data structures and algorithmic thinking.
.png)
.png)
