Assumes understanding of Big O notation. Examples are in JavaScript. Information references "Cracking the Coding Interview" by Gayle Laakmann McDowell
Understanding Doubly Linked Lists
A doubly linked list is very similar to a singly linked list, except for the node’s structure and the way we add/remove nodes.
Node Structure
A node in a doubly linked list contains a prev pointer, next pointer, and value. The prev pointer points to the previous node and the next pointer points to the next node. By nature, this list goes both ways at each node.
Adding a Node
To insert a new node (newNode
) at a specific index:
Store the node currently at the insertion index in a temporary variable
nextNode
.-
Update the connections for the previous node and the new node:
- Set the previous node's
next
pointer tonewNode
. - Set
newNode
'sprev
pointer to the previous node.
- Set the previous node's
-
Connect the new node to the next node:
- Set
newNode
'snext
pointer tonextNode
. - Set
nextNode
'sprev
pointer tonewNode
.
- Set
Removing a Node
To remove a node at a specific index:
- Update the previous node's
next
pointer:- Set it to point to the node after the one being removed.
- Update the next node's
prev
pointer:- Set it to point to the node before the one being removed.
This effectively "bridges" the gap created by removing the node, maintaining the list's integrity.
Time Complexity Analysis
Adding/Removing inside the doubly linked list →
Adding/Removing at the head or tail of doubly linked list →
JavaScript Implementation
Classical OOP
class ListNode {
constructor(value, prev = null, next = null) {
this.value = value;
this.prev = prev;
this.next = next;
}
}
class DoublyLinkedList {
constructor() {
this.head = null;
this.tail = null;
this.size = 0;
}
// add a node to the head of the list
addHead(value) {
const newNode = new ListNode(value, null, this.head);
if (this.head) {
this.head.prev = newNode;
} else {
this.tail = newNode; // If list was empty, new node is also the tail
}
this.head = newNode;
this.size++;
}
// Add a node to the tail of the list
addTail(value) {
const newNode = new ListNode(value, this.tail, null);
if (this.tail) {
this.tail.next = newNode;
} else {
this.head = newNode; // If list was empty, new node is also the head
}
this.tail = newNode;
this.size++;
}
// Remove a node from the head of the list
removeHead() {
if (!this.head) return null; // List is empty
const removedValue = this.head.value;
this.head = this.head.next;
if (this.head) {
this.head.prev = null;
} else {
this.tail = null; // List became empty
}
this.size--;
return removedValue;
}
// Remove a node from the tail of the list
removeTail() {
if (!this.tail) return null; // List is empty
const removedValue = this.tail.value;
this.tail = this.tail.prev;
if (this.tail) {
this.tail.next = null;
} else {
this.head = null; // List became empty
}
this.size--;
return removedValue;
}
// Remove a node at a specific index
removeAt(index) {
if (index < 0 || index >= this.size) return null;
let current;
if (index < this.size / 2) {
current = this.head;
for (let i = 0; i < index; i++) {
current = current.next;
}
} else {
current = this.tail;
for (let i = this.size - 1; i > index; i--) {
current = current.prev;
}
}
if (current.prev) current.prev.next = current.next;
if (current.next) current.next.prev = current.prev;
if (index === 0) this.head = current.next;
if (index === this.size - 1) this.tail = current.prev;
this.size--;
return current.value;
}
// Get the size of the list
getSize() {
return this.size;
}
// Get the values in the list
getValues() {
const values = [];
let current = this.head;
while (current) {
values.push(current.value);
current = current.next;
}
return values;
}
}
Prototype-based OOP
function ListNode(value, prev = null, next = null) {
this.value = value;
this.prev = prev;
this.next = next;
}
function DoublyLinkedList() {
this.head = null;
this.tail = null;
this.size = 0;
}
// Add a node to the head of the list
DoublyLinkedList.prototype.addHead = function(value) {
const newNode = new ListNode(value, null, this.head);
if (this.head) {
this.head.prev = newNode;
} else {
this.tail = newNode;
}
this.head = newNode;
this.size++;
};
// Add a node to the tail of the list
DoublyLinkedList.prototype.addTail = function(value) {
const newNode = new ListNode(value, this.tail, null);
if (this.tail) {
this.tail.next = newNode;
} else {
this.head = newNode;
}
this.tail = newNode;
this.size++;
};
// Remove a node from the head of the list
DoublyLinkedList.prototype.removeHead = function() {
if (!this.head) return null;
const removedValue = this.head.value;
this.head = this.head.next;
if (this.head) {
this.head.prev = null;
} else {
this.tail = null;
}
this.size--;
return removedValue;
};
// Remove a node from the tail of the list
DoublyLinkedList.prototype.removeTail = function() {
if (!this.tail) return null;
const removedValue = this.tail.value;
this.tail = this.tail.prev;
if (this.tail) {
this.tail.next = null;
} else {
this.head = null;
}
this.size--;
return removedValue;
};
// Remove a node at a specific index
DoublyLinkedList.prototype.removeAt = function(index) {
if (index < 0 || index >= this.size) return null;
let current;
if (index < this.size / 2) {
current = this.head;
for (let i = 0; i < index; i++) {
current = current.next;
}
} else {
current = this.tail;
for (let i = this.size - 1; i > index; i--) {
current = current.prev;
}
}
if (current.prev) current.prev.next = current.next;
if (current.next) current.next.prev = current.prev;
if (index === 0) this.head = current.next;
if (index === this.size - 1) this.tail = current.prev;
this.size--;
return current.value;
};
// Get the size of the list
DoublyLinkedList.prototype.getSize = function() {
return this.size;
};
// Get the values in the list
DoublyLinkedList.prototype.getValues = function() {
const values = [];
let current = this.head;
while (current) {
values.push(current.value);
current = current.next;
}
return values;
};
Top comments (0)