## DEV Community

Terrence Jung

Posted on • Updated on

# Implementing a Doubly Linked List

Assumes understanding of Big O notation. Examples are in JavaScript. Information references "Cracking the Coding Interview" by Gayle Laakmann McDowell

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.

To insert a new node (newNode) at a specific index:

1. Store the node currently at the insertion index in a temporary variable nextNode.

2. Update the connections for the previous node and the new node:

• Set the previous node's next pointer to newNode.
• Set newNode's prev pointer to the previous node.
3. Connect the new node to the next node:

• Set newNode's next pointer to nextNode.
• Set nextNode's prev pointer to newNode.

## Removing a Node

To remove a node at a specific index:

1. Update the previous node's next pointer:
• Set it to point to the node after the one being removed.
2. 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 → $O(n)$

• Adding/Removing at the head or tail of doubly linked list → $O(1)$

## JavaScript Implementation

### Classical OOP

class ListNode {
constructor(value, prev = null, next = null) {
this.value = value;
this.prev = prev;
this.next = next;
}
}

constructor() {
this.tail = null;
this.size = 0;
}

const newNode = new ListNode(value, null, this.head);
} else {
this.tail = newNode; // If list was empty, new node is also the tail
}
this.size++;
}

// Add a node to the tail of the list
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
if (!this.head) return null; // List is empty
} 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) {
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 = [];
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;
}

this.tail = null;
this.size = 0;
}

const newNode = new ListNode(value, null, this.head);
} else {
this.tail = newNode;
}
this.size++;
};

// Add a node to the tail of the list
const newNode = new ListNode(value, this.tail, null);
if (this.tail) {
this.tail.next = newNode;
} else {
}
this.tail = newNode;
this.size++;
};

// Remove a node from the head of the list
} else {
this.tail = null;
}
this.size--;
return removedValue;
};

// Remove a node from the tail of the list
if (!this.tail) return null;
const removedValue = this.tail.value;
this.tail = this.tail.prev;
if (this.tail) {
this.tail.next = null;
} else {
}
this.size--;
return removedValue;
};

// Remove a node at a specific index
if (index < 0 || index >= this.size) return null;
let current;
if (index < this.size / 2) {
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
return this.size;
};

// Get the values in the list