C++ Data Structures and Algorithms

C++ implementations of core data structures and algorithms, written from scratch with a focus on correctness, complexity, and modern C++ practices.

Project Structure

.
├── .gitignore
├── LICENSE
├── README.md
├── algorithms
│   ├── searching.cpp
│   ├── searching.h
│   ├── sorting.cpp
│   └── sorting.h
├── array
│   ├── array.h
│   └── array2D.h
├── BST
│   └── BST.h
├── deque
│   └── deque.h
├── graph
│   ├── algorithms
│   │   ├── mst.cpp
│   │   ├── mst.h
│   │   ├── shortest_path.cpp
│   │   ├── shortest_path.h
│   │   ├── traversal.cpp
│   │   └── traversal.h
│   ├── graph.cpp
│   └── graph.h
├── hashTable
│   ├── HashTableChaining.h
│   ├── HashTableLinear.h
│   └── HashTableQuadratic.h
├── linkedList
│   ├── circularLinkedList.h
│   ├── doublyLinkedList.h
│   └── linkedList.h
├── queue
│   ├── circularQueue.h
│   ├── priorityQueue.h
│   └── queueArrayBased.h
└── stack
    └── stack.h

Contents

Folder	What's inside
array	Dynamic Array<T> and Array2D<T> with insert, erase, search, fill, enlarge, and merge
linkedList	Singly linked list (with reverse()), doubly linked list, and circular linked list
stack	Array-based Stack<T> with push, pop, and peek
queue	Array-based queue, circular queue, and a linked-list priority queue
deque	Double-ended queue (Deque<T>) on a circular buffer, with insert/delete at both ends and search
hashTable	Hash tables for int keys: separate chaining, linear probing, and quadratic probing
BST	Binary search tree with insert, search, remove, min/max, height, and in/pre/post-order traversals
graph	Adjacency-list Graph, plus traversal, shortest-path, and minimum-spanning-tree algorithms in graph/algorithms
algorithms	Sorting and searching algorithms

Algorithms

• Sorting: selection sort, bubble sort, insertion sort, heap sort, merge sort, quick sort
• Searching: linear search, binary search (iterative and recursive)
• Graph traversal: BFS (with distances and parents), DFS, DFS with discovery/finish timestamps, connected components, cycle detection, topological sort
• Shortest paths: Dijkstra (priority queue), Bellman-Ford (with negative-cycle detection), Floyd-Warshall, path reconstruction
• Minimum spanning tree: Kruskal (union-find with path compression and union by rank) and Prim (priority queue)

Highlights

• Containers are generic class templates in the ds namespace, so they work with any copyable type. The hash tables are written for int keys.
• Classes that own memory follow the Rule of Three: a copy constructor, copy assignment operator, and destructor that do a deep copy and release memory correctly.
• Invalid operations are reported with standard exceptions (std::out_of_range, std::runtime_error, std::logic_error) instead of undefined behavior.
• The open-addressing hash tables track a load factor and rehash to the next prime size when it reaches 0.7.
• Graph algorithms validate their input, for example Dijkstra rejects negative edge weights and topological sort rejects graphs with cycles.

Building

The data structures are header-only, so include the header you need:

#include "BST/BST.h"

int main() {
    ds::BST<int> tree;
    tree.insert(5);
    tree.insert(3);
    tree.insert(8);
    tree.printInOrder();
}

The sorting, searching, and graph code has .cpp files, so compile them together with your main.cpp:

g++ -std=c++17 main.cpp algorithms/sorting.cpp algorithms/searching.cpp -o main

The code compiles with any C++11 or later compiler (checked with g++).