TypeScript: Implement a Doubly Linked List

1. Introduction

A Doubly Linked List (DLL) is a type of linked list in which each node contains a data part and two pointers. The two pointers are:

1. A pointer to the next node in the sequence (next pointer).

2. A pointer to the previous node in the sequence (previous pointer).

This allows for bidirectional traversal, which can be more versatile than a singly linked list, at the cost of slightly increased complexity.

2. Program Overview

Our TypeScript program will implement a basic Doubly Linked List. The primary operations covered include adding a node at the end, deleting a node, and displaying the list.

3. Code Program

class Node {
    data: number;
    next: Node | null;
    prev: Node | null;

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

class DoublyLinkedList {
    private head: Node | null;
    private tail: Node | null;

    constructor() {
        this.head = null;
        this.tail = null;
    }

    // Add a node to the end of the list
    append(data: number): void {
        const newNode = new Node(data);

        if (!this.head) {
            this.head = newNode;
            this.tail = newNode;
        } else {
            this.tail!.next = newNode;
            newNode.prev = this.tail;
            this.tail = newNode;
        }
    }

    // Delete a node from the list by its value
    delete(data: number): void {
        let current = this.head;

        while (current) {
            if (current.data === data) {
                if (current.prev) {
                    current.prev.next = current.next;
                } else {
                    this.head = current.next;
                }

                if (current.next) {
                    current.next.prev = current.prev;
                } else {
                    this.tail = current.prev;
                }
                return;
            }
            current = current.next;
        }
    }

    // Display the list elements
    display(): void {
        let current = this.head;

        while (current) {
            console.log(current.data);
            current = current.next;
        }
    }
}

// Test the Doubly Linked List
const dll = new DoublyLinkedList();
dll.append(10);
dll.append(20);
dll.append(30);
dll.display();
dll.delete(20);
dll.display();

4. Step By Step Explanation

1. The Node class:

• This represents an individual node in the DLL.b. Each node has a data part, a next pointer to point to the next node, and a prev pointer to point to the previous node.

2. The DoublyLinkedList class:

a. Contains a head pointer to the first node and a tail pointer to the last node.

b. The append method is used to add nodes to the end of the list.

• If the list is empty, both the head and tail point to the new node.
• If not, the new node is attached to the end, and the tail pointer is updated.

c. The delete method removes a node with the given data value.

• It traverses the list, and when the node with the matching data is found, it adjusts the pointers of the previous and next nodes to exclude the current node from the list.
• If the node to be deleted is the head or tail, the head or tail pointer is updated accordingly.

d. The display method is used to print the data values of all nodes, starting from the head and moving to the tail.