Algorithms and Data Structures in TypeScript: A Practical Guide

Algorithms and Data Structures in TypeScript: In Practice

TypeScript is not just a superset of JavaScript. Thanks to strict typing and modern capabilities, TypeScript is ideal for implementing complex algorithms and data structures. In this article, we will break down key data structures and algorithms with practical examples in TypeScript. You will learn how to implement a stack, queue, linked list, hash table, and also master binary search and sorting algorithms.

1. Stack and Queue: Fundamental Data Structures

Stack and queue are basic structures used everywhere: from processing function calls to managing tasks in the browser.

Stack — LIFO (Last In, First Out)

The stack works on the principle of "last in, first out". Let's implement it using an array and TypeScript generics:

class Stack<T> {    private items: T[] = [];

    push(item: T): void {        this.items.push(item);    }

    pop(): T | undefined {        return this.items.pop();    }

    peek(): T | undefined {        return this.items[this.items.length - 1];    }

    isEmpty(): boolean {        return this.items.length === 0;    }

    size(): number {        return this.items.length;    }}

// Usage exampleconst numberStack = new Stack<number>();numberStack.push(10);numberStack.push(20);console.log(numberStack.pop()); // 20console.log(numberStack.peek()); // 10

Queue — FIFO (First In, First Out)

The queue works on the principle of "first in, first out". Implementation in TypeScript:

class Queue<T> {    private items: T[] = [];

    enqueue(item: T): void {        this.items.push(item);    }

    dequeue(): T | undefined {        return this.items.shift();    }

    front(): T | undefined {        return this.items[0];    }

    isEmpty(): boolean {        return this.items.length === 0;    }

    size(): number {        return this.items.length;    }}

// Usage exampleconst stringQueue = new Queue<string>();stringQueue.enqueue('A');stringQueue.enqueue('B');console.log(stringQueue.dequeue()); // 'A'console.log(stringQueue.front());   // 'B'

Important: The shift() operation in JavaScript has O(n) complexity because it shifts all elements. For a more performant queue, use a linked list or a circular buffer.

2. Linked List

A linked list is a sequence of nodes, where each node stores data and a reference to the next node. In TypeScript, we can use interfaces for strict typing.

interface ListNode<T> {    value: T;    next: ListNode<T> | null;}

class LinkedList<T> {    private head: ListNode<T> | null = null;

    append(value: T): void {        const newNode: ListNode<T> = { value, next: null };        if (!this.head) {            this.head = newNode;            return;        }        let current = this.head;        while (current.next) {            current = current.next;        }        current.next = newNode;    }

    prepend(value: T): void {        const newNode: ListNode<T> = { value, next: this.head };        this.head = newNode;    }

    delete(value: T): void {        if (!this.head) return;        if (this.head.value === value) {            this.head = this.head.next;            return;        }        let current = this.head;        while (current.next) {            if (current.next.value === value) {                current.next = current.next.next;                return;            }            current = current.next;        }    }

    print(): void {        let current = this.head;        const values: T[] = [];