Comprehensive Analysis of C++ Data Structures: 20 Core Implementation Solutions from Linked Lists to Graph Theory

1. Advanced Practice of Linear Data Structures

1.1 Deep Implementation of Linked List

The linked list, as the most basic dynamic data structure, has a wide range of variants and application scenarios. Below is the complete implementation of a doubly linked list:

#include <iostream>
#include <memory>

template<typename T>
class Node {
public:
    T data;
    std::unique_ptr<Node<T>> next;
    Node<T>* prev;
    
    Node(const T& val) : data(val), next(nullptr), prev(nullptr) {}
};

template<typename T>
class LinkedList {
public:
    LinkedList() : head(nullptr), tail(nullptr), size(0) {}
    
    void insert(const T& value) {
        auto new_node = std::make_unique<Node<T>>(value);
        if (head == nullptr) {
            head = new_node.get();
            tail = head;
        } else {
            tail->next = new_node;
            new_node->prev = tail;
            tail = new_node.get();
        }
        size++;
    }
    
    bool deleteValue(const T& value) {
        Node<T>* current = head;
        while (current != nullptr) {
            if (current->data == value) {
                if (current->prev) current->prev->next = current->next.release();
                else head = current->next.release();
                
                if (current->next) current->next->prev = current->prev;
                else tail = current->prev;
                
                size--;
                return true;
            }
            current = current->next.get();
        }
        return false;
    }
    
    void display() const {
        Node<T>* current = head;
        while (current != nullptr) {
            std::cout << current->data << " ";
            current = current->next.get();
        }
        std::cout << std::endl;
    }
    
    size_t getSize() const { return size; }
    
private:
    Node<T>* head;
    Node<T>* tail;
    size_t size;
};

int main() {
    LinkedList<int> list;
    list.insert(10);
    list.insert(20);
    list.insert(30);
    
    std::cout << "Linked List Content: ";
    list.display();
    
    std::cout << "After Deleting 20: ";
    list.deleteValue(20);
    list.display();
    
    return 0;
}

1.2 Advanced Applications of Stacks and Queues

Stacks and queues, as constrained data structures, have various implementations in practical programming:

#include <iostream>
#include <stack>
#include <queue>
#include <deque>
#include <memory>

// Stack functionality implemented using deque
class StackUsingDeque {
private:
    std::deque<int> deque;
    
public:
    void push(int value) { deque.push_back(value); }
    
    int pop() {
        int value = deque.back();
        deque.pop_back();
        return value;
    }
    
    int top() const { return deque.back(); }
    
    bool isEmpty() const { return deque.empty(); }
};

// Priority Queue implementation
class PriorityQueue {
private:
    std::multimap<int, std::string> data;
    
public:
    void enqueue(int priority, const std::string& task) {
        data.insert({priority, task});
    }
    
    std::string dequeue() {
        if (data.empty()) return "";
        auto it = data.begin();
        std::string task = it->second;
        data.erase(it);
        return task;
    }
};

// Circular Queue implementation
class CircularQueue {
private:
    int* data;
    int front;
    int rear;
    int capacity;
    int count;
    
public:
    CircularQueue(int size) : capacity(size), front(0), rear(0), count(0) {
        data = new int[capacity];
    }
    
    ~CircularQueue() { delete[] data; }
    
    void enqueue(int value) {
        if (isFull()) throw std::overflow_error("Queue is full");
        data[rear] = value;
        rear = (rear + 1) % capacity;
        count++;
    }
    
    int dequeue() {
        if (isEmpty()) throw std::underflow_error("Queue is empty");
        int value = data[front];
        front = (front + 1) % capacity;
        count--;
        return value;
    }
    
    bool isEmpty() const { return count == 0; }
    bool isFull() const { return count == capacity; }
};

int main() {
    // Stack implementation test
    StackUsingDeque stack;
    stack.push(10);
    stack.push(20);
    std::cout << "Top element of stack: " << stack.top() << std::endl;
    
    // Priority Queue test
    PriorityQueue pq;
    pq.enqueue(3, "Low priority task");
    pq.enqueue(1, "High priority task");
    std::cout << "Dequeued task: " << pq.dequeue() << std::endl;
    
    // Circular Queue test
    CircularQueue cq(5);
    cq.enqueue(10);
    cq.enqueue(20);
    std::cout << "Circular Queue Dequeue: " << cq.dequeue() << std::endl;
    
    return 0;
}

2. Tree Structures and Algorithm Implementations

2.1 Complete Implementation of Binary Search Tree

The binary search tree is the most commonly used type of tree structure, supporting efficient search, insertion, and deletion operations:

#include <iostream>
#include <memory>
#include <stack>
#include <queue>

template<typename T>
class BST {
private:
    struct Node {
        T data;
        std::unique_ptr<Node> left;
        std::unique_ptr<Node> right;
        Node(const T& val) : data(val), left(nullptr), right(nullptr) {}
    };
    
    Node* root;
    
    Node* findMin(Node* node) {
        while (node && node->left) node = node->left.get();
        return node;
    }
    
    Node* deleteNode(Node* node, const T& value) {
        if (!node) return nullptr;
        
        if (value < node->data) {
            node->left = deleteNode(node->left.release(), value);
        } else if (value > node->data) {
            node->right = deleteNode(node->right.release(), value);
        } else {
            if (!node->left) {
                return node->right.release();
            } else if (!node->right) {
                return node->left.release();
            } else {
                Node* min = findMin(node->right.get());
                node->data = min->data;
                node->right = deleteNode(node->right.release(), min->data);
            }
        }
        return node;
    }
    
public:
    BST() : root(nullptr) {}
    
    void insert(const T& value) {
        if (!root) {
            root = new Node(value);
            return;
        }
        
        Node* current = root.get();
        while (true) {
            if (value < current->data) {
                if (!current->left) {
                    current->left = std::make_unique<Node>(value);
                    break;
                }
                current = current->left.get();
            } else if (value > current->data) {
                if (!current->right) {
                    current->right = std::make_unique<Node>(value);
                    break;
                }
                current = current->right.get();
            } else {
                // Value already exists, handling can be adjusted as needed
                break;
            }
        }
    }
    
    void deleteNode(const T& value) {
        root = deleteNode(root.release(), value);
    }
    
    void inorder() {
        std::stack<Node*> stack;
        Node* current = root.get();
        
        while (current || !stack.empty()) {
            while (current) {
                stack.push(current);
                current = current->left.get();
            }
            
            current = stack.top();
            stack.pop();
            std::cout << current->data << " ";
            current = current->right.get();
        }
        std::cout << std::endl;
    }
    
    void bfs() {
        if (!root) return;
        
        std::queue<Node*> queue;
        queue.push(root.get());
        
        while (!queue.empty()) {
            Node* current = queue.front();
            queue.pop();
            
            std::cout << current->data << " ";
            
            if (current->left) queue.push(current->left.get());
            if (current->right) queue.push(current->right.get());
        }
        std::cout << std::endl;
    }
};

int main() {
    BST<int> tree;
    tree.insert(50);
    tree.insert(30);
    tree.insert(70);
    tree.insert(20);
    tree.insert(40);
    tree.insert(60);
    tree.insert(80);
    
    std::cout << "Inorder Traversal: ";
    tree.inorder();
    
    std::cout << "Breadth-First Traversal: ";
    tree.bfs();
    
    tree.deleteNode(30);
    std::cout << "Inorder Traversal after Deleting 30: ";
    tree.inorder();
    
    return 0;
}

2.2 Implementation of AVL Trees and Red-Black Trees

Balanced binary search trees are crucial in high-performance scenarios. Below is a simplified implementation of an AVL tree:

#include <algorithm>
#include <iostream>

template<typename T>
class AVLNode {
public:
    T data;
    AVLNode* left;
    AVLNode* right;
    int height;
    
    AVLNode(const T& val) : data(val), left(nullptr), right(nullptr), height(1) {}
};

template<typename T>
class AVLTree {
public:
    AVLNode<T>* root;
    
    AVLTree() : root(nullptr) {}
    
    int getHeight(AVLNode<T>* node) {
        return node ? node->height : 0;
    }
    
    int getBalanceFactor(AVLNode<T>* node) {
        return node ? getHeight(node->left) - getHeight(node->right) : 0;
    }
    
    AVLNode<T>* leftRotate(AVLNode<T>* z) {
        AVLNode<T>* y = z->right;
        z->right = y->left;
        y->left = z;
        
        z->height = 1 + std::max(getHeight(z->left), getHeight(z->right));
        y->height = 1 + std::max(getHeight(y->left), getHeight(y->right));
        
        return y;
    }
    
    AVLNode<T>* rightRotate(AVLNode<T>* y) {
        AVLNode<T>* x = y->left;
        y->left = x->right;
        x->right = y;
        
        y->height = 1 + std::max(getHeight(y->left), getHeight(y->right));
        x->height = 1 + std::max(getHeight(x->left), getHeight(x->right));
        
        return x;
    }
    
    void insert(const T& value) {
        root = insertNode(root, value);
    }
    
    AVLNode<T>* insertNode(AVLNode<T>* node, const T& value) {
        if (!node) return new AVLNode<T>(value);
        
        if (value < node->data) {
            node->left = insertNode(node->left, value);
        } else if (value > node->data) {
            node->right = insertNode(node->right, value);
        } else {
            return node;
        }
        
        node->height = 1 + std::max(getHeight(node->left), getHeight(node->right));
        
        int balance = getBalanceFactor(node);
        
        // Left-Left case
        if (balance > 1 && value < node->left->data) {
            return rightRotate(node);
        }
        
        // Right-Right case
        if (balance < -1 && value > node->right->data) {
            return leftRotate(node);
        }
        
        // Left-Right case
        if (balance > 1 && value > node->left->data) {
            node->left = leftRotate(node->left);
            return rightRotate(node);
        }
        
        // Right-Left case
        if (balance < -1 && value < node->right->data) {
            node->right = rightRotate(node->right);
            return leftRotate(node);
        }
        
        return node;
    }
    
    void preorder() {
        preorderTraversal(root);
        std::cout << std::endl;
    }
    
private:
    void preorderTraversal(AVLNode<T>* node) {
        if (node) {
            std::cout << node->data << " ";
            preorderTraversal(node->left);
            preorderTraversal(node->right);
        }
    }
};

int main() {
    AVLTree<int> tree;
    tree.insert(10);
    tree.insert(20);
    tree.insert(30);
    tree.insert(40);
    tree.insert(50);
    tree.insert(60);
    
    std::cout << "Preorder Traversal: ";
    tree.preorder();
    
    return 0;
}

3. Graph Structures and Algorithm Implementations

3.1 Basic Representation and Traversal of Graphs

Graph structures are indispensable in modeling complex relationships. Below are implementations of adjacency lists and adjacency matrices:

#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <stack>

class Graph {
private:
    int vertices;
    std::vector<std::vector<int>> adjacencyMatrix;
    std::vector<std::list<int>> adjacencyList;
    
public:
    Graph(int V) : vertices(V), 
        adjacencyMatrix(V, std::vector<int>(V, 0)),
        adjacencyList(V) {}
    
    void addEdgeMatrix(int src, int dest, int weight=1) {
        if (src >= 0 && src < vertices && dest >= 0 && dest < vertices) {
            adjacencyMatrix[src][dest] = weight;
            // For undirected graph
            adjacencyMatrix[dest][src] = weight;
        }
    }
    
    void addEdgeList(int src, int dest) {
        if (src >= 0 && src < vertices && dest >= 0 && dest < vertices) {
            adjacencyList[src].push_back(dest);
            // For undirected graph
            adjacencyList[dest].push_back(src);
        }
    }
    
    void bfsMatrix(int start) {
        std::vector<bool> visited(vertices, false);
        std::queue<int> queue;
        
        visited[start] = true;
        queue.push(start);
        
        while (!queue.empty()) {
            int current = queue.front();
            queue.pop();
            std::cout << current << " ";
            
            for (int i = 0; i < vertices; ++i) {
                if (!visited[i] && adjacencyMatrix[current][i] == 1) {
                    visited[i] = true;
                    queue.push(i);
                }
            }
        }
    }
    
    void bfsList(int start) {
        std::vector<bool> visited(vertices, false);
        std::queue<int> queue;
        
        visited[start] = true;
        queue.push(start);
        
        while (!queue.empty()) {
            int current = queue.front();
            queue.pop();
            std::cout << current << " ";
            
            for (auto neighbor : adjacencyList[current]) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.push(neighbor);
                }
            }
        }
    }
    
    void dfsMatrix(int start) {
        std::vector<bool> visited(vertices, false);
        std::stack<int> stack;
        
        stack.push(start);
        
        while (!stack.empty()) {
            int current = stack.top();
            stack.pop();
            
            if (!visited[current]) {
                visited[current] = true;
                std::cout << current << " ";
                
                for (int i = vertices - 1; i >= 0; --i) {
                    if (adjacencyMatrix[current][i] == 1 && !visited[i]) {
                        stack.push(i);
                    }
                }
            }
        }
    }
    
    void dfsList(int start) {
        std::vector<bool> visited(vertices, false);
        std::stack<int> stack;
        
        stack.push(start);
        
        while (!stack.empty()) {
            int current = stack.top();
            stack.pop();
            
            if (!visited[current]) {
                std::cout << current << " ";
                visited[current] = true;
                
                for (auto neighbor : adjacencyList[current]) {
                    if (!visited[neighbor]) {
                        stack.push(neighbor);
                    }
                }
            }
        }
    }
};

int main() {
    // Using adjacency matrix
    Graph g1(4);
    g1.addEdgeMatrix(0, 1);
    g1.addEdgeMatrix(0, 2);
    g1.addEdgeMatrix(1, 3);
    g1.addEdgeMatrix(2, 3);
    
    std::cout << "Adjacency Matrix BFS: ";
    g1.bfsMatrix(0);
    std::cout << "\nAdjacency Matrix DFS: ";
    g1.dfsMatrix(0);
    std::cout << std::endl;
    
    // Using adjacency list
    Graph g2(4);
    g2.addEdgeList(0, 1);
    g2.addEdgeList(0, 2);
    g2.addEdgeList(1, 3);
    g2.addEdgeList(2, 3);
    
    std::cout << "Adjacency List BFS: ";
    g2.bfsList(0);
    std::cout << "\nAdjacency List DFS: ";
    g2.dfsList(0);
    std::cout << std::endl;
    
    return 0;
}

3.2 Implementation of Advanced Graph Algorithms

Shortest path and minimum spanning tree algorithms have important applications in graph theory:

#include <iostream>
#include <vector>
#include <queue>
#include <climits>

// Dijkstra's algorithm implementation
void dijkstra(const std::vector<std::vector<int>>& graph, int start) {
    int vertices = graph.size();
    std::vector<int> dist(vertices, INT_MAX);
    std::vector<bool> visited(vertices, false);
    
    dist[start] = 0;
    
    for (int i = 0; i < vertices - 1; ++i) {
        int min_dist = INT_MAX;
        int current = -1;
        
        for (int v = 0; v < vertices; ++v) {
            if (!visited[v] && dist[v] < min_dist) {
                min_dist = dist[v];
                current = v;
            }
        }
        
        visited[current] = true;
        
        for (int v = 0; v < vertices; ++v) {
            if (!visited[v] && graph[current][v] && 
                dist[current] != INT_MAX &&&
                dist[current] + graph[current][v] < dist[v]) {
                dist[v] = dist[current] + graph[current][v];
            }
        }
    }
    
    std::cout << "Shortest distances from start " << start << ":\n";
    for (int i = 0; i < vertices; ++i) {
        std::cout << "Distance to " << i << ": " << dist[i] << "\n";
    }
}

// Prim's algorithm implementation for minimum spanning tree
void prim(const std::vector<std::vector<int>>& graph) {
    int vertices = graph.size();
    std::vector<int> parent(vertices, -1);
    std::vector<int> key(vertices, INT_MAX);
    std::vector<bool> mstSet(vertices, false);
    
    key[0] = 0;
    
    for (int count = 0; count < vertices - 1; ++count) {
        int min_key = INT_MAX;
        int current = -1;
        
        for (int v = 0; v < vertices; ++v) {
            if (!mstSet[v] && key[v] < min_key) {
                min_key = key[v];
                current = v;
            }
        }
        
        mstSet[current] = true;
        
        for (int v = 0; v < vertices; ++v) {
            if (graph[current][v] && !mstSet[v] && graph[current][v] < key[v]) {
                parent[v] = current;
                key[v] = graph[current][v];
            }
        }
    }
    
    std::cout << "Minimum spanning tree edges:\n";
    for (int i = 1; i < vertices; ++i) {
        std::cout << parent[i] << " - " << i << "\n";
    }
}

int main() {
    // Dijkstra's algorithm test
    std::vector<std::vector<int>> graph_dijkstra = {
        {0, 4, 0, 0, 0, 0, 0, 8, 0},
        {4, 0, 8, 0, 0, 0, 0, 11, 0},
        {0, 8, 0, 7, 0, 4, 0, 0, 2},
        {0, 0, 7, 0, 9, 14, 0, 0, 0},
        {0, 0, 0, 9, 0, 10, 0, 0, 0},
        {0, 0, 4, 14, 10, 0, 2, 0, 0},
        {0, 0, 0, 0, 0, 2, 0, 1, 6},
        {8, 11, 0, 0, 0, 0, 1, 0, 7},
        {0, 0, 2, 0, 0, 0, 6, 7, 0}
    };
    
    dijkstra(graph_dijkstra, 0);
    
    // Prim's algorithm test
    std::vector<std::vector<int>> graph_prim = {
        {0, 2, 0, 1, 0},
        {2, 0, 3, 2, 4},
        {0, 3, 0, 0, 5},
        {1, 2, 0, 0, 1},
        {0, 4, 5, 1, 0}
    };
    
    prim(graph_prim);
    
    return 0;
}

4. Hash Tables and Set Operations

4.1 Hash Table Implementation and Collision Resolution

Hash tables, as efficient storage and retrieval data structures, rely on hash functions and collision resolution:

#include <iostream>
#include <vector>
#include <list>
#include <algorithm>

template<typename K, typename V>
class HashTable {
private:
    static const int DEFAULT_CAPACITY = 10;
    int capacity;
    int size;
    std::vector<std::list<std::pair<K, V>>> buckets;
    
    int hash(const K& key) const {
        return std::hash<K>{}(key) % capacity;
    }
    
    void rehash() {
        capacity *= 2;
        auto old_buckets = buckets;
        buckets = std::vector<std::list<std::pair<K, V>>>(capacity);
        
        for (auto& bucket : old_buckets) {
            for (auto& element : bucket) {
                int index = hash(element.first);
                buckets[index].push_back(element);
            }
        }
    }
    
public:
    HashTable(int initial_capacity = DEFAULT_CAPACITY) 
        : capacity(initial_capacity), size(0), buckets(capacity) {}
    
    void insert(const K& key, const V& value) {
        int index = hash(key);
        
        for (auto& element : buckets[index]) {
            if (element.first == key) {
                // Key already exists, update value
                element.second = value;
                return;
            }
        }
        
        buckets[index].push_back({key, value});
        size++;
        
        // Load factor check
        if (static_cast<double>(size) / capacity > 0.75) {
            rehash();
        }
    }
    
    V get(const K& key) {
        int index = hash(key);
        for (auto& element : buckets[index]) {
            if (element.first == key) {
                return element.second;
            }
        }
        throw std::out_of_range("Key does not exist");
    }
    
    void remove(const K& key) {
        int index = hash(key);
        auto& bucket = buckets[index];
        
        for (auto it = bucket.begin(); it != bucket.end(); ++it) {
            if (it->first == key) {
                bucket.erase(it);
                size--;
                return;
            }
        }
        throw std::out_of_range("Key does not exist");
    }
};

int main() {
    HashTable<std::string, int> phonebook;
    
    phonebook.insert("Alice", 123456);
    phonebook.insert("Bob", 654321);
    
    std::cout << "Alice's number: " << phonebook.get("Alice") << std::endl;
    
    phonebook.remove("Bob");
    
    return 0;
}

4.2 Union-Find and Bitmap Implementations

Union-Find and bitmaps are efficient data structures for special purposes:

#include <iostream>
#include <vector>
#include <cstring>

// Union-Find implementation
class UnionFind {
private:
    std::vector<int> parent;
    std::vector<int> rank;
    
public:
    UnionFind(int n) : parent(n), rank(n, 0) {
        for (int i = 0; i < n; ++i) parent[i] = i;
    }
    
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // Path compression
        }
        return parent[x];
    }
    
    void unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        
        if (rootX == rootY) return;
        
        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
    }
    
    bool connected(int x, int y) {
        return find(x) == find(y);
    }
};

// Bitmap implementation
class Bitmap {
private:
    std::vector<unsigned char> data;
    size_t size;
    
public:
    Bitmap(size_t n) : size(n) {
        data.resize((n + 8 - 1) / 8, 0);
    }
    
    void set(size_t pos) {
        if (pos >= size) return;
        data[pos / 8] |= (1 << (pos % 8));
    }
    
    void clear(size_t pos) {
        if (pos >= size) return;
        data[pos / 8] &= ~(1 << (pos % 8));
    }
    
    bool test(size_t pos) {
        if (pos >= size) return false;
        return (data[pos / 8] && (1 << (pos % 8))) != 0;
    }
};

int main() {
    // Union-Find test
    UnionFind uf(10);
    uf.unite(1, 2);
    uf.unite(3, 4);
    std::cout << "Are 1 and 2 connected: " << uf.connected(1, 2) << std::endl;
    
    // Bitmap test
    Bitmap bm(100);
    bm.set(50);
    std::cout << "Is bit 50 set: " << bm.test(50) << std::endl;
    
    return 0;
}

This article comprehensively introduces various data structures in C++, from basic linear structures to complex non-linear structures, covering linked lists, stacks, queues, trees, graphs, hash tables, union-find, and bitmaps. Each section includes detailed code implementations and practical application cases, demonstrating the advantages and applicable scenarios of different data structures in solving real-world problems.