A collection of fundamental data structures implemented entirely from scratch in C++.
This project serves as a practical exercise in understanding how data structures work under the hood, managing memory manually, and writing efficient C++ code without relying on the Standard Template Library (STL) for the core implementations. Everything, including the underlying linked lists and maps used by the more complex structures, was built from the ground up.
Here is a breakdown of the data structures included in this project and their primary capabilities:
A self-balancing Binary Search Tree (BST) where the heights of the two child subtrees of any node differ by at most one.
insert(value): Inserts a new value and automatically balances the tree through rotations.remove(value): Removes a value and maintains the AVL balance property.searchAVL(value): Searches for a specific value within the tree.getMin(): Finds and returns the minimum value.printInOrder(): Prints the tree's elements in sorted order.
A weighted graph implemented using a custom adjacency list (which itself relies on custom Map and List templates).
insertEdge(v1, v2, weight): Adds a weighted edge between two vertices.deleteEdge(v1, v2): Removes an existing edge.findConnectedComponents(): Traverses the graph (using DFS) to find and count connected components.computeShortestPath(v1, v2): Calculates the shortest path between two nodes.computeSpanningTree(): Computes the Minimum Spanning Tree (MST) of the graph.
A dynamic hash table that resolves collisions using separate chaining (an array of custom LinkedList objects).
insert(number): Hashes the key and inserts it into the appropriate bucket.search(number): Looks up a value in O(1) average time.rehash(): Automatically resizes and reorganizes the table when the load factor gets too high.
Array-based binary heaps used to efficiently retrieve the minimum or maximum element. Both implementations dynamically resize themselves as needed.
insert(element): Adds an element and bubbles it up to maintain the heap property.extractMin()/extractMax(): Removes and returns the root (minimum or maximum value) while re-heapifying the structure.getMin()/getMax(): Peeks at the root value without removing it.
To keep the project strictly STL-free, custom generic (template) structures were implemented to support the Graph and Hash Table:
List<T>: A singly linked list supportingpush_front,push_back,erase, and indexing.Map<K, V>: A linked-list-based dictionary supporting key-value pairs and the[]operator.
To compile and run the code, you will need:
- A C++ compiler (GCC, Clang, or MSVC) supporting C++11 or later.
- Make or CMake (if you are using a specific build system).
./my_project