dst-typescript-collection

Data Structures in TypeScript

A comprehensive collection of data structures implemented in TypeScript with full test coverage.

📚 Data Structures Implemented

1. Linked List (MyLinkedList)

• Singly linked list with generic type support
• Operations: append, prepend, remove, search, contains
• Methods: getSize(), isEmpty(), toArray(), print(), clear()

2. Hash Map (MyHashMap)

• Generic key-value storage with collision handling
• Dynamic resizing and load factor management
• Operations: put, get, remove, containsKey, containsValue
• Methods: keys(), values(), entries(), getCapacity(), getLoadFactor()

3. Stack (MyStack)

• LIFO (Last In, First Out) data structure
• Configurable capacity (default: infinite)
• Operations: push, pop, peek
• Methods: isEmpty(), isFull(), size(), search(), contains()

4. Queue (MyQueue)

• FIFO (First In, First Out) data structure
• Configurable capacity (default: infinite)
• Operations: enqueue, dequeue, front, back
• Methods: isEmpty(), isFull(), size(), search(), contains()

5. Set (MySet)

• Collection of unique elements
• Set theory operations: union, intersection, difference, symmetric difference
• Methods: add(), delete(), has(), size(), isEmpty()

6. Tree (MyTree)

• Multi-child tree with configurable minimum children (default: 2)
• Traversal: preorder, postorder, level order
• Methods: addChild(), remove(), getHeight(), getDepth(), isBalanced()

7. Binary Search Tree (MyBST)

• Binary search tree with efficient search and insertion
• BST property: left child < parent < right child
• Traversal: inorder (sorted), preorder, postorder, level order
• Methods: insert(), search(), remove(), findMin(), findMax()
• BST-specific: isValidBST(), isBalanced(), getSuccessor(), getPredecessor()
• Loop detection: hasLoop(), getLoopCount(), getLoopData(), getLoopNodes()

8. AVL Tree (MyAVLTree)

• Self-balancing binary search tree with height balance
• AVL property: height difference between left and right subtrees ≤ 1
• Automatic rebalancing through rotations (left, right, left-right, right-left)
• Methods: insert(), search(), remove(), findMin(), findMax()
• AVL-specific: isValidAVL(), isBalanced(), getNodeBalanceFactor(), getNodeHeight()
• Traversal: inorder (sorted), preorder, postorder, level order

9. Red-Black Tree (MyRedBlackTree)

• Self-balancing binary search tree with color properties
• Red-Black properties: root is black, red nodes can't have red children, equal black height
• Automatic rebalancing through color changes and rotations
• Methods: insert(), search(), remove(), findMin(), findMax()
• RB-specific: isValidRedBlack(), getNodeColor(), isRed(), isBlack(), getParent(), getSibling(), getUncle()
• Traversal: inorder (sorted), preorder, postorder, level order

10. Graph (MyGraph)

• Directed and undirected graph support
• Weighted edges with customizable weights
• Algorithms: DFS, BFS, shortest path, cycle detection, topological sort
• Methods: addVertex(), addEdge(), hasPath(), getConnectedComponents()

11. Heap (MyHeap)

• Min/Max heap with priority queue functionality
• Configurable comparison functions
• Operations: insert, extract, peek
• Methods: getMin(), getMax(), getKthElement(), isValid()

12. Trie (MyTrie)

• Prefix tree for efficient string operations
• Pattern matching and autocomplete functionality
• Methods: insert(), search(), startsWith(), getWordsWithPrefix()

🚀 Getting Started

Prerequisites

• Node.js (v14 or higher)
• npm or yarn

Installation

# Clone the repository
git clone <repository-url>
cd DST

# Install dependencies
npm install

# Run tests
npm test

# Run tests with coverage
npm run test:coverage

# Build the project
npm run build

🧪 Testing

The project includes comprehensive test suites for all data structures:

# Run all tests
npm test

# Run tests in watch mode
npm run test:watch

# Run tests with coverage report
npm run test:coverage

Test Coverage

• 12 Test Suites: All data structures
• 523 Tests: Comprehensive coverage
• 100% Pass Rate: All tests passing

📁 Project Structure

DST/
├── src/
│   ├── DataStructures/
│   │   ├── MyLinkedList.ts
│   │   ├── MyHashMap.ts
│   │   ├── MyStack.ts
│   │   ├── MyQueue.ts
│   │   ├── MySet.ts
│   │   ├── MyTree.ts
│   │   ├── MyBST.ts
│   │   ├── MyAVLTree.ts
│   │   ├── MyRedBlackTree.ts
│   │   ├── MyGraph.ts
│   │   ├── MyHeap.ts
│   │   └── MyTrie.ts
│   ├── Test/
│   │   ├── MyLinkedList.test.ts
│   │   ├── MyHashMap.test.ts
│   │   ├── MyStack.test.ts
│   │   ├── MyQueue.test.ts
│   │   ├── MySet.test.ts
│   │   ├── MyTree.test.ts
│   │   ├── MyBST.test.ts
│   │   ├── MyAVLTree.test.ts
│   │   ├── MyRedBlackTree.test.ts
│   │   ├── MyGraph.test.ts
│   │   ├── MyHeap.test.ts
│   │   └── MyTrie.test.ts
│   └── index.ts
├── package.json
├── tsconfig.json
├── jest.config.js
└── README.md

💻 Usage Examples

Linked List

import { MyLinkedList } from './src/DataStructures/MyLinkedList';

const list = new MyLinkedList<number>();
list.append(1);
list.append(2);
list.prepend(0);
console.log(list.toArray()); // [0, 1, 2]

Hash Map

import { MyHashMap } from './src/DataStructures/MyHashMap';

const map = new MyHashMap<string, number>();
map.put('key1', 1);
map.put('key2', 2);
console.log(map.get('key1')); // 1

Stack

import { MyStack } from './src/DataStructures/MyStack';

const stack = new MyStack<number>();
stack.push(1);
stack.push(2);
console.log(stack.pop()); // 2

Queue

import { MyQueue } from './src/DataStructures/MyQueue';

const queue = new MyQueue<number>();
queue.enqueue(1);
queue.enqueue(2);
console.log(queue.dequeue()); // 1

Set

import { MySet } from './src/DataStructures/MySet';

const set = new MySet<number>();
set.add(1);
set.add(2);
set.add(1); // Duplicate, won't be added
console.log(set.size()); // 2

Tree

import { MyTree } from './src/DataStructures/MyTree';

const tree = new MyTree<number>();
tree.addToRoot(1);
tree.addChild(1, 2);
tree.addChild(1, 3);
console.log(tree.preorder()); // [1, 2, 3]

Binary Search Tree

import { MyBST } from './src/DataStructures/MyBST';

const bst = new MyBST<number>();
bst.insert(5);
bst.insert(3);
bst.insert(7);
console.log(bst.inorder()); // [3, 5, 7] (sorted)
console.log(bst.findMin()); // 3
console.log(bst.findMax()); // 7
console.log(bst.hasLoop()); // false (no loops in normal BST)

AVL Tree

import { MyAVLTree } from './src/DataStructures/MyAVLTree';

const avl = new MyAVLTree<number>();
avl.insert(5);
avl.insert(3);
avl.insert(7);
avl.insert(1);
console.log(avl.inorder()); // [1, 3, 5, 7] (sorted)
console.log(avl.isBalanced()); // true (always balanced)
console.log(avl.getNodeBalanceFactor(5)); // 0 (balanced)

Red-Black Tree

import { MyRedBlackTree } from './src/DataStructures/MyRedBlackTree';

const rbt = new MyRedBlackTree<number>();
rbt.insert(10);
rbt.insert(5);
rbt.insert(15);
rbt.insert(3);
rbt.insert(7);
console.log(rbt.inorder()); // [3, 5, 7, 10, 15] (sorted)
console.log(rbt.isValidRedBlack()); // true (validates RB properties)
console.log(rbt.getNodeColor(10)); // 'BLACK' (root is black)
console.log(rbt.isRed(5)); // true (some nodes are red)

Graph

import { MyGraph } from './src/DataStructures/MyGraph';

const graph = new MyGraph<string>();
graph.addVertex('A');
graph.addVertex('B');
graph.addEdge('A', 'B', 5);
console.log(graph.hasPath('A', 'B')); // true

Heap

import { MyHeap } from './src/DataStructures/MyHeap';

const heap = new MyHeap<number>(); // Min heap
heap.insert(3);
heap.insert(1);
heap.insert(2);
console.log(heap.peek()); // 1

Trie

import { MyTrie } from './src/DataStructures/MyTrie';

const trie = new MyTrie();
trie.insert('hello');
trie.insert('world');
console.log(trie.search('hello')); // true
console.log(trie.startsWith('hel')); // true

🔧 Development

Adding New Data Structures

• Create a new file in src/DataStructures/
• Implement the data structure with TypeScript
• Add comprehensive tests in src/Test/
• Export the class from src/index.ts
• Run tests to ensure everything works

Running Tests

# Run all tests
npm test

# Run specific test file
npm test -- MyLinkedList.test.ts

# Run tests with verbose output
npm test -- --verbose

📊 Performance

All data structures are optimized for:

• Time Complexity: Efficient algorithms implemented
• Space Complexity: Memory-efficient implementations
• Type Safety: Full TypeScript support with generics
• Error Handling: Comprehensive error checking

🤝 Contributing

• Fork the repository
• Create a feature branch (git checkout -b feature/amazing-feature)
• Commit your changes (git commit -m 'Add some amazing feature')
• Push to the branch (git push origin feature/amazing-feature)
• Open a Pull Request

📝 License

This project is licensed under the ISC License - see the LICENSE file for details.

🙏 Acknowledgments

• Built with TypeScript for type safety
• Tested with Jest for comprehensive coverage
• Inspired by classic data structures and algorithms

Happy Coding! 🚀