Algorithms and Data Structures in JavaScript: A Practical Guide

Algorithms and Data Structures in JavaScript: From Theory to Practice

The ability to work with algorithms and data structures is a key skill for any developer, regardless of the programming language. JavaScript (especially in the Node.js environment) is no exception. In this article, we will break down fundamental data structures and classic algorithms, implementing them in pure JavaScript. You will see how stacks, queues, linked lists, trees, and sorting/searching algorithms are applied in real-world backend development tasks on Node.js.

1. Stack and Queue: Basic Structures for Data Management

Stack and Queue are linear data structures that differ in the rules for adding and removing elements. A stack operates on the LIFO (Last In, First Out) principle, while a queue operates on FIFO (First In, First Out).

Implementing a Stack in JavaScript

In JavaScript, a stack can be implemented using an array or a linked list. Let's look at a simple array-based version:

class Stack {\n    constructor() {\n        this.items = [];\n    }\n\n    push(element) {\n        this.items.push(element);\n    }\n\n    pop() {\n        if (this.isEmpty()) return null;\n        return this.items.pop();\n    }\n\n    peek() {\n        if (this.isEmpty()) return null;\n        return this.items[this.items.length - 1];\n    }\n\n    isEmpty() {\n        return this.items.length === 0;\n    }\n\n    size() {\n        return this.items.length;\n    }\n}\n\n// Example usage\nconst stack = new Stack();\nstack.push('A');\nstack.push('B');\nstack.push('C');\nconsole.log(stack.pop());  // 'C'\nconsole.log(stack.peek()); // 'B'

Stacks are often used for checking balanced parentheses, implementing the "Back" button in a browser, or for depth-first tree traversal.

Implementing a Queue in JavaScript

A queue can also be built on an array, but for better performance (avoiding re-indexing with shift) we use a linked list or two stacks. Here is a simple array-based implementation:

class Queue {\n    constructor() {\n        this.items = [];\n    }\n\n    enqueue(element) {\n        this.items.push(element);\n    }\n\n    dequeue() {\n        if (this.isEmpty()) return null;\n        return this.items.shift();\n    }\n\n    front() {\n        if (this.isEmpty()) return null;\n        return this.items[0];\n    }\n\n    isEmpty() {\n        return this.items.length === 0;\n    }\n\n    size() {\n        return this.items.length;\n    }\n}\n\n// Example usage\nconst queue = new Queue();\nqueue.enqueue(1);\nqueue.enqueue(2);\nqueue.enqueue(3);\nconsole.log(queue.dequeue()); // 1\nconsole.log(queue.front());   // 2

Queues are used in task management systems, BFS (breadth-first search) algorithms, and for data buffering in Node.js (e.g., streams).

2. Linked List: A Dynamic Structure for Frequent Insertions

A Linked List is a sequence of nodes, each containing data and a reference to the next node. Unlike an array, inserting and deleting elements in the middle of the list is done in O(1) time if you have a reference to the node.

Implementing a Singly Linked List

class ListNode {\n    constructor(value, next = null) {\n        this.value = value;\n        this.next = next;\n    }\n}\n\nclass LinkedList {\n    constructor() {\n        this.head = null;\n        this.tail = null;\n        this.length = 0;\n    }\n\n    append(value) {\n        const newNode = new ListNode(value);\n        if (!this.head) {\n            this.head = newNode;\n            this.tail = newNode;\n        } else {\n            this.tail.next = newNode;\n            this.tail = newNode;\n        }\n        this.length++;\n        return this;\n    }\n\n    prepend(value) {\n        const newNode = new ListNode(value, this.head);\n        this.head = newNode;\n        if (!this.tail) this.tail = newNode;\n