aloalgo.comIntroduction to Linked Lists
A linked list is a linear data structure where elements are stored in nodes, and each node points to the next one. Unlike arrays, linked list elements are not stored contiguously in memory.The Node Structure
Each node contains two parts: the data and a reference (pointer) to the next node.Singly vs Doubly Linked Lists
| Type | Structure | Trade-off |
|---|---|---|
| Singly Linked | Each node points to next only | Less memory, can only traverse forward |
| Doubly Linked | Each node points to next and prev | More memory, can traverse both ways |
Linked List vs Array
| Operation | Array | Linked List |
|---|---|---|
| Access by index | O(1) | O(n) |
| Insert at beginning | O(n) | O(1) |
| Insert at end | O(1) amortized | O(1) with tail pointer |
| Insert in middle | O(n) | O(1) if you have the node |
| Delete at beginning | O(n) | O(1) |
| Delete in middle | O(n) | O(1) if you have the node |
| Memory layout | Contiguous, cache-friendly | Scattered, pointer overhead |
Why Arrays Are Fast for Access
Arrays store elements contiguously in memory. To access element at index i, the computer calculates:base_address + i * element_size. This is a single arithmetic operation - O(1).Linked lists must traverse from the head, following each pointer until reaching the desired position - O(n).Why Linked Lists Are Fast for Insert/Delete
When you insert or delete in an array, all subsequent elements must shift to maintain contiguous storage - O(n) elements need to move.In a linked list, insertion or deletion only requires updating a few pointers - O(1) once you have a reference to the node.When to Use Linked Lists
- Frequent insertions/deletions: When you need to add or remove elements at arbitrary positions often
- Unknown size: When you don't know the size upfront and want to avoid array reallocation
- Implementing other structures: Stacks, queues, and LRU caches are often built with linked lists
- No random access needed: When you only need sequential access
When to Use Arrays
- Random access: When you need to access elements by index frequently
- Cache efficiency: When performance matters and you're iterating through elements
- Memory efficiency: When you want to minimize memory overhead (no pointer storage)
- Fixed or known size: When the size is known in advance
Basic Operations
Common Interview Tips
- Draw it out: Linked list problems are much easier to solve when you visualize the pointers.
- Handle edge cases: Empty list (null head), single node, and operations on head/tail.
- Save references: Before modifying pointers, save any references you'll need later.
- Use dummy nodes: A dummy head simplifies edge cases when the head might change.
Was this helpful?
Company
Practice
Learn
© 2026 aloalgo.com. All rights reserved.