Module
x/datastructure/linkedList/doubly/doublyLinkedList.ts
Implement different Data Structures using TypeScript. Deno Third-party Module.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206import { LinkedListApi, NodeType, DataType } from "./helper.d.ts";import { DoublyNode } from "./doublyNode.ts";import { addGenerator, updateGenerator, searchGenerator, iteratorGenerator} from "./generators.ts"
export class DoublyLinkedList implements LinkedListApi { #head: null|NodeType #tail: null|NodeType public size: number
constructor() { this.#head = null this.#tail = null this.size = 0 }
static createDL() { return new this(); }
// insert in the head prepend(data: DataType<any>) { const newNode = new DoublyNode(data); if (this.#head === null) { this.#head = newNode this.#tail = newNode return true; }
const currentNode = this.#head this.#head = newNode this.#head.next = currentNode currentNode.prev = newNode
this.size++ return true; }
// inset in the tail append(data: DataType<any>) { const newNode = new DoublyNode(data); if (this.#head === null) { this.#head = newNode this.#tail = newNode return true; }
const currentNode = this.#tail this.#tail!.next = newNode this.#tail = newNode this.#tail.prev = currentNode this.size++
return false; }
// // add anywhere of the linked list except head & tail add(data: DataType<any>, position: number) { if (position === 0) { console.error("Use `prepend()` method to insert data at Head."); return false; } else if (position === this.size) { console.error("Use `append()` method to insert data at Tail."); return false; } else if (position > this.size && position != this.size + 1) { console.error(`Out of range. Size of the linkedList is ${this.size}`); return false; } // generator function that returns an iterator const iterator = addGenerator(this.#head, data, position) const iteratorNext = iterator.next() if (iteratorNext.value) { this.size++ return true }
return false; }
getFromHead() { if (this.#head === null) { return false }
return this.#head.data; }
getFromTail() { if (this.#tail === null) { return false }
return this.#tail.data }
log() { let currentNode = this.#head while (currentNode !== null) { console.log(currentNode.data); currentNode = currentNode.next } }
remove(key: string|number) { if (this.#head === null) { return false; } if (this.#head.data.key === key) { const prevHeadData = this.#head.data this.#head = this.#head.next if (this.#head === null) this.#tail = this.#head
this.size-- if (this.#head === null) this.size = 0 return prevHeadData; } if (this.#tail!.data.key === key) { const prevTailData = this.#tail!.data this.#tail = this.#tail!.prev this.#tail!.next = null return prevTailData; }
// two pointer approach let previousNode: NodeType = null; let currentNode: NodeType = this.#head while (currentNode !== null) { if (key === currentNode.data.key) { const temp = currentNode.data previousNode!.next = currentNode.next currentNode.next!.prev = previousNode if (currentNode!.next === null) this.#tail = previousNode
this.size-- return temp; }
previousNode = currentNode currentNode = currentNode.next }
return false; }
update(key: string|number, newValue: any) { if (this.#head === null) { return false; }
if (this.#head.data.key === key) { this.#head.data.value = newValue return this.#head.data; } if (this.#tail!.data.key === key) { this.#tail!.data.value = newValue return this.#tail!.data; }
// generator function that returns an iterator const iterator = updateGenerator(key, this.#head, newValue) const iteratorNext = iterator.next() if (iteratorNext.value) { this.size++ return iteratorNext.value }
return false; }
search(key: string|number) { if (this.#head === null) { return false; }
if (this.#head.data.key === key) { return this.#head.data; } if (this.#tail!.data.key === key) { return this.#tail!.data }
// generator function that returns an iterator const iterator = searchGenerator(key, this.#head) const iteratorNext = iterator.next() if (iteratorNext.value) { this.size++ return iteratorNext.value }
return false; }
iterator() { // generator function that returns an iterator const iterator = iteratorGenerator(this.#head) return iterator }}