Intro
Last time, we learned how to update a specific node.
Today, we'll learn how to insert a new node at a specific index.
Starter Code
We start with code that has the push, unshift and get method,
because we can reuse them to add data.
class Node {
constructor(value) {
this.value = value;
this.prev = null;
this.next = null;
}
}
class DoublyLinkedList {
constructor() {
this.length = 0;
this.head = null;
this.tail = null;
}
push(value) {
const newNode = new Node(value);
if (!this.length) {
this.head = newNode;
this.tail = newNode;
} else {
this.tail.next = newNode;
newNode.prev = this.tail;
this.tail = newNode;
}
this.length += 1;
return newNode;
}
unshift(value) {
const newNode = new Node(value);
if (!this.length) {
this.head = newNode;
this.tail = newNode;
} else {
newNode.next = this.head;
this.head.prev = newNode;
this.head = newNode;
}
this.length += 1;
return newNode;
}
get(index) {
if (!this.length || index < 0 || index >= this.length) {
return null;
} else {
let currentNode;
if (index < this.length / 2) {
let counter = 0;
currentNode = this.head;
while (counter < index) {
currentNode = currentNode.next;
counter += 1;
}
} else {
let counter = this.length - 1;
currentNode = this.tail;
while (counter > index) {
currentNode = currentNode.prev;
counter -= 1;
}
}
return currentNode;
}
}
}
Thoughts
First, we should think about the constraints and possibilities:
If the index is less than 0:
- return null
If the index is greater than the list's length:
- return null
If the index equals 0:
- use the
unshiftmethod to add the data
If the index equals length:
- use the
pushmethod to add the data
All remaining cases:
- create a new node
- find the node that is currently before the desired place and connect it to the new node
- find the node that is currently at the desired place and connect it to the new node
- increase the list's length by 1
- return the new node
Example
// current list:
A <===> B
// desired list:
A <===> X <===> B
Steps:
// current list:
A <===> B
// find the node that is currently before the desired place and connect it to the new node
// there is still the connection from B.prev to A
A <===> X
A <== B
// find the node that is currently at the desired place and connect it to the new node
A <===> X <===> B
// desired list:
A <===> X <===> B
=> list after last step equals the desired list
Implementation (Short)
class Node {
constructor(value) {
this.value = value;
this.prev = null;
this.next = null;
}
}
class DoublyLinkedList {
constructor() {
this.length = 0;
this.head = null;
this.tail = null;
}
push(value) {
const newNode = new Node(value);
if (!this.length) {
this.head = newNode;
this.tail = newNode;
} else {
this.tail.next = newNode;
newNode.prev = this.tail;
this.tail = newNode;
}
this.length += 1;
return newNode;
}
unshift(value) {
const newNode = new Node(value);
if (!this.length) {
this.head = newNode;
this.tail = newNode;
} else {
newNode.next = this.head;
this.head.prev = newNode;
this.head = newNode;
}
this.length += 1;
return newNode;
}
get(index) {
if (!this.length || index < 0 || index >= this.length) {
return null;
} else {
let currentNode;
if (index < this.length / 2) {
let counter = 0;
currentNode = this.head;
while (counter < index) {
currentNode = currentNode.next;
counter += 1;
}
} else {
let counter = this.length - 1;
currentNode = this.tail;
while (counter > index) {
currentNode = currentNode.prev;
counter -= 1;
}
}
return currentNode;
}
}
insert(index, value) {
// if the index is less than 0 or greater than the list's length, return null
if (index < 0 || index > this.length) {
return null;
} else if (index === 0) {
// if the index equals 0, use the `unshift` method
return this.unshift(value);
} else if (index === this.length) {
// if the index equals length, use the `push` method
return this.push(value);
} else {
// create new node
const newNode = new Node(value);
// find the new previous node
const newPrevNode = this.get(index - 1);
// find the new next node
const newNextNode = newPrevNode.next;
// connect the new node to the new previous node
newNode.prev = newPrevNode;
newPrevNode.next = newNode;
// connect the new node to the new next node
newNode.next = newNextNode;
newNextNode.prev = newNode;
// increase the list's length by 1
this.length += 1;
// return the new node
return newNode;
}
}
}
Result
Let's have a look how to use the Doubly Linked List's insert method and its results.
const newDLL = new DoublyLinkedList();
// index too low
console.log(newDLL.insert(-1, "too low"));
// null
// shoould display the new node
console.log(newDLL.insert(0, "at 0"));
// Node { value: 'at 0', prev: null, next: null }
// shoould display the new node
console.log(newDLL.insert(1, "at 1"));
// <ref *1> Node {
// value: 'at 1',
// prev: Node { value: 'at 0', prev: null, next: [Circular *1] },
// next: null
// }
// should insert the node between the other two nodes
console.log(newDLL.insert(1, "new at 1"));
// <ref *1> Node {
// value: 'new at 1',
// prev: Node { value: 'at 0', prev: null, next: [Circular *1] },
// next: Node { value: 'at 1', prev: [Circular *1], next: null }
// }
// should show three nodes in the list: at 0 => new at 1 => at 1
console.log(newDLL);
// DoublyLinkedList {
// length: 3,
// head: <ref *1> Node {
// value: 'at 0',
// prev: null,
// next: Node { value: 'new at 1', prev: [Circular *1], next: [Node] }
// },
// tail: <ref *2> Node {
// value: 'at 1',
// prev: Node { value: 'new at 1', prev: [Node], next: [Circular *2] },
// next: null
// }
// }
Next Part
We will implement our next method for the Doubly Linked List: remove a specific node.
If you want to get notified, subscribe!
Top comments (0)