Doubly Linked List
Last updated
A doubly linked list is a linked list where each node holds two pointers: next (to the following node) and prev (to the preceding one). That extra backward link lets you traverse in both directions and delete a node in O(1) when you already have a reference to it - because you can reach its predecessor directly instead of walking from the head. Press play above to watch nodes link and relink both ways.
The cost is one extra pointer per node and more bookkeeping: every insert and delete must update both next and prev on the neighbors. It's the structure behind many deques and LRU caches, where fast removal from both ends matters.
Time complexity
| Operation | Complexity | Notes |
|---|---|---|
| Insert at head/tail | O(1) | With head and tail pointers |
| Delete a known node | O(1) | Reach prev directly - no walk |
| Search | O(n) | Still linear scan |
| Access by index | O(n) | No random access |
Singly vs doubly linked list
| Aspect | Singly | Doubly |
|---|---|---|
| Pointers per node | 1 (next) | 2 (next + prev) |
| Traverse backward | No | Yes |
| Delete a known node | O(n) (find prev) | O(1) |
| Memory overhead | Lower | Higher |
Worked example
Building [10, 20, 30] by appending, then deleting node 20:
| Step | Structure | Action |
|---|---|---|
| Start | null | Empty list: head and tail are both null |
| Append 10 | 10 | First node; head and tail both point to it, prev = next = null |
| Append 20 | 10 <-> 20 | Set 10.next = 20 and 20.prev = 10; tail = 20 |
| Append 30 | 10 <-> 20 <-> 30 | Set 20.next = 30 and 30.prev = 20; tail = 30 |
| Delete 20 | 10 <-> 30 | Using 20.prev and 20.next: set 10.next = 30 and 30.prev = 10 in O(1) |
When to use a doubly linked list
| Use it when | Avoid it when |
|---|---|
| You need to traverse or splice in both directions | You only ever move forward - a singly linked list is lighter |
You delete arbitrary nodes you already hold a reference to (O(1)) | You mostly index by position - use an array for O(1) access |
| You implement a deque, LRU cache, or on-screen undo history | Memory is tight - the extra prev pointer doubles link overhead |
| Insertions and removals happen at both ends frequently | The data is small and rarely changes - array copies are cheaper |
Doubly Linked List code
A clean, runnable Doubly Linked List implementation in Python, JavaScript, Java, C++, C. Pick a language, copy the code, or open it pre-loaded in the Coddy Playground.
Doubly Linked List code in Python
Python
1class Node:2 def __init__(self, value):3 self.value = value4 self.prev = None5 self.next = None6
7
8class DoublyLinkedList:9 def __init__(self):10 self.head = None11 self.tail = None12
13 def append(self, value):14 node = Node(value)15 if self.tail is None:16 self.head = self.tail = node17 return18 # Wire both directions: old tail <-> new node19 node.prev = self.tail20 self.tail.next = node21 self.tail = node22
23 def prepend(self, value):24 node = Node(value)25 if self.head is None:26 self.head = self.tail = node27 return28 node.next = self.head29 self.head.prev = node30 self.head = node31
32 def forward(self):33 values, current = [], self.head34 while current:35 values.append(current.value)36 current = current.next37 return values38
39 def backward(self):40 values, current = [], self.tail41 while current:42 values.append(current.value)43 current = current.prev44 return values45
46
47lst = DoublyLinkedList()48for value in [2, 3, 4]:49 lst.append(value)50lst.prepend(1)51
52print("Forward: ", lst.forward())53print("Backward:", lst.backward())Doubly Linked List code in JavaScript
JavaScript
1class Node {2 constructor(value) {3 this.value = value;4 this.prev = null;5 this.next = null;6 }7}8
9class DoublyLinkedList {10 constructor() {11 this.head = null;12 this.tail = null;13 }14
15 // Tail pointer makes append O(1)16 append(value) {17 const node = new Node(value);18 if (!this.tail) {19 this.head = node;20 this.tail = node;21 return;22 }23 node.prev = this.tail;24 this.tail.next = node;25 this.tail = node;26 }27
28 forward() {29 const out = [];30 for (let n = this.head; n; n = n.next) out.push(n.value);31 return out;32 }33
34 backward() {35 const out = [];36 for (let n = this.tail; n; n = n.prev) out.push(n.value);37 return out;38 }39}40
41const list = new DoublyLinkedList();42for (const value of [10, 20, 30, 40]) list.append(value);43console.log("Forward: ", list.forward().join(" <-> "));44console.log("Backward:", list.backward().join(" <-> "));Doubly Linked List code in Java
Java
1public class Main {2 static class Node {3 int value;4 Node prev, next;5 Node(int value) { this.value = value; }6 }7
8 static Node head, tail;9
10 static void append(int value) {11 Node node = new Node(value);12 if (head == null) { head = tail = node; return; }13 node.prev = tail;14 tail.next = node;15 tail = node;16 }17
18 // Unlink in O(1) once found: fix both neighbor pointers19 static void delete(int value) {20 for (Node cur = head; cur != null; cur = cur.next) {21 if (cur.value != value) continue;22 if (cur.prev != null) cur.prev.next = cur.next; else head = cur.next;23 if (cur.next != null) cur.next.prev = cur.prev; else tail = cur.prev;24 return;25 }26 }27
28 public static void main(String[] args) {29 append(1);30 append(2);31 append(3);32 append(4);33
34 StringBuilder forward = new StringBuilder("Forward:");35 for (Node cur = head; cur != null; cur = cur.next) forward.append(" ").append(cur.value);36 System.out.println(forward);37
38 StringBuilder backward = new StringBuilder("Backward:");39 for (Node cur = tail; cur != null; cur = cur.prev) backward.append(" ").append(cur.value);40 System.out.println(backward);41
42 delete(3);43 StringBuilder after = new StringBuilder("After delete 3:");44 for (Node cur = head; cur != null; cur = cur.next) after.append(" ").append(cur.value);45 System.out.println(after);46 }47}Doubly Linked List code in C++
C++
1#include <iostream>2
3struct Node {4 int value;5 Node* prev = nullptr;6 Node* next = nullptr;7 explicit Node(int v) : value(v) {}8};9
10struct DoublyLinkedList {11 Node* head = nullptr;12 Node* tail = nullptr;13
14 void append(int value) {15 Node* node = new Node(value);16 if (tail == nullptr) {17 head = tail = node;18 return;19 }20 node->prev = tail; // link both directions21 tail->next = node;22 tail = node;23 }24
25 void prepend(int value) {26 Node* node = new Node(value);27 if (head == nullptr) {28 head = tail = node;29 return;30 }31 node->next = head;32 head->prev = node;33 head = node;34 }35
36 void printForward() const {37 for (Node* cur = head; cur != nullptr; cur = cur->next) {38 std::cout << cur->value << " <-> ";39 }40 std::cout << "null\n";41 }42
43 void printBackward() const {44 for (Node* cur = tail; cur != nullptr; cur = cur->prev) {45 std::cout << cur->value << " <-> ";46 }47 std::cout << "null\n";48 }49};50
51int main() {52 DoublyLinkedList list;53 for (int value : {10, 20, 30}) list.append(value);54 list.prepend(5);55 std::cout << "Forward: ";56 list.printForward();57 std::cout << "Backward: ";58 list.printBackward();59 return 0;60}Doubly Linked List code in C
C
1#include <stdio.h>2#include <stdlib.h>3
4typedef struct Node {5 int value;6 struct Node* prev;7 struct Node* next;8} Node;9
10Node* head = NULL;11Node* tail = NULL;12
13Node* newNode(int value) {14 Node* n = calloc(1, sizeof(Node));15 n->value = value;16 return n;17}18
19void append(int value) {20 Node* node = newNode(value);21 if (tail == NULL) {22 head = tail = node;23 return;24 }25 node->prev = tail; // link both directions26 tail->next = node;27 tail = node;28}29
30void prepend(int value) {31 Node* node = newNode(value);32 if (head == NULL) {33 head = tail = node;34 return;35 }36 node->next = head;37 head->prev = node;38 head = node;39}40
41void printForward(void) {42 for (Node* cur = head; cur != NULL; cur = cur->next) {43 printf("%d <-> ", cur->value);44 }45 printf("NULL\n");46}47
48void printBackward(void) {49 for (Node* cur = tail; cur != NULL; cur = cur->prev) {50 printf("%d <-> ", cur->value);51 }52 printf("NULL\n");53}54
55int main(void) {56 int values[] = {10, 20, 30};57 for (int i = 0; i < 3; i++) append(values[i]);58 prepend(5);59 printf("Forward: ");60 printForward();61 printf("Backward: ");62 printBackward();63 return 0;64}Doubly Linked List FAQ
What is the difference between a singly and doubly linked list?
A singly linked list has one pointer per node (
next), so you can only move forward. A doubly linked list adds a prev pointer, letting you traverse backward and delete a node you hold a reference to in O(1) - at the cost of an extra pointer per node and updating two links on every change.When is a doubly linked list worth the extra memory?
When you need backward traversal or
O(1) deletion of arbitrary nodes you already reference - classic cases are deques (double-ended queues) and LRU caches, where entries are moved and evicted from both ends frequently.Why can a doubly linked list delete a node in O(1)?
To remove a node you must connect its predecessor to its successor. In a singly linked list you'd have to walk from the head to find the predecessor (
O(n)); in a doubly linked list the node's prev pointer gives you the predecessor directly, so the relinking is O(1).Doubly linked list vs array: which should I use?
Use an array when you need
O(1) access by index and cache-friendly iteration, and when insertions mostly happen at the end. Use a doubly linked list when you frequently insert or remove in the middle or at both ends given a node reference, since that is O(1) versus an array's O(n) shift. Arrays win on memory and locality; the list wins on structural edits.What is a sentinel node in a doubly linked list?
A sentinel (or dummy) node is a placeholder that sits before the head and/or after the tail so the list is never truly empty. It removes the
null checks for head, tail, and boundary inserts/deletes, letting every operation follow the same relinking code path. Many production LRU-cache implementations use two sentinels to avoid special-casing the ends.What is the most common bug when deleting from a doubly linked list?
Forgetting to update
head or tail when you delete the first or last node, which leaves a dangling pointer to a freed node. Always check whether node.prev is null (update head) or node.next is null (update tail) before rewiring the neighbors.Related resources
More visualizations
