Easy difficulty · Algorithm · Topics: linked-list, doubly, insertion, deletion, traversal
A doubly linked list is a chain of nodes where every node knows both its successor (next) and its predecessor (prev). That second pointer lets you walk the list in either direction and unlink a node without hunting for the node before it. This sample keeps both a head and a tail pointer and implements insertion at both ends, insertion after a value, deletion, and forward/backward traversal.
A singly linked list is a one-way street; a doubly linked list is a two-way street. Because each node points back to its neighbour, a node can remove itself: "tell my left neighbour that its right neighbour is now my right neighbour, and tell my right neighbour that its left neighbour is now my left neighbour". The price is one extra pointer per node and twice as many pointers to keep consistent.
The invariant: for every node n, n.next.prev === n and n.prev.next === n, head.prev === null and tail.next === null. Each operation touches up to four pointers and must restore this invariant before returning.
nextprevtailheadprev is the old tail, the old tail's next becomes the new node, and tail moves.target. Link the new node to curr on its left and curr.next on its right, then fix the neighbours: curr.next.prev = node (or tail = node when inserting after the tail) and curr.next = node.curr.prev.next = curr.next, or move head if there is no left neighbour), and make its right neighbour skip it (curr.next.prev = curr.prev, or move tail).head, follow next.tail, follow prev. This is what a singly linked list cannot do.Test case 0, list shown head to tail:
| # | Operation | List after | Returns |
|---|---|---|---|
| 1 | insertTail(2) | 2 (head = tail = 2) | - |
| 2 | insertHead(1) | 1 <-> 2 | - |
| 3 | insertTail(4) | 1 <-> 2 <-> 4 | - |
| 4 | insertAfter(2, 3) | 1 <-> 2 <-> 3 <-> 4 | true |
| 5 | delete(1) | 2 <-> 3 <-> 4 (head moves to 2) | true |
| 6 | delete(4) | 2 <-> 3 (tail moves to 3) | true |
| 7 | toArray() | unchanged | [2, 3] |
| 8 | toArrayReverse() | unchanged | [3, 2] |
In step 4, curr stops at node 2. The new node 3 gets prev = 2 and next = 4; then 4.prev is set to 3 and finally 2.next is set to 3. In step 5 the node 1 has no prev, so the code takes the "deleting the head" branch.
| Operation | Time | Space | Why |
|---|---|---|---|
| insertHead / insertTail | O(1) | O(1) | head and tail give direct access to both ends |
| insertAfter / delete (by value) | O(n) | O(1) | The scan for the value dominates; the relinking is O(1) |
| delete (given the node) | O(1) | O(1) | prev removes the need for a predecessor search |
| toArray / toArrayReverse | O(n) | O(n) | Each node is visited once and copied to the output |
next but forgetting prev) leaves a list that traverses fine forwards and breaks backwards.tail when inserting after the last node or deleting it.curr.next before overwriting it).this.head list: prev arrows are drawn as well as next arrows, so you can check that each pair of neighbours points at each other.curr pointer scanning from the head in insertAfter and delete.this.head and this.tail jumping when the first or last node changes.Input: ops = [insertTail(2), insertHead(1), insertTail(4), insertAfter(2, 3), delete(1), delete(4), toArray(), toArrayReverse()]
Output: [null, null, null, true, true, true, [2, 3], [3, 2]]
class DoublyLinkedList {
constructor() {
this.head = null;
this.tail = null;
}
// Add a node in front of head. O(1).
insertHead(value) {
const node = new DNode(value);
node.next = this.head;
if (this.head !== null) {
this.head.prev = node;
} else {
this.tail = node; // first node is both head and tail
}
this.head = node;
}
// Add a node after tail. O(1) thanks to the tail pointer.
insertTail(value) {
const node = new DNode(value);
node.prev = this.tail;
if (this.tail !== null) {
this.tail.next = node;
} else {
this.head = node;
}
this.tail = node;
}
// Insert a new node right after the first node holding `target`.
insertAfter(target, value) {
let curr = this.head;
while (curr !== null && curr.val !== target) {
curr = curr.next;
}
if (curr === null) return false;
const node = new DNode(value);
node.prev = curr;
node.next = curr.next;
if (curr.next !== null) {
curr.next.prev = node;
} else {
this.tail = node; // inserted after the old tail
}
curr.next = node;
return true;
}
// Unlink the first node holding `value`. Needs no "previous" variable.
delete(value) {
let curr = this.head;
while (curr !== null && curr.val !== value) {
curr = curr.next;
}
if (curr === null) return false;
if (curr.prev !== null) {
curr.prev.next = curr.next;
} else {
this.head = curr.next; // deleting the head
}
if (curr.next !== null) {
curr.next.prev = curr.prev;
} else {
this.tail = curr.prev; // deleting the tail
}
return true;
}
// Forward traversal: head to tail through next.
toArray() {
const values = [];
let curr = this.head;
while (curr !== null) {
values.push(curr.val);
curr = curr.next;
}
return values;
}
// Backward traversal: tail to head through prev.
toArrayReverse() {
const values = [];
let curr = this.tail;
while (curr !== null) {
values.push(curr.val);
curr = curr.prev;
}
return values;
}
}
class DNode {
constructor(val) {
this.val = val;
this.prev = null;
this.next = null;
}
}