What is a Linked List?
A Linked List is a linear data structure where elements called nodes are stored in sequence. Each node contains data and a pointer (or link) to the next node in the sequence. Unlike arrays, linked lists do not store elements in contiguous memory locations.
The first node is called the head. The last node points to null to indicate the end of the list.
When to Use Linked List
Dynamic Size
When you don't know the total size upfront — lists grow and shrink at runtime without reallocation
Frequent Insertions/Deletions
When you need to add or remove elements often at arbitrary positions — O(1) at head vs O(n) for arrays
No Random Access Needed
When sequential traversal is acceptable and you rarely need O(1) access by index
Real-time Data Streams
When processing data as it arrives — buffers, streams, task queues
Consider an Array Instead When:
You need fast random access by index • You have a known, fixed size • Memory is constrained (pointer overhead) • You need cache-friendly access patterns
Node Structure
- ›Data: Stores the actual value (can be any data type)
- ›Next Pointer: Points to the next node in the sequence
- ›Head: First node of the list
- ›Null: Last node points to null to mark end
Types of Linked Lists
Each node has only a next pointer. Traversal is one-directional: from head to tail.
Each node has next and prev pointers. Can traverse both forward and backward.
Last node points back to the head (or first node), forming a circle. No null at the end.
Common Operations
| Operation | Description | Time Complexity |
|---|---|---|
| Insert at Head | Add new node at beginning | O(1) |
| Insert at Tail | Add new node at end | O(n) |
| Delete by Value | Remove first node with value | O(n) |
| Search | Find node by value | O(n) |
| Reverse | Reverse node order | O(n) |
Linked List vs Array
| Aspect | Linked List | Array |
|---|---|---|
| Memory | Dynamic, non-contiguous | Fixed size, contiguous |
| Access | Sequential only O(n) | Random access O(1) |
| Insert at Head | O(1) | O(n) — shift elements |
| Delete at Head | O(1) | O(n) — shift elements |
| Memory Overhead | Extra for pointers | No extra overhead |