Algorithms and Data Structures in TypeScript: A Practical Guide

Algorithms and Data Structures in TypeScript: From Theory to Practice

Understanding algorithms and data structures is the foundation that distinguishes an experienced developer from a beginner. TypeScript, thanks to its strict typing and modern capabilities, allows you to write reliable and readable code for solving classic problems. In this article, we will break down key data structures and algorithms using practical examples with TypeScript. You will learn how to implement a stack, queue, binary search, and quick sort, and also get acquainted with the basics of working with graphs.

1. Basic Data Structures: Stack and Queue

Stack and queue are the simplest yet extremely useful structures. A stack operates on the LIFO (Last In, First Out) principle, while a queue operates on FIFO (First In, First Out). In TypeScript, they are conveniently implemented based on an array using generics for type safety.

Stack Implementation

class Stack<T> {\n    private items: T[] = [];\n\n    push(item: T): void {\n        this.items.push(item);\n    }\n\n    pop(): T | undefined {\n        return this.items.pop();\n    }\n\n    peek(): T | undefined {\n        return this.items[this.items.length - 1];\n    }\n\n    isEmpty(): boolean {\n        return this.items.length === 0;\n    }\n\n    size(): number {\n        return this.items.length;\n    }\n}\n\n// Example usage\nconst stack = new Stack<number>();\nstack.push(10);\nstack.push(20);\nconsole.log(stack.pop()); // 20\nconsole.log(stack.peek()); // 10

Queue Implementation

class Queue<T> {\n    private items: T[] = [];\n\n    enqueue(item: T): void {\n        this.items.push(item);\n    }\n\n    dequeue(): T | undefined {\n        return this.items.shift();\n    }\n\n    front(): T | undefined {\n        return this.items[0];\n    }\n\n    isEmpty(): boolean {\n        return this.items.length === 0;\n    }\n\n    size(): number {\n        return this.items.length;\n    }\n}\n\n// Example usage\nconst queue = new Queue<string>();\nqueue.enqueue('A');\nqueue.enqueue('B');\nconsole.log(queue.dequeue()); // A\nconsole.log(queue.front()); // B

Note: the built-in shift() method has O(n) complexity, so for large amounts of data it is better to implement a queue based on a linked list.

2. Search Algorithms: Linear and Binary

Searching for elements is one of the most common operations. Linear search is simple but slow on large data. Binary search works in O(log n) time but requires a sorted array.

Linear Search

function linearSearch<T>(arr: T[], target: T): number {\n    for (let i = 0; i < arr.length; i++) {\n        if (arr[i] === target) {\n            return i;\n        }\n    }\n    return -1;\n}\n\nconst numbers = [3, 7, 1, 9, 4];\nconsole.log(linearSearch(numbers, 9)); // 3

Binary Search (Recursive Version)

function binarySearch<T>(arr: T[], target: T, left: number = 0, right: number = arr.length - 1): number {\n    if (left > right) {\n        return -1;\n    }\n\n    const mid = Math.floor((left + right) / 2);\n\n    if (arr[mid] === target) {\n        return mid;\n    }\n\n    if (arr[mid] > target) {\n        return binarySearch(arr, target, left, mid - 1);\n    } else {\n        return binarySearch(arr, target, mid + 1, right);\n    }\n}\n\nconst sortedArray = [1, 3, 5, 7, 9, 11];\nconsole.log(binarySearch(sortedArray, 7)); // 3\nconsole.log(binarySearch(sortedArray, 6)); // -1

For an iterative version, use a while loop. TypeScript helps avoid type-related errors: the generic <T> ensures that the array and the target element are of the same type.

3. Sorting: Quick Sort

Quick sort is one of the most efficient algorithms with an average complexity of O(n log n). R