C++ Templated Basic Data Structures, DirectedGraph, AVL Tree, Priority Queue, Doubly Linked List, Stack, Queue, HashMap, MinHeap

AVL.h

#ifndef AVL_H
#define AVL_H

#include <iostream>
#include <stdlib.h>
#include <stack>
#include "../data_structs/queueLL.h"

using std::stack;

template<typename T>
class AVL{
    private:
        class Vertex{
            public:
                int height;
                Vertex() :
                    height(0), right(nullptr), left(nullptr){}

                Vertex(const T& data) :
                    height(0), right(nullptr), left(nullptr), data(data){}

                Vertex(const T& data, Vertex* left, Vertex* right) :
                    height(0), right(right), left(left), data(data){}

                Vertex* right;
                Vertex* left;
                T data;
        };

        enum WeightStatus{BALANCED, LEFT_HEAVY, RIGHT_HEAVY, ERROR};

        Vertex* root;

        //keeps track of the vertex when a find operation has been executed
        Vertex* finder;

        int numberOfElements;

        ///Helper Functions///
        void insert(const T& entry, Vertex*& current);
        void remove(const T& target, Vertex*& current);

        void clear(Vertex*& current);
        void displayInOrder(const Vertex* current);
        void displayPreOrder(const Vertex* current);
        void displayPostOrder(const Vertex* current);

        Vertex* find(Vertex* current, const T& target) const;
        const Vertex* getMin(const Vertex* current) const;
        const Vertex* getMax(const Vertex* current) const;
        int getHeight(const Vertex* current) const;
        WeightStatus getWeight(const Vertex* current) const;

        void balance(Vertex*& current);
        void leftRotation(Vertex*& current);
        void rightRotation(Vertex*& current);
        void updateHeight(Vertex*& current);

        int max(int a, int b) const;

    public:
        class Iterator{
            private:
                stack<Vertex*> parents;
                Vertex* current = nullptr;
            public:
                Iterator(){}
                Iterator(Vertex* const begin){
                    current = begin;
                }

                T& getData() const{
                    return current->data;
                }

                //in order traversal through tree
                T& next(){
                    //go all the way to the left - current is null after the loop
                    while(current){
                        parents.push(current);
                        current = current->left;
                    }
                    //get parent
                    current = parents.top();
                    parents.pop();

                    //save current
                    Vertex* temp = current;

                    //go to the right of the tree
                    current = current->right;
                    return temp->data;
                }
                bool hasNext(){
                    return current != nullptr || !parents.empty();
                }
                //the stack gets reset - only the current Vertex is copied
                Iterator operator=(const Iterator& src){
                    if(this == &src)
                        return *this;
                    this->current = src.current;
                    return *this;
                }

                bool operator==(const Iterator& i){
                    return current == i.current;
                }
                bool operator!=(const Iterator& i){
                    return current != i.current;
                }
        };

        AVL();
        AVL(const AVL& src);
        ~AVL();

        void insert(const T& entry);
        void remove(const T& target);

        bool find(const T& target);

        Iterator get(const T& target);

        //Should only be called if find() returned true;
        const T& getFoundData() const;

        const T& getMin() const;
        const T& getMax() const;
        int getHeight() const;

        void display();         //inOrderDisplay - generic name
        void displayInOrder();
        void displayPreOrder();
        void displayPostOrder();
        void displayLevelOrder();
        const T& getRootValue();

        int size();
        bool isEmpty();
        void clear();

        const Iterator begin() const;
        const Iterator end() const;
};

template<typename T>
AVL<T>::AVL() :
    root(nullptr), finder(nullptr), numberOfElements(0)
{}

template<typename T>
AVL<T>::AVL(const AVL& src){
    root = nullptr;
    finder = nullptr;

    Iterator src_itr;
    src_itr = src.begin();
    while(src_itr.hasNext())
        this->insert(src_itr.next());
}

template<typename T>
AVL<T>::~AVL(){
    clear();
}

template<typename T>
void AVL<T>::insert(const T& entry){
    insert(entry, root);
}

template<typename T>
void AVL<T>::remove(const T& target){
    remove(target, root);
}

template<typename T>
bool AVL<T>::find(const T& target){
    finder = find(root, target);
    return (finder);
}

template<typename T>
typename AVL<T>::Iterator AVL<T>::get(const T& target){
    return Iterator(find(root, target));
}

template<typename T>
const T& AVL<T>::getFoundData() const {
    return finder->data;
}

template<typename T>
const T& AVL<T>::getMin() const{
    return getMin(root)->data;
}

template<typename T>
const T& AVL<T>::getMax() const{
    return getMax(root)->data;
}

template<typename T>
int AVL<T>::getHeight() const{
    return getHeight(root);
}

template<typename T>
void AVL<T>::display(){
    displayInOrder(root);
}

//left-parent-right
template<typename T>
void AVL<T>::displayInOrder(){
    displayInOrder(root);
}

//parent-left-right
template<typename T>
void AVL<T>::displayPreOrder(){
    displayPreOrder(root);
}

//left right parent
template<typename T>
void AVL<T>::displayPostOrder(){
    displayPostOrder(root);
}

template<typename T>
void AVL<T>::displayLevelOrder(){
    QueueLL<Vertex*> container;
    container.enqueue(root);
    while(!container.empty()){
        Vertex* current = container.dequeue();
        if(current != nullptr){

            //display parent
            std::cout << current->data << std::endl;

            //enqueue children for future printing
            container.enqueue(current->left);
            container.enqueue(current->right);
        }
    }
}

template<typename T>
const T& AVL<T>::getRootValue(){
    return root->data;
}

template<typename T>
int AVL<T>::size(){
    return numberOfElements;
}

template<typename T>
bool AVL<T>::isEmpty(){
    return root == nullptr;
}

template<typename T>
void AVL<T>::clear(){
    clear(root);
}

template<typename T>
const typename AVL<T>::Iterator AVL<T>::begin() const{
    return Iterator(root);
}

template<typename T>
const typename AVL<T>::Iterator AVL<T>::end() const{
    return Iterator(nullptr);
}

///Helper Functions///
template<typename T>
void AVL<T>::insert(const T& entry, Vertex*& current){
    //empty slot found
    if(current == nullptr){
        current = new Vertex(entry);
        ++numberOfElements;
    }

    //larger values go to right of tree
    else if(entry > current->data)
        insert(entry, current->right);

    //smaller values go to the left
    else
        insert(entry, current->left);

    updateHeight(current);

    //balance every vertex(if needed) along the traversed path
    balance(current);
}

template<typename T>
void AVL<T>::remove(const T& target, Vertex*& current){
    //search for the target
    if(current != nullptr){
        //found
        if(target == current->data){
            --numberOfElements;
            //full node case
            if(current->left && current->right){
                int r = rand() % 2;
                //replace data with maximum vertex data in left substree
                if(r == 0){
                    Vertex* max = const_cast<Vertex*>(getMax(current->left));
                    current->data = max->data;
                    delete max;
                    max = nullptr;
                }
                //replace data with minimum vertex data in right substree
                else{
                    Vertex* min = const_cast<Vertex*>(getMin(current->right));
                    current->data = min->data;
                    delete min;
                    min = nullptr;
                }
            }
            //left child exists - create link from current's parent to current's child
            else if(current->left){
                Vertex* child = current->left;
                delete current;
                current = child;
            }
            //right child exists - create link from current's parent to current's child
            else if(current->right){
                Vertex* child = current->right;
                delete current;
                current = child;
            }
            //leaf
            else{
                delete current;
                current = nullptr;
            }
        }
        //search left
        else if(target > current->data)
            remove(target, current->right);

        //search right
        else
            remove(target, current->left);
    }
    updateHeight(current);

    //balance every vertex(if needed) along the traversed path
    balance(current);
}

template<typename T>
typename AVL<T>::Vertex* AVL<T>::find(Vertex* current, const T& target) const{

    //return a default T
    if(current == nullptr)
        return current;

    //found
    if(target == current->data)
        return current;

    //search left
    else if(target < current->data)
        return find(current->left, target);

    //search right
    else
        return find(current->right, target);
}

//return the left most vertex
template<typename T>
const typename AVL<T>::Vertex* AVL<T>::getMin(const Vertex* current) const{
    if(current == nullptr)
        return current;
    while(current->left != nullptr)
        current = current->left;
    return current;
}

//return the right most vertex
template<typename T>
const typename AVL<T>::Vertex* AVL<T>::getMax(const Vertex* current) const{
    if(current == nullptr)
        return current;
    while(current->right != nullptr)
        current = current->right;
    return current;
}

template<typename T>
int AVL<T>::getHeight(const Vertex* current) const{
    if(current == nullptr)
        return -1;
    return current->height;
}

template<typename T>
typename AVL<T>::WeightStatus AVL<T>::getWeight(const Vertex* current) const{
    if(current == nullptr)
        return ERROR;

    int l = getHeight(current->left);
    int r = getHeight(current->right);
    int diff = l - r;

    if(diff > 1 ) return LEFT_HEAVY;
    if(diff < -1) return RIGHT_HEAVY;
    return BALANCED;
}

template<typename T>
void AVL<T>::balance(Vertex*& current){
    if(current != nullptr){
        WeightStatus w = getWeight(current);

        //left heavy
        if(w == LEFT_HEAVY){
            w = getWeight(current->left);

            //left-left heavy
            if(w == LEFT_HEAVY || w == BALANCED)
                rightRotation(current);

            //left-right heavy
            else{
                leftRotation(current->left);
                rightRotation(current);
            }
        }
        //right heavy
        else if(w == RIGHT_HEAVY){
            w = getWeight(current->right);

            //right-right heavy
            if(w == RIGHT_HEAVY || w == BALANCED)
                leftRotation(current);

            //right-left heavy
            else{
                rightRotation(current->right);
                leftRotation(current);
            }
        }
    }
}

template<typename T>
void AVL<T>::leftRotation(Vertex*& current){
    if(current != nullptr){
        Vertex* newLeftChild = current;
        Vertex* newCurrent = current->right;
        Vertex* newLeftRightChild = current->right->left;

        current = newCurrent;                       //height changes
        current->left = newLeftChild;               //height changes
        current->left->right = newLeftRightChild;   //height doesn't change

        //update heights
        updateHeight(current->left);
        updateHeight(current);
    }
}

template<typename T>
void AVL<T>::rightRotation(Vertex*& current){
    if(current != nullptr){
        Vertex* newRightChild = current;
        Vertex* newCurrent = current->left;
        Vertex* newRightLeftChild = current->left->right;

        current = newCurrent;
        current->right = newRightChild;
        current->right->left = newRightLeftChild;

        //update heights
        updateHeight(current->right);
        updateHeight(current);
    }
}

template<typename T>
void AVL<T>::updateHeight(Vertex*& current){
    if(current != nullptr){
        int l = getHeight(current->left);
        int r = getHeight(current->right);
        current->height = 1 + max(l, r);
    }
}

template<typename T>
void AVL<T>::displayInOrder(const Vertex* current){
    if(current != nullptr){
        //print left subtree
        displayInOrder(current->left);
        //print parent
        std::cout << current->data << std::endl;
        //print right subtree
        displayInOrder(current->right);
    }
}

template<typename T>
void AVL<T>::displayPreOrder(const Vertex* current){
    if(current != nullptr){
        std::cout << current->data << std::endl;
        displayInOrder(current->left);
        displayInOrder(current->right);
    }
}

template<typename T>
void AVL<T>::displayPostOrder(const Vertex* current){
    if(current != nullptr){
        displayInOrder(current->left);
        displayInOrder(current->right);
        std::cout << current->data << std::endl;
    }
}

template<typename T>
void AVL<T>::clear(Vertex*& current){
    if(current != nullptr){
        //go to children
        clear(current->right);
        clear(current->left);

        //delete parent
        delete current;
        current = nullptr;
    }
}

template<typename T>
int AVL<T>::max(int a, int b) const{
    return (a > b) ? a : b;
}

#endif

basic_priority_queue.h

/*
    Priority Queue that used the vector as
    a container
*/

#ifndef BASIC_PQ
#define BASIC_PQ

#include <vector>
#include <iostream>

using std::vector;

template <typename T>
class basic_priority_queue{

    private:
        vector<T> container;

    public:

        void insert(const T& entry){
            //empty container
            if(container.empty())
                container.push_back(entry);

            //greater than last
            else if(entry >= container.back())
                container.push_back(entry);

            else{
                typename vector<T>::iterator i;
                for(i = container.begin(); i != container.end(); i++){
                    if(entry < *i){
                        container.insert(i, entry);
                        return;
                    }
                }
                //add to the back - entry has the greatest value
                container.push_back(entry);
            }
        }

        void update(const T& target){
            //find entry
            typename vector<T>::iterator i;
            for(i = container.begin(); i != container.end(); ++i){
                //found
                if(target == *i){
                    container.erase(i);
                    this->insert(target);
                    break;
                }
            }
        }

        const T& extractMin(){
            return container.front();
        }

        //removes min
        void pop(){
            container.erase(container.begin());
        }

        bool empty(){
            return container.empty();
        }

        void display(){
            typename vector<T>::iterator i;
            for(i = container.begin(); i != container.end(); ++i)
                std::cout << *i << std::endl;
        }

        // POINTER VARIANTS
        void insert(const T*& entry){
            //empty container
            if(container.empty())
                container.push_back(entry);

            //greater than last
            else if(entry >= container.back())
                container.push_back(entry);

            else{
                typename vector<T>::iterator i;
                for(i = container.begin(); i != container.end(); i++){
                    if(*entry < **i){
                        container.insert(i, entry);
                        return;
                    }
                }
                //add to the back - entry has the greatest value
                container.push_back(entry);
            }
        }

    void update(const T*& target){
        //find entry
        typename vector<T>::iterator i;
        for(i = container.begin(); i != container.end(); ++i){
            //found
            if(*target == **i) {
                container.erase(i);
                this->insert(target);
                break;
            }
        }
    }
};


#endif

BinaryMinHeap.h

#ifndef BINARYMINHEAP_H
#define BINARYMINHEAP_H

#include <iostream>
#include <cassert>
#include <vector>
using std::vector;
using std::cout;
using std::endl;

template<typename T>
class BinaryMinHeap{

    private:
        //container to hold all elements
        vector<T> container;

        //obtains parent/child indexes relative to current index
        int getParentIndex(int currentIndex);
        int getRightChildIndex(int currentIndex);
        int getLeftChildIndex(int currentIndex);

        void swap(T& a, T& b);

        void pushUp();
        void pushDown(int currentIndex, int end);

    public:
        BinaryMinHeap();
        ~BinaryMinHeap();

        void insert(const T& entry);
        T extractMin();

        void updateValue(const T& target);

        int size();
        bool isEmpty();

        void clear();
        void displayLevelOrder();
};

template<typename T>
BinaryMinHeap<T>::BinaryMinHeap(){}

template<typename T>
BinaryMinHeap<T>::~BinaryMinHeap(){}

template<typename T>
void BinaryMinHeap<T>::insert(const T& entry){
    //insert at the end first
    container.push_back(entry);
    pushUp();
}

template <typename T>
T BinaryMinHeap<T>::extractMin(){
    //save min
    T min = container.front();

    int end = container.size() - 1;
    int currentIndex = 0;


    //swap first element with last- and remove last after swap
    swap(container.at(currentIndex), container.at(end));
    container.pop_back();
    end--;

    pushDown(currentIndex, end);

    return min;
}

//Updates an element from the min heap and shifts it accordingly through the heap to
//keep order constraint
template<typename T>
void BinaryMinHeap<T>::updateValue(const T& target){
}

template<typename T>
void BinaryMinHeap<T>::pushDown(int currentIndex, int end){
    while(1){
        int leftIndex = getLeftChildIndex(currentIndex);
        int rightIndex = getRightChildIndex(currentIndex);

        //full node
        if(leftIndex <= end && rightIndex <= end){
            T left = container.at(leftIndex);
            T right = container.at(rightIndex);
            T current = container.at(currentIndex);

            //no violation
            if(current < right && current < left)
                break;

            //find smaller one
            int smaller = (left < right) ? leftIndex : rightIndex;

            //swap with smaller
            swap(container.at(currentIndex), container.at(smaller));
            currentIndex = smaller;

        }
        //only left exist
        else if(leftIndex <= end){
            T left = container.at(leftIndex);
            T current = container.at(currentIndex);

            //no violation
            if(current < left)
                break;

            swap(container.at(currentIndex), container.at(leftIndex));
            currentIndex = leftIndex;
        }
        //no children - we are done
        else break;
    }
}

template<typename T>
void BinaryMinHeap<T>::pushUp(){
    /*check for order constraint- push the entry upwards
        until it its parent is smaller and its children are greater*/
    int currentIndex = container.size() - 1;
    int parentIndex = getParentIndex(currentIndex);

    //keep pushing up until order contraint is satisfied
    while(container.at(currentIndex) < container.at(parentIndex)){
        swap(container.at(currentIndex), container.at(parentIndex));

        currentIndex = parentIndex;
        parentIndex = getParentIndex(currentIndex);
    }
}

template<typename T>
int BinaryMinHeap<T>::size(){
    return container.size();
}

template<typename T>
bool BinaryMinHeap<T>::isEmpty(){
    return container.empty();
}


template<typename T>
void BinaryMinHeap<T>::clear(){
    container.clear();
}

template<typename T>
int BinaryMinHeap<T>::getParentIndex(int currentIndex){
    assert(currentIndex >= 0 && currentIndex < container.size());
    return (currentIndex - 1) / 2;
}

template<typename T>
int BinaryMinHeap<T>::getRightChildIndex(int currentIndex){
    return 2*currentIndex + 2;
}

template<typename T>
int BinaryMinHeap<T>::getLeftChildIndex(int currentIndex){
    return 2*currentIndex + 1;
}

template<typename T>
void BinaryMinHeap<T>::swap(T& a, T& b){
    T temp(a);
    a = b;
    b = temp;
}

template<typename T>
void BinaryMinHeap<T>::displayLevelOrder(){
    for(T e: container)
        cout << e << endl;
}

#endif

DirectedGraph.h

#ifndef DIRECTED_GRAPH_H
#define DIRECTED_GRAPH_H

#include <iostream>
#include <ostream>
#include <vector>
#include <queue>
#include <string>
#include <limits>
#include "../AVL/AVL.h"
#include "../data_structs/basic_priority_queue.h"

using std::vector;
using std::ostream;
using std::cout;
using std::endl;
using std::queue;
using std::string;

template<typename T>
class DirectedGraph{
    public:
        class Edge;

        class Vertex{

            friend ostream& operator<<(ostream& os, const Vertex& v){
                os << v.data << ":\tadj. list: ";
                for(Edge e : v.outgoingEdges)
                    os << e.end->data << ", ";
                return os;
            }

            public:
                Vertex(){}
                Vertex(const T& data) : data(data){}

                T data;
                Vertex* predecessor = nullptr;
                vector<Edge> outgoingEdges;
                bool visited = false;
                int weight = 0;

                bool weightCompare = false;

                //number of incoming edges
                int inDegree = 0;

                //used for temporary computation (like in topo sort)
                int tempInDegree = 0;

                bool operator<(const Vertex& v) const{
                    if(weightCompare)
                        return weight < v.weight;
                    return data < v.data;
                }

                bool operator>(const Vertex& v) const{
                    if(weightCompare)
                        return weight > v.weight;
                    return data > v.data;
                }

                bool operator>=(const Vertex& v) const{
                    if(weightCompare)
                        return weight >= v.weight;
                    return data >= v.data;
                }

                bool operator==(const Vertex& v) const{
                    if(weightCompare)
                        return weight == v.weight;
                    return data == v.data;
                }
        };

        class Edge{
            public:
                Edge() :
                    start(nullptr), end(nullptr){}
                int weight;
                Vertex* start;
                Vertex* end;
                bool operator==(const Edge& e){
                    return *start == *(e.start) && *end == *(e.end);
                }
        };

        DirectedGraph(){}
        ~DirectedGraph(){}

        void addVertex(const T& entry){
            vertices.insert(Vertex(entry));
        }

        void removeVertex(const T& target){
            vertices.remove(Vertex(target));
        }

        void addEdge(const T& start, const T& end, int weight = 1){
           typename AVL<Vertex>::Iterator startItr = vertices.get(Vertex(start));
           typename AVL<Vertex>::Iterator endItr = vertices.get(Vertex(end));

            //check if vertices were found
            if(startItr != vertices.end() && endItr != vertices.end()){

                //create directed edge between start and end
                Edge e;
                e.start = &startItr.getData();
                e.end = &endItr.getData();
                e.weight = weight;

                //add edge to start vertex
                startItr.getData().outgoingEdges.push_back(e);
                endItr.getData().inDegree++;
            }
        }

        void removeEdge(const T& start, const T& end){
           typename AVL<Vertex>::Iterator startItr = vertices.get(Vertex(start));
           typename AVL<Vertex>::Iterator endItr = vertices.get(Vertex(end));

            //check if vertices were found
            if(startItr != vertices.end() && endItr != vertices.end()){

                //create directed edge between start and end
                Edge e;
                e.start = &startItr.getData();
                e.end = &endItr.getData();

                //remove edge from start vertex
                vector<Edge>* v = &(startItr.getData().outgoingEdges);
                for(int i = 0; i < v->size(); i++)
                    if(e == v->at(i)){
                        v->erase(v->begin() + i);
                        break;
                    }
                endItr.getData().inDegree--;
            }
        }

        //do a BFS on the entire graph relative to the start vertex
        void BFS(const T& start){
            typename AVL<Vertex>::Iterator itr = vertices.get(Vertex(start));

            //start found
            if(itr != vertices.end()){
                //reset visit booleans to false - and predecessors to null
                typename AVL<Vertex>::Iterator i;
                i = vertices.begin();
                while(i.hasNext()){
                    Vertex* v = &i.next();
                    v->visited = false;
                    v->predecessor = nullptr;
                }

                //create queue and insert first element
                queue<Vertex*> q;
                itr.getData().visited = true;
                q.push(&itr.getData());

                //queue not empty
                while(!q.empty()){
                    Vertex* v = q.front();
                    q.pop();

                    //go through all neighbors
                    for(Edge e : v->outgoingEdges){

                        //unvisited
                        if(!e.end->visited){
                            e.end->visited = true;
                            e.end->predecessor = v;
                            q.push(e.end);
                        }
                    }
                }
            }
        }

        //shortest path using BFS
        void shortestPath(const T& start, const T& end){
            typename AVL<Vertex>::Iterator startItr = vertices.get(Vertex(start));
            typename AVL<Vertex>::Iterator endItr = vertices.get(Vertex(end));

            //found
            if(startItr != vertices.end() && endItr != vertices.end()){
                Vertex current = endItr.getData();
                string path = "";

                //while we can traverse back to the end
                while(current.predecessor){
                    path = " -> " + current.data + path;
                    current = *current.predecessor;
                }
                path = "Path: " + current.data + path;
                cout << path;
            }
        }

        //perform dijkstra's shortest path on the graph
        //relative to start
        void dijkstra(const T& start){
            typename AVL<Vertex>::Iterator itr = vertices.get(Vertex(start));

            if(itr != vertices.end()){

                basic_priority_queue<Vertex*> pq;

                //Vertices: reset visit booleans to false , predecessors to null, and weights to "infinity"
                typename AVL<Vertex>::Iterator i;
                i = vertices.begin();
                while(i.hasNext()){
                    Vertex* v = &i.next();
                    v->weightCompare = true;
                    v->predecessor = nullptr;
                    v->weight = 10000000;

                    //fill the container with the unvisited verticex
                    pq.insert(v);
                }
                //itr is pointing to start
                //Set starting point weight;
                itr.getData().weight = 0;
                pq.update(&itr.getData());

                while(!pq.empty()){
                    Vertex* current = pq.extractMin();
                    pq.pop();

                    //reset weight compare to false - (for correct comparisons inside AVL tree container)
                    current->weightCompare = false;

                    for(Edge e : current->outgoingEdges){
                        Vertex* adj = e.end;

                        //update Vertex weight from current to adj
                        //if there is a new shorter path to adj
                        int newWeight = current->weight + e.weight;
                        if(newWeight < adj->weight){
                            adj->predecessor = current;
                            adj->weight = newWeight;
                            //restructure pq
                            pq.update(adj);
                        }
                    }
                }
            }
        }

        //display each vertex and their adjacent vertices
        void display(){
            typename AVL<Vertex>::Iterator itr;
            itr = vertices.begin();
            while(itr.hasNext())
                cout << itr.next() << endl;
        }

        //display the predecessor vertex for each vertex from the most recent BFS
        void displayPredecessorLinks(){
            typename AVL<Vertex>::Iterator itr;
            itr = vertices.begin();
            while(itr.hasNext()){
                Vertex v = itr.next();
                cout << "Vertex: " << v.data << " pred is: ";

                //if predecessor exists
                if(v.predecessor != nullptr)
                    cout << v.predecessor->data << endl;
                else
                    cout << "NULL\n";
            }
        }

        //takes in a containers to store the data of vertices in topo order.
        bool topoSort(vector<T>& container){
            //tempIndegree to the original indegree
            typename AVL<Vertex>::Iterator itr = vertices.begin();
            while(itr.hasNext()){
                Vertex* v = &itr.next();
                v->tempInDegree = v->inDegree;
            }

            //queue up all vertices with indegrees of zero
            //No incoming edges
            queue<Vertex*> q;
            itr = vertices.begin();
            while(itr.hasNext()){
                Vertex* v = &itr.next();
                if(v->inDegree == 0)
                    q.push(v);
            }

            int i = 0;
            while(!q.empty()){
                //obtain a vertex with no incoming edges
                Vertex* v = q.front(); q.pop();

                //store in container
                container.push_back(v->data);
                ++i;

                for(Edge e : v->outgoingEdges){
                    Vertex* adj = e.end;

                    //since we popped v from the queue,
                    //adj, has one less incoming edge
                    adj->tempInDegree--;

                    //if it has indegree of 0, then that is the next
                    //vertices we can visit
                    if(adj->tempInDegree == 0)
                        q.push(adj);
                }
            }
            //cycle found
            if(i != vertices.size())
                return false;
            return true;
        }


        //retrieve vertex data
        const Vertex* find(const T& target){
            typename AVL<Vertex>::Iterator i = vertices.get(Vertex(target));
            if(i != vertices.end())
                return &i.getData();
            return nullptr;
        }

        void clear(){
            vertices.clear();
        }

    private:
        //container of vertices for the graph
        AVL<Vertex> vertices;
};

#endif

doublyLinkedList.h

#ifndef DOUBLYLINKEDLIST_H
#define DOUBLYLINKEDLIST_H

template<typename T>
class DoublyLinkedList{
    //display
    friend std::ostream& operator<<(std::ostream& os, const DoublyLinkedList& list){
        for(Iterator itr = list.begin(); itr != list.end(); ++itr)
            os << itr.peek() << '\n';
        return os;
    }
    private:
        template<typename>
        class Node{
            public:
                Node() :
                    next(nullptr, prev(nullptr)){}

                Node(const T& data) :
                    data(data), next(nullptr), prev(nullptr){}

                Node(const T& data, Node<T>* next, Node<T>* prev) :
                    data(data), next(next), prev(prev) {}

                T data;
                Node<T>* next;
                Node<T>* prev;
        };

        Node<T>* head;
        Node<T>* tail;
        int numberOfElements;

    public:
        class Iterator{
            private:
                const Node<T>* current;

            public:
                Iterator(){}
                Iterator(const Node<T>* current) :
                    current(current){}

                void operator++(){
                    current = current->next;
                }

                Iterator& operator++(int useless){
                    current = current->next;
                    return *this;
                }

                bool operator!=(const Iterator& other) const{
                    return current != other.current;
                }

                bool operator==(const Iterator& other) const{
                    return current == other.current;
                }

                const T& peek() const{
                    return current->data;
                }

                const Node<T>* getCurrent() const{
                    return current;
                }
        };

        //create an empty list
        DoublyLinkedList();

        ~DoublyLinkedList();

        const int size() const
            {return numberOfElements;}

        void addFront(const T& entry);
        void addBack(const T& entry);
        void removeFront();
        void removeBack();

        //user must check if list is not empty in order to get elements
        const T& getFront() const;
        const T& getBack() const;
        const T& getAt(const Iterator& itr) const;

        void insertNextTo(const T& target, const T& newEntry);
        void insertPrevTo(const T& target, const T& newEntry);
        void insertNextTo(const Iterator& itr, const T& newEntry);
        void insertPrevTo(const Iterator& itr, const T& newEntry);

        void remove(const T& target);

        //has the iterator point to the element next to the one removed - careful with this one
        void removeAt(Iterator& itr);

        void display() const;
        void displayReversed() const;
        void clear();
        bool isEmpty() const;

        const Iterator begin() const
            {return Iterator(head);}

        const Iterator end() const
            {return Iterator(nullptr);}
};

template<typename T>
DoublyLinkedList<T>::DoublyLinkedList() :
    head(nullptr),
    tail(nullptr),
    numberOfElements(0)
{}

template<typename T>
DoublyLinkedList<T>::~DoublyLinkedList(){
    clear();
}

template<typename T>
void DoublyLinkedList<T>::addFront(const T& entry){
    Node<T>* temp = new Node<T>(entry, head, nullptr);

    //empty list
    if(tail == nullptr)
        tail = temp;

    //old head becomes second
    if(head != nullptr)
        head->prev = temp;

    //update new head
    head = temp;

    ++numberOfElements;
}

template<typename T>
void DoublyLinkedList<T>::addBack(const T& entry){
    Node<T>* temp = new Node<T>(entry, nullptr, tail);

    if(head == nullptr)
        head = temp;

    //old tail becomes second to last
    if(tail != nullptr)
        tail->next = temp;

    //set new tail
    tail = temp;

    ++numberOfElements;
}

template<typename T>
void DoublyLinkedList<T>::removeFront(){
    if(head != nullptr){
        Node<T>* temp = head->next;
        delete head;
        head = temp;

        if(head != nullptr)
            head->prev = nullptr;
        //empty list - reset tail
        else
            tail = nullptr;

        --numberOfElements;
    }
}

template<typename T>
void DoublyLinkedList<T>::removeBack(){
    if(tail != nullptr){
        Node<T>* temp = tail->prev;
        delete tail;
        tail = temp;

        if(tail != nullptr)
            tail->next = nullptr;
        else
            head = nullptr;

        --numberOfElements;
    }
}

template<typename T>
const T& DoublyLinkedList<T>::getFront() const {
    return head->data;
}

template<typename T>
const T& DoublyLinkedList<T>::getBack() const {
    return tail->data;
}

template<typename T>
const T& DoublyLinkedList<T>::getAt(const Iterator& itr) const {
    return itr.peek();
}

template<typename T>
void DoublyLinkedList<T>::insertNextTo(const T& target, const T& newEntry){
    Iterator itr;
    for(itr = begin(); itr != end(); ++itr)
        //target found
        if(itr.peek() == target){
            //a new node will be inserted between these two
            Node<T>* newPrev = const_cast<Node<T>*>(itr.getCurrent());
            Node<T>* newNext = newPrev->next;

            Node<T>* temp = new Node<T>(newEntry, newNext, newPrev);
            newPrev->next = temp;

            if(newNext != nullptr)
                newNext->prev = temp;

            //if new Next is null that means that the new insertion is the new tail
            else tail = temp;

            ++numberOfElements;
            return;
        }
}

template<typename T>
void DoublyLinkedList<T>::insertPrevTo(const T& target, const T& newEntry){
    Iterator itr;
    for(itr = begin(); itr != end(); ++itr)
        //target found
        if(itr.peek() == target){
            //a new node will be inserted between these two
            Node<T>* newNext = const_cast<Node<T>*>(itr.getCurrent());
            Node<T>* newPrev = newNext->prev;

            Node<T>* temp = new Node<T>(newEntry, newNext, newPrev);
            newNext->prev = temp;

            if(newPrev != nullptr)
                newPrev->next = temp;

            //if newPrev is null that means that the new insertion is the new head
            else head = temp;

            ++numberOfElements;
            return;
        }
}

//insert directly from the Iterator's current position
template<typename T>
void DoublyLinkedList<T>::insertNextTo(const Iterator& itr, const T& newEntry){

    //a new node will be inserted between these two
    Node<T>* newPrev = const_cast<Node<T>*>(itr.getCurrent());
    Node<T>* newNext = newPrev->next;

    Node<T>* temp = new Node<T>(newEntry, newNext, newPrev);
    newPrev->next = temp;

    if(newNext != nullptr)
        newNext->prev = temp;

    else tail = temp;

    ++numberOfElements;
}

template<typename T>
void DoublyLinkedList<T>::insertPrevTo(const Iterator& itr, const T& newEntry){
    //a new node will be inserted between these two
    Node<T>* newNext = const_cast<Node<T>*>(itr.getCurrent());
    Node<T>* newPrev = newNext->prev;

    Node<T>* temp = new Node<T>(newEntry, newNext, newPrev);
    newNext->prev = temp;

    if(newPrev != nullptr)
        newPrev->next = temp;

    else head = temp;

    ++numberOfElements;
}

template<typename T>
void DoublyLinkedList<T>::remove(const T& target){
    Iterator itr;
    for(itr = begin(); itr != end(); ++itr){
        if(itr.peek() == target){

            Node<T>* current = const_cast<Node<T>*>(itr.getCurrent());

            //first one
            if(current == head)
                removeFront();
            //tail
            else if(current == tail)
                removeBack();
            //middle
            else{
                //hold onto the neighbors
                Node<T>* prev = current->prev;
                Node<T>* next = current->next;

                delete current;
                current = nullptr;

                //relink list
                prev->next = next;
                next->prev = prev;
            }
            --numberOfElements;
            break;
        }
    }
}

template<typename T>
void DoublyLinkedList<T>::removeAt(Iterator& itr){

    Node<T>* current = const_cast<Node<T>*>(itr.getCurrent());

    //shift iterator to next in position
    ++itr;

    //first one
    if(current == head)
        removeFront();
    //tail
    else if(current == tail)
        removeBack();
    //middle
    else{
        //hold onto the neighbors
        Node<T>* prev = current->prev;
        Node<T>* next = current->next;

        delete current;
        current = nullptr;

        //relink list
        prev->next = next;
        next->prev = prev;
    }
    --numberOfElements;
}

template<typename T>
void DoublyLinkedList<T>::display() const{
    Node<T>* current = head;
    while(current != nullptr){
        std::cout << current->data << '\n';
        current = current->next;
    }
}

template<typename T>
void DoublyLinkedList<T>::displayReversed() const{
    Node<T>* current = tail;
    while(current != nullptr){
        std::cout << current->data << '\n';
        current = current->prev;
    }
}

template<typename T>
void DoublyLinkedList<T>::clear(){
    //iterate through entire list
    while(head != nullptr){
        Node<T>* current = head;
        head = current->next;
        delete current;
        current = nullptr;
    }
    numberOfElements = 0;
}

template<typename T>
bool DoublyLinkedList<T>::isEmpty() const{
    return head == nullptr;
}

#endif

HashTable.h

/*
    A Generic Hash Table that uses
    AVL trees for chaining. AVL Tree is overkill, a vector would
    be better. AVL tree was used for fun.

    Hash Table always has a prime capacity to avoid
    clustering of items from purposeful assualts.
*/

#ifndef HASH_TABLE
#define HASH_TABLE

#include "../AVL/AVL.h"
#include <iostream>
#include <cmath>

using std::cout;
using std::endl;

//container type, element type
template<typename T>
class HashTable{
    private:
        int capacity;
        int minCapacity = 11;
        int numberOfElements = 0;
        double low, high;

        AVL<T>* container;

        unsigned hash(const T& value){
            return value % capacity;
        }

        double loadFactor(){
            return static_cast<double>(numberOfElements) / capacity;
        }

        void rehash(const T& entry){
            int pos = hash(entry);

            //insert at bucket
            container[pos].insert(entry);
        }

        void resize(int newCap){

            cout <<  capacity <<", RESIZE: " << newCap << endl;
            //hold referene to old container
            AVL<T>* temp = container;
            int oldCap = capacity;

            container = new AVL<T>[newCap];
            capacity = newCap;

            //go through each bucket
            for(int bucket = 0; bucket < oldCap; bucket++){
                //iterate through all items in a bucket
                typename AVL<T>::Iterator itr;
                itr = temp[bucket].begin();

                while(itr.hasNext())
                    //rehash into new container
                    rehash(itr.next());
            }
            delete[] temp;
        }

        int nextPrimeCap(int reference){
            int p = reference;
            while(!isPrime(p))
                p++;
            return p;
        }

        //n will never be 2
        bool isPrime(int n){
            for(int i = 2; i < sqrt(n); i++)
                if(n % i == 0)
                    return false;
            return true;
        }

    public:
        //Simplifies accessing individual elements outside the hash table.
        //This can be used to check if an obtained element is valid
        //so it can accessed/modified.
        class Element{
            public:
                Element(){
                    valid = false;
                }
                Element(T* data, bool valid){
                    this->data = data;
                    this->valid = valid;
                }
                T* data;
                bool valid;
        };

        HashTable(){
            low = 0.1;
            high = 2.0;
            capacity = minCapacity;
            container = new AVL<T>[capacity];
        }

        HashTable(double low, double high){
            this->low = low;
            this->high = high;
            capacity = minCapacity;
            container = new AVL<T>[capacity];
        }

        ~HashTable(){
            if(container)
                delete[] container;
        }

        void insert(const T& entry){
            numberOfElements++;
            int pos = hash(entry);

            //if it doesn't exist in the table then insert
            if(!get(entry).valid){
                //insert at bucket
                container[pos].insert(entry);

                //resize if need
                if(numberOfElements > minCapacity && loadFactor() > high)
                    resize(nextPrimeCap(capacity*2));
            }
        }

        void remove(const T& target){
            //remove if target is found
            if(get(target).valid){
                numberOfElements--;
                int pos = hash(target);

                //remove from bucket
                container[pos].remove(target);

                //resize if need
                if(numberOfElements > minCapacity && loadFactor() < low)
                    resize(nextPrimeCap(capacity/2));
            }
        }

        //Find an element.
        const Element get(const T& target){
            int pos = hash(target);
            bool found = container[pos].find(target);
            if(found){
                T* data = const_cast<T*>(&container[pos].getFoundData());
                return Element(data, true);
            }
            //invalid Element
            return Element();
        }

        void display(){
            //display each bucket
            for(int i = 0; i < capacity; i++){
                cout << "Bucket " << i << endl;
                container[i].display();
                cout << endl;
            }
        }
};

#endif

priorityQueueLL.h

#ifndef PRIORITYQUEUELL_H
#define PRIORITYQUEUELL_H

#include "doublyLinkedList.h"

template<typename T>
class PriorityQueueLL{

    //display
    friend std::ostream& operator<<(std::ostream& os, const PriorityQueueLL& pq){
        os << pq.container;
        return os;
    }

    private:
        DoublyLinkedList<T> container;

    public:
        void insert(const T& entry);
        void update(const T& entry);

        const T extractMin();
        void display() const;
        const int size() const;
        bool empty() const;

};

template<typename T>
void PriorityQueueLL<T>::insert(const T& entry){

    //empty container
    if(container.isEmpty())
        container.addFront(entry);

    //greater than last
    else if(entry >= container.getBack())
        container.addBack(entry);

    else{
        typename DoublyLinkedList<T>::Iterator itr;
        for(itr = container.begin(); itr != container.end(); ++itr)
            //sorted position found
            if(entry < itr.peek()){
                container.insertPrevTo(itr, entry);
                return;
            }

        //add to the back - entry has the greatest value
        container.addBack(entry);
    }
}

//updates by removing the target and then reinserting it to keep
//priority queue order
template<typename T>
void PriorityQueueLL<T>::update(const T& target){
    //find entry
    typename DoublyLinkedList<T>::Iterator itr;
    for(itr = container.begin(); itr != container.end(); ++itr){
        //found
        if(target == itr.peek()){
            container.removeAt(itr);
            this->insert(target);
            break;
        }
    }
}

template<typename T>
const T PriorityQueueLL<T>::extractMin(){
    T temp = container.getFront();
    container.removeFront();
    return temp;
}

template<typename T>
void PriorityQueueLL<T>::display() const{
    container.display();
}

template<typename T>
const int PriorityQueueLL<T>::size() const{
    return container.size();
}

template<typename T>
bool PriorityQueueLL<T>::empty() const{
    return container.isEmpty();
}

#endif

quadHashTable.h

#ifndef QUAD_HASH
#define QUAD_HASH

#include <iostream>
#include <cmath>

using std::cout;
using std::endl;

template<typename T>
class QuadHashTable{

    private:
        class Bucket{
            public:
                T value;
                bool occupied = false;
                bool deleted = false;
        };

        Bucket* container;
        int capacity;
        int numberOfElements = 0;

        int nextPrimeCap(int reference){
            int p = reference;
            while(!isPrime(p))
                p++;
            return p;
        }

        //n will never be 2
        bool isPrime(int n){
            for(int i = 2; i < sqrt(n); i++)
                if(n % i == 0)
                    return false;
            return true;
        }

        //used only by resize()
        void rehash(Bucket& b){
            int hash = b.value % capacity;
            int pos = hash;
            int i = 0;

            //find unoccupied bucket
            while(container[pos].occupied){
                i++;
                pos = (hash + i*i) % capacity;
            }
            //fillup bucket
            container[pos] = b;
        }

        void resize(int newCap){
            //have reference to old container
            Bucket* temp = container;
            int oldCap = capacity;

            //setup new container
            capacity = newCap;
            container = new Bucket[capacity];

            //rehash values into new container
            for(int i = 0; i < oldCap; i++)
                if(temp[i].occupied){
                    rehash(temp[i]);          //reuse insert with the updated container
                }

            //delete old copies
            delete temp;
        }

    public:
        QuadHashTable(){
            capacity = 13;
            container = new Bucket[capacity];
        }
        QuadHashTable(int cap){
            capacity = (cap < 13) ? 17 : nextPrimeCap(cap);
            container = new Bucket[capacity];
        }
        ~QuadHashTable(){
            delete[] container;
            container = nullptr;
        }

        void insert(const T& entry){
            numberOfElements++;
            int hash = entry % capacity;
            int pos = hash;
            int i = 0;

            //find unoccupied bucket or one that is deleted
            while(container[pos].occupied && !container[pos].deleted){
                i++;
                pos = (hash + i*i) % capacity;
            }
            //fillup bucket - reset deleted status
            container[pos].value = entry;
            container[pos].occupied = true;
            container[pos].deleted = false;

            //expand capacity if needed
            if(numberOfElements >= capacity/2){
                int newCap = nextPrimeCap(capacity*2);
                resize(newCap);
            }
        }

        //return the index position of target in the hash table
        int find(const T& target){
            int hash = target % capacity;
            int pos = hash;
            int i = 0;

            //search until there is an empty bucket
            while(container[pos].occupied){
                //found
                if(!container[pos].deleted && container[pos].value == target)
                    return pos;
                i++;
                pos = (hash + i*i) % capacity;
            }
            //empty bucket found, target does not exist
            return -1;
        }

        bool contains(const T& target){
            return find(target) != -1;
        }

        void remove(const T& target){
            int pos = find(target);

            //mark as deleted if found
            if(pos != -1){
                numberOfElements--;

                //deleted buckets are still occupied by "dead" values
                container[pos].deleted = true;

                //shrink if needed
                if(numberOfElements <= capacity/8){
                    int newCap = nextPrimeCap(capacity/2);
                    resize(newCap);
                }
            }
        }

        int size(){
            return numberOfElements;
        }

        //reset hash table
        void clear(){
            delete[] container;
            capacity = 13;
            numberOfElements = 0;
            container = new Bucket[capacity];
        }

        void display(){
            for(int i = 0; i < capacity; i++){
                cout << i << ": ";
                if(container[i].occupied && !container[i].deleted)
                    cout << container[i].value;
                cout << endl;
            }
        }
};

#endif

queueLL.h

#ifndef QUEUELL_H
#define QUEUELL_H

#include "doublyLinkedList.h"

template<typename T>
class QueueLL{

    //display
    friend std::ostream& operator<<(std::ostream& os, const QueueLL& q){
        os << q.container;
        return os;
    }

    private:
        DoublyLinkedList<T> container;

    public:
        void enqueue(const T& entry);
        const T dequeue();
        const int size() const;
        bool empty() const;
};

template<typename T>
void QueueLL<T>::enqueue(const T& entry){
    container.addBack(entry);
}

template<typename T>
const T QueueLL<T>::dequeue(){
    const T temp = container.getFront();
    container.removeFront();
    return temp;
}

template<typename T>
const int QueueLL<T>::size() const{
    return container.size();
}

template<typename T>
bool QueueLL<T>::empty() const{
    return container.isEmpty();
}

#endif

stackLL.h

#ifndef STACKLL_H
#define STACKLL_H

#include "doublyLinkedList.h"

template<typename T>
class StackLL{

    //display
    friend std::ostream& operator<<(std::ostream& os, const StackLL& s){
        os << s.container;
        return os;
    }

    private:
        DoublyLinkedList<T> container;


    public:
        void push(const T& entry);
        const T pop();
        const int size() const;
        bool empty() const;

        //////////////////////////////
        //additional "weird" methods:
        //////////////////////////////

        //remove and return the kth item from the top of the stack.
        T popkth(int k);

        //decimate: remove every 10th item from the stack
        void decimate();

        //add entry to stack, but insert it
        //right after the current ith item from the top
        //(and before the i+1 item).
        void insertAt(const T& entry, int i);
};

template<typename T>
void StackLL<T>::push(const T& entry){
    container.addFront(entry);
}

template<typename T>
const T StackLL<T>::pop(){
    const T temp = container.getFront();
    container.removeFront();
    return temp;
}

template<typename T>
const int StackLL<T>::size() const{
    return container.size();
}

template<typename T>
bool StackLL<T>::empty() const{
    return container.isEmpty();
}

template<typename T>
T StackLL<T>::popkth(int k){
    T temp;
    int counter = 0;
    typename DoublyLinkedList<T>::Iterator itr;
    for(itr = container.begin(); itr != container.end(); itr++){
        if(counter == k){
            temp = itr.peek();
            container.removeAt(itr);
            break;
        }
        ++counter;
    }
    return temp;
}

template<typename T>
void StackLL<T>::decimate(){
    int counter = 1;
    typename DoublyLinkedList<T>::Iterator itr;
    for(itr = container.begin(); itr != container.end(); itr++){
        //every tenth
        if(counter == 10){
            container.removeAt(itr);

            //check if we reached the end of the container
            //removeAt modified itr by shifting it the next pos.
            if(itr == nullptr)
                return;

            //reset counter
            counter = 1;
        }
        ++counter;
    }
}

template<typename T>
void StackLL<T>::insertAt(const T& entry, int i){
    int counter = 0;
    typename DoublyLinkedList<T>::Iterator itr;
    for(itr = container.begin(); itr != container.end(); ++itr){
        if(counter == i){
            container.insertNextTo(itr, entry);
            break;
        }
        ++counter;
    }
}

#endif

These are some basic data structures that I have done in the past during my coursework. Some data structures use other data structures in this gist. You can take a look at the code and use it for reference or for your own needs.