Intro
Last time, we learned how to shift / remove data from the beginning of our Doubly Linked List.
Today, we'll learn how to get a specific node by its index.
Starter Code
We start with code that has the push method, because to remove data, we first have 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;
}
}
Thoughts
First, we should think about the constraints and possibilities:
If the list is empty, if the index is less than 0, or if the index is greater than or equal to the list length:
- return null
If the desired node is in the bottom half of the list:
- add counter
- start from the head
- go to the next node until we found our desired node
- return node
If the desired node is in the top half of the list:
- add counter
- start from the tail
- go to the previous node until we found our desired node
- return node
Example:
// current list:
A (head) <===> B <===> C (tail)
// desired node:
get(0); // A (starting from head)
get(1); // B (starting node doesn't matter, equal distance from head or tail)
get(2); // C (starting from tail)
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;
}
get(index) {
// if list is empty, if index is less than 0, or if index is greater than or equal to the list length, return null
if (!this.length || index < 0 || index >= this.length) {
return null;
} else {
let currentNode;
// if the desired node is in the bottom half of the list
if (index < this.length / 2) {
// add counter, starting from 0 and counting upwards in the loop
let counter = 0;
// start from the head
currentNode = this.head;
// go to the next node until we found our desired node
while (counter < index) {
currentNode = currentNode.next;
counter += 1;
}
} else {
// add counter, starting from the top and counting downwards in the loop
let counter = this.length - 1;
// start from the tail
currentNode = this.tail;
// go to the previous node until we found our desired node
while (counter > index) {
currentNode = currentNode.prev;
counter -= 1;
}
}
// return node
return currentNode;
}
}
}
Result
Let's have a look how to use the Doubly Linked List's get method and its results.
const newDLL = new DoublyLinkedList();
newDLL.push("A");
newDLL.push("B");
newDLL.push("C");
// nothing to see
console.log(newDLL.get(-1));
// null
// should be A
console.log(newDLL.get(0));
// <ref *1> Node {
// value: 'A',
// prev: null,
// next: <ref *2> Node {
// value: 'B',
// prev: [Circular *1],
// next: Node { value: 'C', prev: [Circular *2], next: null }
// }
// }
// should be B
console.log(newDLL.get(1));
// <ref *1> Node {
// value: 'B',
// prev: Node { value: 'A', prev: null, next: [Circular *1] },
// next: Node { value: 'C', prev: [Circular *1], next: null }
// }
// should be C
console.log(newDLL.get(2));
// <ref *2> Node {
// value: 'C',
// prev: <ref *1> Node {
// value: 'B',
// prev: Node { value: 'A', prev: null, next: [Circular *1] },
// next: [Circular *2]
// },
// next: null
// }
// nothing to see
console.log(newDLL.get(3));
// null
Next Part
We will implement our next method for the Doubly Linked List: set / update a specific node.
If you want to get notified, subscribe!
Tasks
- Have a look at the
getmethod in the Singly Linked List. What are the differences between the Doubly Linked List and the Singly Linked List? Are there some Pros and Cons?
Top comments (0)