C++ Data Structures & Algorithms

Overview

In this systems development project, I built a full suite of classic data structures and algorithms from scratch in C++ using CLion — deliberately avoiding STL containers for the core exercises. Every implementation ships with a hand-rolled Node class, a destructor that reclaims memory node by node, and Big-O analysis integrated directly into the execution output. Below, each topic pairs the algorithm with an interactive sandbox you can run in your browser.

1. Fibonacci Sequence

Project Context: Built as an initial algorithmic warm-up to practice vector logic, basic loop structures, and tracking cumulative metrics (sum, max, and average) while mapping out algorithmic complexity.

// running it

$ g++ main.cpp -o fib && ./fibbrowser sandbox

Sequence: 0 1 1 2 3 5 8 13 21 34 55 89 144
Count:   13
Max:     144
Average: 28.92

$ python main.pyreal Python · Pyodide

Sequence: 0 1 1 2 3 5 8 13 21 34 55 89 144
Count:   13
Max:     144
Average: 28.92

Sequence: 0 1 1 2 3 5 8 13 21 34 55 89 144 | Count: 13 | Max: 144 | Average: 28.92

2. Linked Lists

Project Context: Moving beyond contiguous memory arrays, this module builds a singly linked list from scratch using a custom Node struct — completely avoiding std::list. It supports front and back insertions, precise node-after lookups, and manual memory teardown.

// running it

$ g++ main.cpp -o list && ./listbrowser sandbox

5 -> 10 -> 20 -> 15 -> NULL

$ python main.pyreal Python · Pyodide

5 -> 10 -> 20 -> 15 -> NULL

5 -> 10 -> 20 -> 15 -> NULL

Applied Project Component: Console Line Editor

This linked list data structure was scaled up into a fully functioning command-line text editor. EDIT loads a document into memory, :I inserts a line before a designated index, :D deletes lines or ranges, :L prints the file buffer, and :E saves and exits — turning raw pointer manipulation into a true productivity tool.

Assignment 1: Line Editor

// running it

$ g++ main.cpp -o editor && ./editorbrowser sandbox

> :L
1: Hello world
2: The quick brown fox
3: Goodbye moon
> :I 2 "Inserted between"
> :L
1: Hello world
2: Inserted between
3: The quick brown fox
4: Goodbye moon
> :D 1
> :L
1: Inserted between
2: The quick brown fox
3: Goodbye moon
> :E
Saved 3 lines to editor.txt

$ python main.pyreal Python · Pyodide

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class Editor:
    def __init__(self):
        self.head = None

def insert_at(self, pos, text):
        if pos <= 1 or self.head is None:
            node = Node(text)
            node.next = self.head
            self.head = node
            return
        cur = self.head
        n = 1
        while cur.next and n < pos - 1:
            cur = cur.next
            n += 1
        node = Node(text)
        node.next = cur.next
        cur.next = node

def delete_at(self, pos):
        if pos <= 1:
            self.head = self.head.next
            return
        cur = self.head
        n = 1
        while cur.next and n < pos - 1:
            cur = cur.next
            n += 1
        if cur.next:
            cur.next = cur.next.next

def list_lines(self):
        lines = []
        cur = self.head
        n = 1
        while cur:
            lines.append(f"{n}: {cur.data}")
            cur = cur.next
            n += 1
        return lines

> :L
1: Hello world
2: The quick brown fox
3: Goodbye moon
> :I 2 "Inserted between"
> :L
1: Hello world
2: Inserted between
3: The quick brown fox
4: Goodbye moon
> :D 1
> :L
1: Inserted between
2: The quick brown fox
3: Goodbye moon
> :E
Saved 3 lines to editor.txt

3. Stacks & Queues

Project Context: Re-utilizing the foundational Node structure to construct linear abstract data types enforcing strict access rules: Last-In-First-Out (LIFO) for stacks and First-In-First-Out (FIFO) for queues, the latter with an efficient tail pointer.

Stack — LIFO

// running it

$ g++ main.cpp -o stack && ./stackbrowser sandbox

3 2 1

$ python main.pyreal Python · Pyodide

3 2 1

3 2 1

Queue — FIFO

// running it

$ g++ main.cpp -o queue && ./queuebrowser sandbox

1 2 3

$ python main.pyreal Python · Pyodide

1 2 3

1 2 3

Applied Project Component: ASCII Maze Solver

Leveraged the stack and queue containers to ingest a 25×25 grid maze text file ( |, -, + walls ), navigate coordinate pathways from the top-left start to the bottom-right exit, and write the solved path back to disk marked with #.

Assignment 2: Maze Solver

// running it

$ g++ main.cpp -o maze && ./mazebrowser sandbox

#ifndef MAZE_H
#define MAZE_H

#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;

struct Pt { int r, c; };

// Breadth-first search from the top-left to the bottom-right corner. Edits the
// solved grid with '#' marking the route; returns false when no path exists.
bool solveMaze(const string maze[H], int h, int w, char solved[H][w + 1]) {
    Pt prev[H][w];
    bool seen[H][w];
    fill(&seen[0][0], &seen[0][0] + H * w, false);

queue<Pt> q;
    q.push({0, 0});
    seen[0][0] = true;
    prev[0][0] = {0, 0};

bool found = false;
    while (!q.empty()) {
        Pt p = q.front();
        q.pop();
        if (p.r == h - 1 && p.c == w - 1) { found = true; break; }
        int dr[] = {-1, 1, 0, 0}, dc[] = {0, 0, -1, 1};
        for (int k = 0; k < 4; k++) {
            int nr = p.r + dr[k], nc = p.c + dc[k];
            if (nr >= 0 && nr < h && nc >= 0 && nc < w &&
                maze[nr][nc] == ' ' && !seen[nr][nc]) {
                seen[nr][nc] = true;
                prev[nr][nc] = p;
                q.push({nr, nc});
            }
        }
    }
    if (!found) return false;

for (int r = 0; r < h; r++)
        for (int c = 0; c < w; c++) solved[r][c] = maze[r][c];

Pt p = {h - 1, w - 1};
    while (p.r != 0 || p.c != 0) { solved[p.r][p.c] = '#'; p = prev[p.r][p.c]; }
    solved[0][0] = '#';
    for (int r = 0; r < h; r++) solved[r][w] = '\0';
    return true;
}

#endif

Solved maze (# marks the path):
# +   
# +   
####  
+++#  
   ###

$ python main.pyreal Python · Pyodide

Solved maze (# marks the path):
# +   
# +   
####  
+++#  
   ###

4. Searching & Trees

Project Context: Transitioning from flat linear collections to hierarchical ordered structures, implementing recursive binary search, unbalanced binary search trees, and self-balancing AVL trees to maintain logarithmic lookup efficiency.

Recursive Binary Search

// running it

$ g++ main.cpp -o bsearch && ./bsearchbrowser sandbox

7 -> 3
4 -> -1

$ python main.pyreal Python · Pyodide

7 -> 3
4 -> -1

7 -> 3 | 4 -> -1

Binary Search Tree (BST)

// running it

$ g++ main.cpp -o bst && ./bstbrowser sandbox

1 3 4 5 7 8

$ python main.pyreal Python · Pyodide

1 3 4 5 7 8

1 3 4 5 7 8

Self-balancing Tree (AVL)

// running it

$ g++ avl.cpp main.cpp -o avl && ./avlbrowser sandbox

#include "avl.h"
#include <algorithm>

AVLNode* AVL::insert(AVLNode* n, int k) {
    if (!n) return new AVLNode(k);
    if (k < n->key) n->left = insert(n->left, k);
    else            n->right = insert(n->right, k);
    n->height = 1 + std::max(nodeHeight(n->left), nodeHeight(n->right));
    return rebalance(n);
}

AVLNode* AVL::erase(AVLNode* n, int k) {
    if (!n) return nullptr;
    if (k < n->key) {
        n->left = erase(n->left, k);
    } else if (k > n->key) {
        n->right = erase(n->right, k);
    } else {
        if (!n->left) return n->right;
        if (!n->right) return n->left;
        AVLNode* succ = n->right;
        while (succ->left) succ = succ->left;
        n->key = succ->key;
        n->right = erase(n->right, succ->key);
    }
    n->height = 1 + std::max(nodeHeight(n->left), nodeHeight(n->right));
    return rebalance(n);
}

AVLNode* AVL::rotateLeft(AVLNode* x) {
    AVLNode* y = x->right;
    x->right = y->left;
    y->left = x;
    x->height = 1 + std::max(nodeHeight(x->left), nodeHeight(x->right));
    y->height = 1 + std::max(nodeHeight(y->left), nodeHeight(y->right));
    return y;
}

AVLNode* AVL::rotateRight(AVLNode* y) {
    AVLNode* x = y->left;
    y->left = x->right;
    x->right = y;
    y->height = 1 + std::max(nodeHeight(y->left), nodeHeight(y->right));
    x->height = 1 + std::max(nodeHeight(x->left), nodeHeight(x->right));
    return x;
}

AVLNode* AVL::rebalance(AVLNode* n) {
    int bf = balanceOf(n);
    if (bf > 1) {
        if (balanceOf(n->left) < 0) n->left = rotateLeft(n->left);
        return rotateRight(n);
    }
    if (bf < -1) {
        if (balanceOf(n->right) > 0) n->right = rotateRight(n->right);
        return rotateLeft(n);
    }
    return n;
}

void AVL::insert(int k) { root = insert(root, k); }
void AVL::erase(int k) { root = erase(root, k); }

void AVL::inorder(AVLNode* n) const {
    if (!n) return;
    inorder(n->left);
    std::cout << n->key << " ";
    inorder(n->right);
}
void AVL::inorder() const { inorder(root); }

bool AVL::balanced(AVLNode* n) const {
    if (!n) return true;
    if (balanceOf(n) > 1 || balanceOf(n) < -1) return false;
    return balanced(n->left) && balanced(n->right);
}
bool AVL::balanced() const { return balanced(root); }

int AVL::height() const { return nodeHeight(root); }

void AVL::clear(AVLNode* n) {
    if (!n) return;
    clear(n->left);
    clear(n->right);
    delete n;
}

Building AVL from: 10 20 30 40 50
  root:    20
  height:  3
  inorder: 10 20 30 40 50
  balanced: yes
Deleting 20...
  root:    30
  height:  3
  inorder: 10 30 40 50
  balanced: yes

$ python main.pyreal Python · Pyodide

class AVLNode:
    def __init__(self, key):
        self.key = key
        self.height = 1
        self.left = None
        self.right = None

class AVL:
    def __init__(self):
        self.root = None

@staticmethod
    def height_of(n):
        return n.height if n else 0

@staticmethod
    def balance_of(n):
        return AVL.height_of(n.left) - AVL.height_of(n.right)

def insert(self, key):
        self.root = self._insert(self.root, key)

def erase(self, key):
        self.root = self._erase(self.root, key)

def _insert(self, n, key):
        if n is None:
            return AVLNode(key)
        if key < n.key:
            n.left = self._insert(n.left, key)
        else:
            n.right = self._insert(n.right, key)
        n.height = 1 + max(self.height_of(n.left), self.height_of(n.right))
        return self._rebalance(n)

def _erase(self, n, key):
        if n is None:
            return None
        if key < n.key:
            n.left = self._erase(n.left, key)
        elif key > n.key:
            n.right = self._erase(n.right, key)
        else:
            if n.left is None:
                return n.right
            if n.right is None:
                return n.left
            succ = n.right
            while succ.left:
                succ = succ.left
            n.key = succ.key
            n.right = self._erase(n.right, succ.key)
        n.height = 1 + max(self.height_of(n.left), self.height_of(n.right))
        return self._rebalance(n)

def _rebalance(self, n):
        bf = self.balance_of(n)
        if bf > 1:
            if self.balance_of(n.left) < 0:
                n.left = self._rotate_left(n.left)
            return self._rotate_right(n)
        if bf < -1:
            if self.balance_of(n.right) > 0:
                n.right = self._rotate_right(n.right)
            return self._rotate_left(n)
        return n

def _rotate_left(self, x):
        y = x.right
        x.right = y.left
        y.left = x
        x.height = 1 + max(self.height_of(x.left), self.height_of(x.right))
        y.height = 1 + max(self.height_of(y.left), self.height_of(y.right))
        return y

def _rotate_right(self, y):
        x = y.left
        y.left = x.right
        x.right = y
        y.height = 1 + max(self.height_of(y.left), self.height_of(y.right))
        x.height = 1 + max(self.height_of(x.left), self.height_of(x.right))
        return x

def inorder(self):
        out = []
        self._inorder(self.root, out)
        return out

def _inorder(self, n, out):
        if n:
            self._inorder(n.left, out)
            out.append(n.key)
            self._inorder(n.right, out)

def balanced(self):
        return self._balanced(self.root)

def _balanced(self, n):
        if n is None:
            return True
        if abs(self.balance_of(n)) > 1:
            return False
        return self._balanced(n.left) and self._balanced(n.right)

def height(self):
        return self.height_of(self.root)

Building AVL from: 10 20 30 40 50
  root:    20
  height:  3
  inorder: 10 20 30 40 50
  balanced: yes
Deleting 20...
  root:    30
  height:  3
  inorder: 10 30 40 50
  balanced: yes

Build 10 20 30 40 50 → root 20, height 3, inorder 10 20 30 40 50 | Delete 20 → root 30, inorder 10 30 40 50

Applied Project Component: Spell Checker

Ingests an external document, maps a dictionary into a self-balancing BST structure, scans text word by word against the tree nodes, flags spelling errors to the console, and outputs structural balance reports to disk.

Assignment 3: Spell Checker

// running it

$ g++ main.cpp -o spell && ./spellbrowser sandbox

#include "spell.h"
#include <cctype>
#include <iostream>
#include <sstream>
using namespace std;

int main() {
    BST tree;
    string dictionary[] = {"a", "accuracy", "along", "also", "ampersand", "an",
        "and", "as", "be", "but", "by", "characters", "check", "checked",
        "document", "for", "includes", "is", "it", "like", "of", "sample",
        "should", "sign", "special", "spell", "test", "the", "this", "to",
        "used", "which", "word", "words", "your"};
    for (const string& w : dictionary) tree.add(w);

string doc = "This is a sample document used to test the accuracy of your "
                 "spell checkr. It includes special characters and a sample "
                 "word thre which should be spell checked.";

cout << "Building dictionary tree...\n";
    cout << "Dictionary words: " << sizeof(dictionary) / sizeof(dictionary[0]) << "\n";
    cout << "\nMisspelled words:\n";

stringstream ss(doc);
    string token;
    while (ss >> token) {
        for (char& c : token) if (ispunct(c)) c = ' ';
        stringstream t2(token);
        string word;
        while (t2 >> word)
            if (!tree.contains(word)) cout << "  " << word << "\n";
    }
}

Building dictionary tree...
Dictionary words: 35
Document words:   28

Misspelled words:
  checkr
  thre

$ python main.pyreal Python · Pyodide

Building dictionary tree...
Dictionary words: 35
Document words:   28

Misspelled words:
  checkr
  thre

5. Hash Tables

Project Context: Implements a hash table using separate chaining where each bucket manages a linked list. Features a custom hashing function, O(1) head/tail inserts, and explicit bucket collision reporting.

// running it

$ g++ main.cpp -o hashtable && ./hashtablebrowser sandbox

0: otter dog
1: bat
2: cat
3: tiger raccoon
Contains 'tiger': yes

$ python main.pyreal Python · Pyodide

0: otter dog
1: bat
2: cat
3: tiger raccoon
Contains 'tiger': yes

0: otter dog
1: bat
2: cat
3: tiger raccoon
Contains 'tiger': yes

6. Sorting

Project Context: Concluding the algorithmic evaluation by executing sorting routines across large random vectors while systematically counting comparison and swap operations to quantify performance differences.

Bubble Sort

// running it

$ g++ main.cpp -o sort && ./sortbrowser sandbox

1 3 5 8 | swaps: 5

$ python main.pyreal Python · Pyodide

1 3 5 8 | swaps: 5

1 3 5 8 | swaps: 5

Applied Project Component: Command-Line Employee Sorter

Loads a tab-separated corporate dataset into a custom object model, overloads comparison operators to drive advanced merge sort logic, and sorts rows dynamically based on terminal arguments — ID, last name, hourly rate, and more.

Assignment 4: Employee Sorter

// running it

$ g++ main.cpp -o sort && ./sortbrowser sandbox

Merge sort by field #2 (last name), ascending:
W1232675, Herrera, Alexis, Yucca Valley, factory, 81.63
W8500260, Ho, Gael, Coshocton, factory, 57.04
W0679037, Murphy, Deegan, Brenham, sales, 54.42
W4372961, Pratt, Amir, Montclair, office, 12.34

$ python main.pyreal Python · Pyodide

Merge sort by field #2 (last name), ascending:
W1232675, Herrera, Alexis, Yucca Valley, factory, 81.63
W8500260, Ho, Gael, Coshocton, factory, 57.04
W0679037, Murphy, Deegan, Brenham, sales, 54.42
W4372961, Pratt, Amir, Montclair, office, 12.34

Engineering Takeaways

Building from scratch — hand-rolling each structure clarifies the physical memory trade-offs, such as why a tail pointer grants O(1) appends and why self-balancing prevents tree degeneration.
Memory discipline — custom destructors that walk and deallocate every node drill down robust, leak-free resource management in C++.
Algorithmic profiling — embedding Big-O metrics and operation counters directly into test outputs turns abstract complexity analysis into concrete, measurable engineering feedback.

All projects were implemented in C++ using CLion.

Give Feedback