TL;DR: A linked list is a chain of nodes where each element knows its neighbor's location. While searching for an element takes O(n) time because you must jump through every preceding link, removing the first item is a constant-time O(1) operation. This makes them the ideal structure for high-performance queues.
Arrays are usually the first thing we reach for, but they have a massive architectural overhead when you start messing with the front of the list. If you need to remove the first item in an array, the language has to shift every other element over to fill the gap. That is fine for ten items, but it is a performance killer for ten million. A linked list solves this by changing how we connect data in memory.
How does a linked list actually store data?
A linked list is a chain of nodes where each node contains its data and a pointer to the next node. Unlike arrays, these nodes don't have to live next to each other in a contiguous block of memory.
Think of it as being daisy-chained together. Each element knows where the thing after it is. In a doubly linked list, the element also knows where the thing before it is. Because each piece of data points to the next, the list can be scattered all over your memory, but the logic remains a single, continuous line. You don't have indices; you just have links.
Why is finding an element in a linked list O(n) time?
Search is O(n) because you have to jump through every link from the first item to reach your target. There is no way to skip ahead to the $i$th element because you don't know where it is until you've visited the element before it.
Let's be real: search is the linked list’s biggest weakness. If you want to find the 10th item, you start at node one. Node one tells you where node two is. You jump to two. Node two tells you where node three is. You jump to three. You keep jumping until you hit your target. If you have $n$ items, you might have to jump $n$ times. That is why arrays—which let you jump straight to an index—are better for finding stuff, while linked lists are built for movement.
How do you remove the first element in O(1) time?
You update the 'head' pointer to the second node. The first node is effectively gone because nothing in the list points to it anymore, and the second node becomes the new start.
This is where linked lists win. To remove the head, you don't move any data. You just go to the second item in the list and remove its link to the first item. Now, the second item is the first, and it still maintains its links to everything that came after it. It’s a pointer swap that takes the same amount of time whether your list has five items or five billion.
// A quick look at O(1) head removal
function popHead(list) {
if (!list.head) return null;
const removedNode = list.head;
// Just point the head to the next link
list.head = list.head.next;
if (list.head) {
list.head.prev = null;
}
return removedNode.data;
}
| Feature |
Linked List |
Array |
| Search by Index |
O(n) - Must jump through links |
O(1) - Direct access |
| Insert/Delete at Start |
O(1) - Just update pointers |
O(n) - Must shift all items |
| Memory Layout |
Scattered - Each node points to next |
Contiguous - All items in a block |
| Use Case |
Queues, Stacks, Buffers |
Sorting, Random Access, Lookups |
When should you use a linked list instead of an array?
You should use a linked list when your primary operations involve adding or removing data from the ends of the list. This makes them the perfect backbone for queues.
Imagine a task runner that picks up jobs from a queue. If that queue is an array, every time you finish a job and shift it off the front, your CPU is working overtime to re-index the remaining tasks. If you use a linked list, you’re just messing around with the links a little bit. You drop the first link, reassign the head, and keep moving. It stays fast regardless of how many tasks are waiting in line.
FAQ
What is a doubly linked list?
A doubly linked list is a version where each node has two pointers: one pointing to the next node and one pointing to the previous node. This allows you to traverse the list in both directions, which is useful for things like browser history where you need to go both forward and backward.
Why do interviewers love asking about linked lists?
Interviewers love them because they test if you actually understand how memory and pointers work under the hood. It’s easy to call .shift() on an array in a high-level language without realizing it’s an O(n) operation; implementing a linked list proves you understand the underlying performance cost.
Can you have a circular linked list?
Yes. In a circular linked list, the tail node points back to the head node instead of pointing to null. This is common in systems where you need to cycle through items repeatedly, like a multiplayer game rotating through player turns.
Cheers!
