Doubly Linked List
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147
type DLLNode = {
value: number;
next: DLLNode | null;
prev: DLLNode | null;
};
class DoublyLinkedList {
private head: DLLNode;
private tail: DLLNode;
private length;
constructor(value: number) {
this.head = this.newNode(value);
this.tail = this.head;
this.length = 1;
}
newNode(value): DLLNode {
return {
value,
next: null,
prev: null
}
}
append(value: number) {
const newNode: DLLNode = this.newNode(value);
newNode.prev = this.tail;
this.tail.next = newNode;
this.tail = newNode;
this.length++;
return this;
}
prepend(value: number) {
const newNode = this.newNode(value);
newNode.next = this.head;
this.head.prev = newNode;
this.head = newNode;
this.length++;
return this;
}
printList() {
const arr = [];
let currNode = this.head;
while (currNode !== null) {
arr.push(currNode.value);
currNode = currNode.next;
}
console.log('List length: ', this.length);
return arr;
}
insert(index: number, value: number) {
// check params
if (index === 0) {
return this.prepend(value);
}
if (index >= this.length) {
return this.append(value);
}
const preNode = this.traverseToIndex(index - 1);
const aftNode = preNode.next;
let newNode = this.newNode(value);
preNode.next = newNode;
newNode.prev = preNode;
newNode.next = aftNode;
aftNode.prev = newNode;
this.length++;
return this;
}
traverseToIndex(index: number) {
let preNode = this.head;
// we need the node before the given index
for (let k = 0; k < index; k++) {
preNode = preNode.next;
}
return preNode;
}
remove(index) {
// check params
const preNode = this.traverseToIndex(index - 1);
const currNode = preNode.next;
const aftNode = currNode.next;
currNode.next = null;
currNode.prev = null;
preNode.next = aftNode;
aftNode.prev = preNode;
this.length--;
return this;
}
}
// 10 --> 5 --> 16 --> 20
/**
let myLinkedList = {
head: {
value: 10,
next: {
value: 5,
next: {
value: 16,
next: null
}
}
}
}
*/
const myLinkedList = new DoublyLinkedList(10);
myLinkedList.append(5);
myLinkedList.append(16);
myLinkedList.append(20);
myLinkedList.prepend(1);
myLinkedList.prepend(3);
myLinkedList.insert(2, 55);
myLinkedList.insert(0, 33);
myLinkedList.insert(42, 88);
// console.log(myLinkedList);
console.log(myLinkedList.printList());
myLinkedList.remove(3);
console.log(myLinkedList.printList());
TypeScript
INFO