Definition
A Linked List is a data structure where each node contains data and a pointer to the next node. Unlike arrays, nodes are not stored contiguously in memory, making middle insertion/deletion efficient.
Key Characteristics
- ✓Dynamic Size: Unlike arrays, size is not fixed and grows as needed.
- ✓Node Structure: Each node consists of [data | next pointer].
- ✓head/tail: Pointers to the start (head) and end (tail) of the list.
- ✓Sequential Access: Cannot access by index directly; must traverse from head.
Use Cases
Used in these scenarios:
Frequent Insert/Delete
More efficient than arrays when frequently inserting or removing data in the middle.
Stack/Queue Implementation
Can efficiently implement stacks (LIFO) and queues (FIFO) using linked lists.
Music Playlist
Suitable for playlists with previous/next track navigation (doubly linked list).
Undo Feature
Linked lists are used to implement undo functionality in editors.
Operations
Main operations:
append(value)
O(1)Add a new node at the end (tail) of the list.
prepend(value)
O(1)Add a new node at the front (head) of the list.
insert(index, value)
O(n)Insert a new node at a specific index. Requires traversal to that position.
delete(index)
O(n)Delete the node at a specific index. Modify the previous node's pointer.
search(value)
O(n)Find a node with a specific value. Traverse sequentially from head.
Complexity
Time Complexity
Space Complexity
Understand Deeper with Visualization
See how the algorithm works through step-by-step animations and code execution.
Start Visualization