Hey friends 👋
Today, I wanted to talk about the concept of running time as we've been referencing it a lot in our DSA series but one of my readers, @prime_1 , suggested covering doubly linked lists next. If you’ve read my last tutorial on singly linked lists but it sounded complicated, don’t worry. I’ll break this down and simplify it as much as possible.
What is a Doubly Linked List?
Think of it like a chain of nodes. Each node is a small box that stores two things:
- The actual data (e.g. a number, text, etc.)
- Pointers (or links) to the node before it and the node after it.
That’s the difference from a singly linked list. In a singly linked list, you can only move forward (you can see that in the tutorial, if you read it, I used this.next
). Simply:
- Node Structure: Each Node only has a next pointer (this.next), which points to the subsequent node in the sequence. It does not have a prev pointer.
- Traversal Direction: Traversal can only happen in one direction: from the head to the tail by following the next pointers, as demonstrated in the print method.
In contrast, in doubly linked list, you can move both forward and backward because each node knows about its neighbour on both sides, so we can have this.prev
and this.next
.
Visualising it
null <- [10] <-> [20] <-> [30] -> null
- The first node (10) has no previous link (
null
). - The last node (30) has no next link (
null
). - Everything in the middle points both ways.
⚡ Running Time (Big-O)
Here’s how common operations perform in a doubly linked list:
-
Traversal (go through the list):
O(n)
→ You may need to check every node. -
Search (find a value):
O(n)
→ Same reason, no shortcuts. -
Insert at the beginning or end:
O(1)
→ You just rewire a couple of pointers. -
Delete at the beginning or end:
O(1)
→ Again, just pointer updates. -
Insert/Delete in the middle:
O(n)
→ You first need to find the spot by traversing.
So, linked lists aren’t always “faster” than arrays. They shine when you’re doing a lot of insertions and deletions, especially at the edges.
Why use it?
- You can traverse in both directions.
- Inserting or deleting nodes in the middle is quicker than with arrays because you don’t shift everything around.
- They’re used in things like browsers’ back/forward history, music playlists, or undo/redo systems.
Let’s Code One
Here’s a simple implementation in JavaScript. Nothing fancy, just to see how it works:
// Node structure
class Node {
constructor(data) {
this.data = data;
this.prev = null;
this.next = null;
}
}
// Doubly Linked List
class DoublyLinkedList {
constructor() {
this.head = null;
this.tail = null;
}
// Add node at the end
append(data) {
const newNode = new Node(data);
if (!this.head) {
this.head = this.tail = newNode;
return;
}
this.tail.next = newNode;
newNode.prev = this.tail;
this.tail = newNode;
}
// Print list forward
printForward() {
let current = this.head;
let result = "";
while (current) {
result += current.data + " ";
current = current.next;
}
console.log("Forward:", result.trim());
}
// Print list backward
printBackward() {
let current = this.tail;
let result = "";
while (current) {
result += current.data + " ";
current = current.prev;
}
console.log("Backward:", result.trim());
}
}
// Example
const dll = new DoublyLinkedList();
dll.append(10);
dll.append(20);
dll.append(30);
dll.printForward(); // Forward: 10 20 30
dll.printBackward(); // Backward: 30 20 10
Try it Out
I’ve put this on CodePen so you can tweak it:
👉 Play with the Doubly Linked List on CodePen
(Open it, add more numbers, print them out, and watch the list grow.)
🙋🏽♀️ Over to You!
That’s the basics of a doubly linked list:
- Each node has links to both the previous and next node.
- You can traverse both ways.
- Running times depend on the operation. Insertions/deletions at the edges are fast, searching is slower.
- They’re super handy for dynamic data where order matters.
Next week we’ll take another step with data structures and see what running time means, but for now, play around with the CodePen and let the concept sink in.
Let me know if you do the Codepen challenge! I'd like to see yours! Connect with me on GitHub
Was this tutorial helpful? Got questions? Or any insight to help me write better tutorials? Let me know in the 💬!
That’s it for today’s midweek mini tutorial!
I’m keeping things light, fun and useful; one small project at a time.
If you enjoyed this, leave a 💬 or 🧡 to let me know.
And if you’ve got an idea for something you'd like me to try out next Wednesday, drop it in the comments. 👇
Follow me to see more straight-forward and short tutorials like this :)
If you are curious about what I do, check out my Portfolio
:-)
Web trails
You can also find me here on LinkedIn
or here X (Twitter)
✍🏾 I’m documenting my learning loudly every Wednesday. Follow along if you're learning JavaScript too!
Let’s keep learning together!
See you next Wednesday, hopefully, I don't stand you up again😑🚀
Top comments (0)