Introduction
The deeper you go into Data Structures and Algorithms, the more you start noticing patterns. Each new structure doesn't just stand alone, it builds on what came before, layering on complexity while keeping familiar elements that make the learning curve feel less steep.
As I continue my DSA journey, this blog picks up right where my last one left off. If you haven't read it yet, I covered linked lists here the foundation we'll be extending today. This time, we're levelling up to the doubly linked list.
Think of it this way: a regular linked list is like a one-way street. Each node knows where to go next, but it has no memory of where it's been. A doubly linked list? That's a two-way street. Each node still points forward with next, but now it also looks backward with previous.
This simple change unlocks powerful new possibilities. We gain a tail property that works like head in reverse, letting us traverse from back to front just as easily as front to back. I'll show you exactly how that works later on.
By the end of this blog, you'll understand how doubly linked lists operate, how to build one in JavaScript, and why this "upgrade" makes certain operations more flexible even if they require a few extra considerations.
Linked List vs Doubly Linked List
If you recall from my last blog, a regular linked list is a one-way street. Each node only knows what's ahead:
A -> B -> C
This works fine until you need to go backwards. Forgot to handle a value? Tough luck, you're looping back from the start. It's like trying to retrace your steps in a maze where the path behind you disappears.
A doubly linked list fixes this by adding that previous pointer I mentioned. Now each node looks both ways:
Null <- A <-> B <-> C -> Null
Think of it like a text editor's undo/redo history. When you type "Hello", that's a node. When you backspace, that's another. Hit Ctrl+Z and you move previous through your changes. Hit Ctrl+Y and you move next to redo them. Each action remembers what came before and what comes after.
I'll admit, managing those two-way connections can feel like juggling at first, especially when you need to swap nodes around. But once you see the pattern, it clicks. And the payoff is worth it: you get a data structure that's far more flexible for certain problems.
Building a Doubly Linked List
Let's build this from the ground up, starting with the individual nodes.
If you remember from the last blog, a regular linked list node looks like this:
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
- value holds the actual data you want to store.
- next is a pointer to the next node in the list.
- If next is null, that means the node is the end of the list.
Each node holds some data and knows where to find the next one. But it's only looking forward, like a person who never looks over their shoulder.
For a doubly linked list, we just add one more property:
class Node {
constructor(value) {
this.value = value;
this.next = null;
this.prev = null;
}
}
That prev pointer is the secret sauce. Now each node can glance backwards at its predecessor, creating those two-way connections we talked about.
Let me show you how this works by manually wiring up three nodes:
const node1 = new Node("A");
const node2 = new Node("B");
const node3 = new Node("C");
node1.next = node2;
node2.prev = node1;
node2.next = node3;
node3.prev = node2;
console.log(node1);
// Null <- A <-> B <-> C -> Null
See how we're creating a chain where each node introduces itself to its neighbours? Node A says "My next is B," and Node B says "My previous is A." It's like a digital handshake in both directions.
Now for the list itself. Since we're building on the linked list foundation, our class structure looks similar, but we need that tail property to track the end:
class LinkedList {
length = 0;
head = null;
tail = null;
size() {
return this.length;
}
isEmpty() {
return this.length === 0;
}
}
Here's what each piece does:
head is our entry point - the first node in the list
tail is our exit point - the last node, which we'll use to traverse backwards
length keeps count, so we don't have to loop through to know how many nodes we have
size() and isEmpty() are convenience methods you'll use constantly
The foundation is set. Now we can start adding the real functionality, beginning with the most common operation: appending new nodes to the end.
Append (Add to End)
Let's start with the most common operation: adding a new node to the end. We call this appending.
Appending means we create a new node and place it after the current last element, making it the new tail.
If the list is empty, this new node simply becomes both the head and tail.
Here's the code:
append(value) {
let node = new Node(value);
if (this.head == null) {
this.head = node;
this.tail = node;
this.length++;
return;
}
this.tail.next = node;
node.prev = this.tail;
this.tail = node;
this.length++;
return
}
Let's break this down step by step.
First, we create a new node. Then we check if the list is empty, meaning the head is null. If it is, this new node becomes both head and tail since it's the only element.
If the list isn't empty, we do three things:
- Set the current tail's next pointer to our new node
- Set our new node's prev pointer back to the current tail
- Reassign tail to point to our new node (it's now the end)
Then we increment the length and we're done.
Example:
const list = new LinkedList();
list.append("A");
list.append("B");
list.append("C");
console.log(list.head);
// Null <- A <-> B <-> C -> Null
Time Complexity: O(1) we place the new node at the end of the list where the tail is, no traversal needed.
Space Complexity: O(1) we create only one new node regardless of list size.
Prepend (Add to Start)
While append adds to the end, prepend adds a new node to the beginning, right before the current head.
The process is straightforward: create a new node, link it to the existing head, then update the head to point to this new node.
Here's the implementation:
prepend(value) {
let node = new Node(value);
if (this.head == null) {
this.head = node;
this.tail = node;
this.length++;
return;
}
node.next = this.head;
this.head.prev = node;
this.head = node;
this.length++;
return;
}
If the list is empty, the new node becomes both head and tail, the same as append.
If the list has nodes, we do three things:
- Set the new node's next pointer to the current head
- Set the current head's prev pointer back to the new node
- Reassign the head to point to our new node
Then increment the length.
Example:
const list = new LinkedList();
list.append("A");
list.append("B");
list.append("C");
list.prepend("D");
console.log(list.head);
// Null <- D <-> A <-> B <-> C -> Null
Time Complexity: O(1) we add the node directly at the start, no traversal needed.
Space Complexity: O(1) only one new node created.
Compared to arrays, where inserting at the start requires shifting every other element, linked lists make this effortless. You just hook up the new node and update a single pointer.
Delete (Remove a Node)
Now that we can add nodes, let's learn how to remove them. The delete() method removes a specific node by its value.
This operation is more involved than adding because we have to handle several edge cases: empty lists, removing the head or tail, and nodes in the middle.
Here's the implementation:
delete(value) {
if (this.head == null) {
return "Error: linked list is empty";
}
let curr = this.head;
while (curr !== null) {
if (curr.value === value) {
break;
}
curr = curr.next;
}
if (curr === null) {
return "Value wasn't in linked list";
}
if (curr === this.head) {
this.head = curr.next;
} else {
curr.prev.next = curr.next;
}
if (curr === this.tail) {
this.tail = curr.prev;
} else {
curr.next.prev = curr.prev;
}
curr.next = null;
curr.prev = null;
this.length--;
return curr;
}
Here's what happens step by step:
First, we check if the list is empty. If it is, we return an error.
Next, we start at the head and loop through until we find the node with the matching value. If we reach the end without finding it, we return another error.
Once we find the node, we handle four possible scenarios:
If it's the head: Move the head to point to the next node
If it's the tail: Move the tail to point to the previous node
If it's in the middle: Link the node's neighbours directly to each other (bypassing the current node)
If it's the only node: Both head and tail become null
Finally, we clean up by nullifying the removed node's pointers and decrementing the length.
Example:
const list = new LinkedList();
list.append("A");
list.append("B");
list.append("C");
list.delete("B");
console.log(list.head);
// Null <- A <-> C -> Null
- Time Complexity: O(n) in the worst case, we might need to traverse the entire list to find the node.
- Space Complexity: O(1) we only adjust pointers, no new data is stored.
Deleting can be tricky because you have to reassign all the links correctly. Double-check your logic, especially around the head and tail edge cases.
Get First and Get Last
These methods let you peek at the ends of your list without removing anything.
getFirst() {
return this.head;
}
getLast() {
return this.tail;
}
- getFirst() → Time: O(1), Space: O(1)
- getLast() → Time: O(1), Space: O(1)
Now that we’ve built all the core methods, let’s look at the full linked list.
Below is the complete class setup, including everything we’ve learned from creating nodes to appending, prepending, and deleting.
class Node {
constructor(value) {
this.value = value;
this.next = null;
this.prev = null;
}
}
class LinkedList {
length = 0;
head = null;
tail = null;
size() {
return this.length;
}
isEmpty() {
return this.length === 0;
}
append(value) {
let node = new Node(value);
if (this.head == null) {
this.head = node;
this.tail = node;
this.length++;
return;
}
this.tail.next = node;
node.prev = this.tail;
this.tail = node;
this.length++;
return
}
prepend(value) {
let node = new Node(value);
if (this.head == null) {
this.head = node;
this.tail = node;
this.length++;
return;
}
node.next = this.head;
this.head.prev = node;
this.head = node;
this.length++;
return;
}
delete(value) {
if (this.head == null) {
return "Error: linked list is empty";
}
let curr = this.head;
while (curr !== null) {
if (curr.value === value) {
break;
}
curr = curr.next;
}
if (curr === null) {
return "Value wasn't in linked list";
}
if (curr === this.head) {
this.head = curr.next;
} else {
curr.prev.next = curr.next;
}
if (curr === this.tail) {
this.tail = curr.prev;
} else {
curr.next.prev = curr.prev;
}
curr.next = null;
curr.prev = null;
this.length--;
return curr;
}
getFirst() {
return this.head;
}
getLast() {
return this.tail;
}
}
Now that the full class is ready, let’s test it out with a few operations:
const list = new LinkedList();
list.append("A");
list.append("B");
list.append("C");
console.log("First:", list.getFirst().value); // A
console.log("Last:", list.getLast().value); // C
console.log("Size:", list.size()); // 3
list.prepend("D");
list.delete("B");
console.log("After Updates:");
console.log("First:", list.getFirst().value); // D
console.log("Last:", list.getLast().value); // C
console.log("Is Empty:", list.isEmpty()); // false
console.log("Size:", list.size()); // 3
Results:
First: A
Last: C
Size: 3
After Updates:
First: D
Last: C
Is Empty: false
Size: 3
Once you run this code, you'll see exactly how nodes connect and adjust as you add or remove data. There's no array indexing, no shifting elements around, everything happens through simple pointer management between nodes.
That's what makes doubly linked lists so powerful: you get a chain-like structure that's both simple and flexible, perfect for dynamic collections where you don't know how much data you'll need to handle upfront.
Extra Methods
I separated these methods because they're a bit more advanced. Once you're comfortable with the core operations, these will give you even more control over your list.
swapValue
This method swaps the values of two nodes without changing their positions.
swapValue(value1,value2) {
let curr = this.head;
let node1 = null;
let node2 = null;
while (curr !== null) {
if (curr.value === value1) {
node1 = curr;
}
if (curr.value === value2) {
node2 = curr;
}
curr = curr.next;
}
if(node1 === null || node2 === null){
return "Can't swap values as value is not in list";
}
let temp = node1.value
node1.value = node2.value
node2.value = temp
return
}
Here's what happens:
We traverse the entire list looking for both values. If we can't find either one, we return an error. Once we have both nodes, we use a temporary variable to swap their values.
- Time complexity: O(n) since we might need to scan the whole list.
- Space complexity: O(1) we're only swapping values, not moving nodes.
insertAt
This method inserts a new node at a specific position.
insertAt(value, pos) {
if (pos < 0 || pos > this.length) {
return "Invalid position.";
}
const newNode = new Node(value);
if (pos === 0) {
newNode.next = this.head;
if (this.head) {
this.head.prev = newNode;
} else {
this.tail = newNode;
}
this.head = newNode;
this.length++;
return;
}
if (pos === this.length) {
newNode.prev = this.tail;
if (this.tail) {
this.tail.next = newNode;
}
this.tail = newNode;
this.length++;
return;
}
let count = 0;
let curr = this.head;
while (count < pos) {
curr = curr.next;
count++;
}
const prevNode = curr.prev;
newNode.next = curr;
newNode.prev = prevNode;
prevNode.next = newNode;
curr.prev = newNode;
this.length++;
}
We handle three cases:
- Position 0: Insert at the head using the same logic as prepend
- Position at length: Insert at the tail using the same logic as append
- Middle position: Traverse to the target position, then insert the new node between prevNode and curr
- Time complexity: O(n) in the worst case when inserting in the middle.
- Space complexity: O(1)
deleteAt
This method removes a node at a specific position.
deleteAt(pos) {
if (pos < 0 || pos >= this.length) {
return "Invalid position.";
}
let curr = this.head;
if (pos === 0) {
this.head = curr.next;
if (this.head) {
this.head.prev = null;
} else {
this.tail = null;
}
curr.next = null;
this.length--;
return curr;
}
let count = 0;
while (count < pos) {
curr = curr.next;
count++;
}
const prevNode = curr.prev;
const nextNode = curr.next;
prevNode.next = nextNode;
if (nextNode === null) {
this.tail = prevNode;
} else {
nextNode.prev = prevNode;
}
curr.next = null;
curr.prev = null;
this.length--;
return curr;
}
We handle two main cases:
Position 0: Remove the head by moving the head to the next and cleaning up pointers
Other positions: Traverse to the target node, then bypass it by linking prevNode directly to nextNode. If we're removing the tail, we update tail to point to prevNode
We always clean up the removed node's pointers and decrement the length.
- Time complexity: O(n) in the worst case
- Space complexity: O(1)
These were just some of the more advanced methods you could come across to show how a doubly linked list works.
Conclusion
And that's our deep dive into Doubly Linked Lists, a simple but powerful upgrade to the singly linked list that gives you bidirectional traversal without sacrificing much performance.
Now that you understand how to build and manage one in JavaScript, you've added another versatile tool to your data structure toolkit, one that shines in scenarios like browser history, undo/redo systems, and anywhere you need to move both forward and backwards through data.
If you enjoyed this blog and want to keep learning, check out these other blogs in the series:
Understanding JavaScript Closures
Helpful resources for your web development journey
Thanks for reading and happy coding as you keep building your DSA skills!
Top comments (0)