Linked List Data Structure

Introduction:
In the previous lesson we studied arrays, which store elements side by side in one block of memory. That makes reading any element by its index very fast, but inserting or deleting in the middle is slow, because every element after it has to shift.
A linked list solves that problem in a different way. Instead of one continuous block, a linked list is a chain of small objects called nodes. Each node holds a value and a pointer (a reference) to the next node. To add or remove an element you only change a few pointers; nothing has to shift.
How a Linked List Works
Every linked list has a head, the first node. Each node points to the next one, and the last node points to null, which marks the end of the list.
head
|
[10 | next] -> [20 | next] -> [30 | next] -> null
To find an element you start at the head and follow the next pointers one by one. This is called traversing the list.
Types of Linked Lists
1. Singly Linked List:
Each node points only to the next node. You can move forward but not backward. This is the simplest and most common type.
2. Doubly Linked List:
Each node has two pointers: next and prev. You can move in both directions, and deleting a node is easier because you can reach its previous node directly. The cost is one extra pointer per node.
null <- [prev | 10 | next] <-> [prev | 20 | next] <-> [prev | 30 | next] -> null
3. Circular Linked List:
The last node points back to the head instead of null, so the list forms a loop. This is useful for things that repeat in turns, such as a playlist on repeat or a round-robin task scheduler.
Building a Singly Linked List in JavaScript
1. The Node:
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
2. The List and Its Operations:
class LinkedList {
constructor() {
this.head = null;
this.size = 0;
}
// Add to the beginning: O(1)
prepend(value) {
const node = new Node(value);
node.next = this.head;
this.head = node;
this.size++;
}
// Add to the end: O(n), because we walk to the last node
append(value) {
const node = new Node(value);
if (!this.head) {
this.head = node;
} else {
let current = this.head;
while (current.next) current = current.next;
current.next = node;
}
this.size++;
}
// Find the first node with this value: O(n)
find(value) {
let current = this.head;
while (current) {
if (current.value === value) return current;
current = current.next;
}
return null;
}
// Remove the first node with this value: O(n)
remove(value) {
if (!this.head) return false;
if (this.head.value === value) {
this.head = this.head.next;
this.size--;
return true;
}
let current = this.head;
while (current.next && current.next.value !== value) {
current = current.next;
}
if (current.next) {
current.next = current.next.next; // skip over the removed node
this.size--;
return true;
}
return false;
}
toArray() {
const values = [];
let current = this.head;
while (current) {
values.push(current.value);
current = current.next;
}
return values;
}
}
3. Using It:
const list = new LinkedList();
list.append(20);
list.append(30);
list.prepend(10);
console.log(list.toArray()); // [10, 20, 30]
list.remove(20);
console.log(list.toArray()); // [10, 30]
console.log(list.find(30)); // Node { value: 30, next: null }
console.log(list.size); // 2
Reversing a Linked List
Reversing a linked list is one of the most popular interview questions. The trick is to walk through the list once and turn every next pointer around, keeping track of the previous node as you go.
reverse() {
let prev = null;
let current = this.head;
while (current) {
const next = current.next; // remember the rest of the list
current.next = prev; // turn the pointer around
prev = current; // move prev one step forward
current = next; // move current one step forward
}
this.head = prev;
}
This runs in O(n) time and uses O(1) extra memory, because it only uses three variables no matter how long the list is.
Time Complexity: Linked List vs Array
- Access by index: array O(1), linked list O(n), since you must walk from the head.
- Insert or delete at the beginning: array O(n), linked list O(1).
- Insert or delete at the end: array O(1) on average, linked list O(1) if you keep a
tailpointer, otherwise O(n). - Insert or delete in the middle (once you are at the node): array O(n), linked list O(1).
- Search for a value: O(n) for both.
- Memory: arrays are compact; linked lists use extra memory for each pointer and are less cache-friendly.
Rule of thumb: use an array when you read by index a lot. Use a linked list when you insert and remove at the ends or in the middle a lot, and rarely need random access.
Real-World Uses of Linked Lists
- Browser history: a doubly linked list lets you go back and forward between pages.
- Undo and redo in text editors.
- Music playlists with next and previous track (circular for repeat mode).
- Building other data structures: stacks, queues and hash table buckets are often built on linked lists.
- LRU caches combine a hash map with a doubly linked list to evict the least recently used item in O(1).
Conclusion:
A linked list stores data as a chain of nodes connected by pointers. It trades fast index access for fast insertion and deletion. You learned the singly, doubly and circular variants, built a singly linked list in JavaScript with prepend, append, find, remove and reverse, and compared its time complexity with arrays. In the next lesson we will use these ideas to build two of the most important data structures in programming: the stack and the queue.


