How to Implement DoublyLinkedList in TypeScript

DoublyLinkedList is a data structure that contains a head, tail and length property. Linked Lists consist of nodes, and each node has a value and a pointer to another node or null.

The DoublyLinkedList is an extension of LinkedList. It has two pointers, one to the first element of the list and another to the last element of the list.

Following are some methods used in DoublyLinkedList:

InsertAtHead(): Inserts an element at the beginning of a DoublyLinkedList.

 insertAtHead(data: number) {
        const newNode = new Node(data);
        if (this.head === null) {
            this.head = newNode;
            this.tail = newNode;
        } else {
            this.head.prev = newNode;
            newNode.next = this.head;
            this.head = newNode;
        }
        this.length++;
    }
    ```

`InsertAtTail()`: Inserts an element at the end of a `DoublyLinkedList`.

```js
 insertAtTail(data: number) {
        const newNode = new Node(data);
        if (this.head === null) {
            this.head = newNode;
            this.tail = newNode;
        } else {
            newNode.prev = this.tail;
            this.tail.next = newNode;
            this.tail = newNode;
        }
        this.length++;
    }

InsertAtIndex(): Inserts an element at index n in a DoublyLinkedList.

 insertAtIndex(data: number, index: number) {
        if (index === 0) {
            this.insertAtHead(data);
            return;
        }
        if (index >= this.length) {
            this.insertAtTail(data);
            return;
        }
        const newNode = new Node(data);
        let currentNode = this.head;
        let currentIndex = 0;
        while (currentIndex !== index) {
            currentNode = currentNode.next;
            currentIndex++;
        }
        newNode.next = currentNode;
        newNode.prev = currentNode.prev;
        currentNode.prev.next = newNode;
        currentNode.prev = newNode;
        this.length++;
       
    }

DeleteAtHead(): Removes and returns the head node of this DoublyLinkedList.

 deleteAtHead() {
        if (this.head === null) {
            return null;
        }
        if (this.head === this.tail) {
            this.head = null;
            this.tail = null;
            this.length--;
            return;
        }
        this.head = this.head.next;
        this.head.prev = null;
        this.length--;
    }

DeleteAtTail(): Removes and returns the tail node of this DoublyLinkedList.

  deleteAtTail() {
        if (this.head === null) {
            return null;
        }
        if (this.head === this.tail) {
            this.head = null;
            this.tail = null;
            this.length--;
            return;
        }
        this.tail = this.tail.prev;
        this.tail.next = null;
        this.length--;
    }

Search(): Searches for a specified value within this DoublyLinkedList and returns its index if found; otherwise, returns -1

  search(data: number) {
        let currentNode = this.head;
        while (currentNode !== null) {
            if (currentNode.data === data) {
                return currentNode;
            }
            currentNode = currentNode.next;
        }
        return null;
    }

printList: This function prints the

   printList(){
        let currentNode = this.head;
        let list = [];
        while (currentNode !== null) {
            list.push(currentNode.data);
            currentNode = currentNode.next;
        }
        return list;
    }

Time Complexity

• insertAtHead: O(1)
• insertAtTail: O(1)
• insertAtIndex: O(n)
• deleteAtHead: O(1)
• deleteAtTail: O(1)
• deleteAtIndex: O(n)
• search: O(n)
• printList: O(n)

Complete Source Code Of DoublyLinkedList

Below is the complete source code

class Node {
    data: number;
    next: Node;
    prev: Node;
    constructor(data: number) {
        this.data = data;
        this.next = null;
        this.prev = null;
    }
    }

class DoublyLinkedList {
    head: Node;
    tail: Node;
    length: number;
    constructor() {
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
    insertAtHead(data: number) {
        const newNode = new Node(data);
        if (this.head === null) {
            this.head = newNode;
            this.tail = newNode;
        } else {
            this.head.prev = newNode;
            newNode.next = this.head;
            this.head = newNode;
        }
        this.length++;
    }
    insertAtTail(data: number) {
        const newNode = new Node(data);
        if (this.head === null) {
            this.head = newNode;
            this.tail = newNode;
        } else {
            newNode.prev = this.tail;
            this.tail.next = newNode;
            this.tail = newNode;
        }
        this.length++;
    }
    insertAtIndex(data: number, index: number) {
        if (index === 0) {
            this.insertAtHead(data);
            return;
        }
        if (index >= this.length) {
            this.insertAtTail(data);
            return;
        }
        const newNode = new Node(data);
        let currentNode = this.head;
        let currentIndex = 0;
        while (currentIndex !== index) {
            currentNode = currentNode.next;
            currentIndex++;
        }
        newNode.next = currentNode;
        newNode.prev = currentNode.prev;
        currentNode.prev.next = newNode;
        currentNode.prev = newNode;
        this.length++;
       
    }
   
    deleteAtTail() {
        if (this.head === null) {
            return null;
        }
        if (this.head === this.tail) {
            this.head = null;
            this.tail = null;
            this.length--;
            return;
        }
        this.tail = this.tail.prev;
        this.tail.next = null;
        this.length--;
    }
   search(data: number) {
        let currentNode = this.head;
        while (currentNode !== null) {
            if (currentNode.data === data) {
                return currentNode;
            }
            currentNode = currentNode.next;
        }
        return null;
    }
    printList(){
        let currentNode = this.head;
        let list = [];
        while (currentNode !== null) {
            list.push(currentNode.data);
            currentNode = currentNode.next;
        }
        return list;
    }
}

const myDoublyLinkedList = new DoublyLinkedList();
myDoublyLinkedList.insertAtHead(10);
myDoublyLinkedList.insertAtHead(20);
myDoublyLinkedList.insertAtHead(30);
myDoublyLinkedList.insertAtTail(40);
myDoublyLinkedList.insertAtTail(50);
myDoublyLinkedList.insertAtTail(60);
myDoublyLinkedList.insertAtIndex(70, 3);
myDoublyLinkedList.deleteAtTail();
console.log(myDoublyLinkedList.printList()); // Output: [30, 20, 10, 70, 40, 50]