TypeScript Data Structures

A collection of data structures implemented in TypeScript.

Introduction

This project provides a set of commonly used data structures implemented in TypeScript. The goal is to provide a robust and efficient implementation of these data structures, making it easy for developers to use them in their projects.

Features

• Linked List: A singly linked list implementation with methods for inserting, deleting, finding, traversing, clearing nodes and more.
• Stack: A stack implementation with methods for pushing, popping, peeking, searching, sorting, cloning, clearing, along with additional operations like finding minimum element, maximum element and more.
• Queue: A queue implementation with methods for enqueueing, dequeueing, peeking at elements and more.
• Tree: A binary search tree implementation with methods for inserting, deleting, searching, traversing nodes, along with additional operations like finding height, minimum element, maximum element and more.
• Other Data Structures: More data structures will be added in the future, including heaps, graphs, segment trees and more.

Installation

To install the TypeScript Data Structures library, run the following command:

npm install @opensource-technologies/typescript-data-structure-library

LinkedList

The LinkedList data structure in this library consists of nodes, where each node contains a value and a reference to the next node in the list. It allows efficient insertion and removal of elements, especially at the beginning or middle of the list.

Available Methods

• append(value: T): void - Append a node to the end of the list.
• prepend(value: T): void - Prepend a node to the start of the list.
• insertAt(value: T, index: number): void - Insert a node at a specific index.
• find(value: T): ListNode<T> | null - Find a node by value.
• remove(value: T): void - Remove a node by value.
• reverse(): void - Reverse the list.
• toArray(): T[] - Convert the list to an array.
• length(): number - Get the length of the list.
• isEmpty(): boolean - Check if the list is empty.
• clear(): void - Clear the list.

Usage

import { LinkedList } from '@opensource-technologies/typescript-data-structure-library';

const list = new LinkedList<number>();

list.append(10);
list.append(20);
list.prepend(5);

console.log(list.toArray()); // Output: [5, 10, 20]
console.log(list.length());  // Output: 3

list.remove(10);
console.log(list.toArray()); // Output: [5, 20]

list.insertAt(15, 1);
console.log(list.toArray()); // Output: [5, 15, 20]

list.reverse();
console.log(list.toArray()); // Output: [20, 15, 5]

console.log(list.isEmpty()); // Output: false
list.clear();
console.log(list.isEmpty()); // Output: true

Stack

The Stack data structure in this library implements the Last-In-First-Out (LIFO) principle, where elements are added and removed from the top of the stack. It is ideal for use cases like backtracking, function call management, and undo functionality.

Available Methods

• push(item: T): void - Push an item onto the stack.
• pop(): T | undefined - Pop an item off the stack.
• peek(): T | undefined - Peek at the top item without removing it.
• isEmpty(): boolean - Check if the stack is empty.
• size(): number - Get the size of the stack.
• search(target: T): boolean - Search for an element in the stack.
• quickSort(): void - Sort the stack using the Quick Sort algorithm.
• mergeSort(): void - Sort the stack using the Merge Sort algorithm.
• getMin(): T - Get the minimum element in the stack
• getMax(): T - Get the maximum element in the stack
• clone(): Stack<T> - Clone the stack
• toArray(): T[] - Convert the stack to an array
• clear(): void - Clear the stack

Example Usage

import { Stack } from '@opensource-technologies/typescript-data-structure-library';

const stack = new Stack<number>();

stack.push(10);
stack.push(20);
stack.push(30);

console.log(stack.peek());  // Output: 30
console.log(stack.pop());   // Output: 30
console.log(stack.size());  // Output: 2
console.log(stack.isEmpty()); // Output: false

stack.push(5);
console.log(stack.getMin()); // Output: 5
console.log(stack.getMax()); // Output: 20

const clonedStack = stack.clone();
console.log(clonedStack.toArray()); // Output: [10, 20, 5]

stack.clear();
console.log(stack.isEmpty()); // Output: true

Queue

The Queue data structure in this library implements the First-In-First-Out (FIFO) principle, where elements are added to the back of the queue and removed from the front. This makes it suitable for scenarios like task scheduling, buffering, and breadth-first traversal.

Available Methods

• push(item: T): void - Adds an item to the back of the queue.
• pop(): T | undefined - Removes and returns the item at the front of the queue.
• peek(): T | undefined - Returns the item at the front of the queue without removing it.
• isEmpty(): boolean - Checks if the queue is empty.
• size(): number - Returns the current number of items in the queue.

Example Usage

import { Queue } from '@opensource-technologies/typescript-data-structure-library';

const queue = new Queue<number>();

queue.push(10);
queue.push(20);
queue.push(30);

console.log(queue.peek()); // Output: 10
console.log(queue.pop());  // Output: 10
console.log(queue.size()); // Output: 2
console.log(queue.isEmpty()); // Output: false

Tree

The Tree data structure in this library is a binary search tree, meaning each node has at most two children. This structure supports a range of operations, including insertion, deletion, traversal, and searching.

Available Methods

• insert(value: T): void - Insert a node with the given value into the tree.
• delete(value: T): void - Delete a node by value from the tree.
• search(value: T): boolean - Search for a node with the given value in the tree.
• preOrderTraversal(): T[] - Perform a pre-order traversal (root, left, right) and return an array of values.
• inOrderTraversal(): T[] - Perform an in-order traversal (left, root, right) and return an array of values.
• postOrderTraversal(): T[] - Perform a post-order traversal (left, right, root) and return an array of values.
• levelOrderTraversal(): T[] - Perform a level-order traversal (breadth-first-search) and return an array of values.
• findMin(): T | null - Find the minimum value in the tree.
• findMax(): T | null - Find the maximum value in the tree.
• getHeight(): number - Calculate the height of the tree.

Example Usage

import { BinaryTree } from '@opensource-technologies/typescript-data-structure-library';

const tree = new BinaryTree<number>();

tree.insert(10);
tree.insert(5);
tree.insert(15);

console.log(tree.inOrderTraversal()); // Output: [5, 10, 15]
console.log(tree.search(10)); // Output: true
console.log(tree.findMin()); // Output: 5
console.log(tree.findMax()); // Output: 15
console.log(tree.getHeight()); // Output: 2

Contributing

Contributions are welcome! If you'd like to contribute to this project, please fork the repository and submit a pull request with your changes.

License

This project is licensed under the MIT License.