C++ Data Structures | 'Implementing from Scratch' Linked List/Tree/Hash Table

1. Linked List

Here is detailed implementation code using C++. Define a class to encapsulate data and functionality, process data with loops, and perform branching with conditionals. Understand the role of each part while examining the code.

template <typename T>
class LinkedList {
private:
    struct Node {
        T data;
        Node* next;
        Node(T val) : data(val), next(nullptr) {}
    };
    
    Node* head;
    int size;
    
public:
    LinkedList() : head(nullptr), size(0) {}
    
    ~LinkedList() {
        while (head) {
            Node* temp = head;
            head = head->next;
            delete temp;
        }
    }
    
    void push_front(T value) {
        Node* newNode = new Node(value);
        newNode->next = head;
        head = newNode;
        size++;
    }
    
    void push_back(T value) {
        Node* newNode = new Node(value);
        
        if (!head) {
            head = newNode;
        } else {
            Node* curr = head;
            while (curr->next) {
                curr = curr->next;
            }
            curr->next = newNode;
        }
        size++;
    }
    
    bool remove(T value) {
        if (!head) return false;
        
        if (head->data == value) {
            Node* temp = head;
            head = head->next;
            delete temp;
            size--;
            return true;
        }
        
        Node* curr = head;
        while (curr->next && curr->next->data != value) {
            curr = curr->next;
        }
        
        if (curr->next) {
            Node* temp = curr->next;
            curr->next = curr->next->next;
            delete temp;
            size--;
            return true;
        }
        
        return false;
    }
    
    void print() {
        Node* curr = head;
        while (curr) {
            cout << curr->data << " -> ";
            curr = curr->next;
        }
        cout << "null" << endl;
    }
};

2. Binary Search Tree (BST)

Here is detailed implementation code using C++. Define a class to encapsulate data and functionality and perform branching with conditionals. Understand the role of each part while examining the code.

template <typename T>
class BST {
private:
    struct Node {
        T data;
        Node* left;
        Node* right;
        
        Node(T val) : data(val), left(nullptr), right(nullptr) {}
    };
    
    Node* root;
    
    Node* insertHelper(Node* node, T value) {
        if (!node) {
            return new Node(value);
        }
        
        if (value < node->data) {
            node->left = insertHelper(node->left, value);
        } else if (value > node->data) {
            node->right = insertHelper(node->right, value);
        }
        
        return node;
    }
    
    bool searchHelper(Node* node, T value) {
        if (!node) return false;
        if (node->data == value) return true;
        
        if (value < node->data) {
            return searchHelper(node->left, value);
        } else {
            return searchHelper(node->right, value);
        }
    }
    
    void inorderHelper(Node* node) {
        if (!node) return;
        
        inorderHelper(node->left);
        cout << node->data << " ";
        inorderHelper(node->right);
    }
    
    void destroyTree(Node* node) {
        if (!node) return;
        
        destroyTree(node->left);
        destroyTree(node->right);
        delete node;
    }
    
public:
    BST() : root(nullptr) {}
    
    ~BST() {
        destroyTree(root);
    }
    
    void insert(T value) {
        root = insertHelper(root, value);
    }
    
    bool search(T value) {
        return searchHelper(root, value);
    }
    
    void inorder() {
        inorderHelper(root);
        cout << endl;
    }
};

int main() {
    BST<int> tree;
    tree.insert(50);
    tree.insert(30);
    tree.insert(70);
    tree.insert(20);
    tree.insert(40);
    
    tree.inorder();  // 20 30 40 50 70
    cout << tree.search(40) << endl;  // 1
}

3. Hash Table

Here is detailed implementation code using C++. Define a class to encapsulate data and functionality, ensure stability through error handling, process data with loops, and perform branching with conditionals. Understand the role of each part while examining the code.

template <typename K, typename V>
class HashTable {
private:
    struct Entry {
        K key;
        V value;
        bool occupied;
        
        Entry() : occupied(false) {}
    };
    
    vector<Entry> table;
    int capacity;
    int size;
    
    int hash(const K& key) {
        return std::hash<K>{}(key) % capacity;
    }
    
    int probe(int index, int i) {
        return (index + i) % capacity;  // Linear probing
    }
    
public:
    HashTable(int cap = 10) : capacity(cap), size(0) {
        table.resize(capacity);
    }
    
    void insert(const K& key, const V& value) {
        if (size >= capacity * 0.7) {
            rehash();
        }
        
        int index = hash(key);
        int i = 0;
        
        while (table[probe(index, i)].occupied) {
            if (table[probe(index, i)].key == key) {
                table[probe(index, i)].value = value;
                return;
            }
            i++;
        }
        
        int pos = probe(index, i);
        table[pos].key = key;
        table[pos].value = value;
        table[pos].occupied = true;
        size++;
    }
    
    bool get(const K& key, V& value) {
        int index = hash(key);
        int i = 0;
        
        while (table[probe(index, i)].occupied) {
            if (table[probe(index, i)].key == key) {
                value = table[probe(index, i)].value;
                return true;
            }
            i++;
        }
        
        return false;
    }
    
    void rehash() {
        vector<Entry> oldTable = table;
        capacity *= 2;
        table.clear();
        table.resize(capacity);
        size = 0;
        
        for (const auto& entry : oldTable) {
            if (entry.occupied) {
                insert(entry.key, entry.value);
            }
        }
    }
};

Summary

Key Points

1. Linked List: Dynamic size, O(1) insertion at front
2. BST: O(log n) search/insert (balanced), O(n) worst case
3. Hash Table: O(1) average, collision handling crucial
4. Implementation: Understand memory management and edge cases

When to Use

✅ Use custom implementation when:

• Learning data structures
• Interview preparation
• Constrained environments (no STL)
• Need specific customization

❌ Use STL when:

• Production code
• Time-critical projects
• Need proven reliability
• Standard operations sufficient

Best Practices

• ✅ Handle memory properly (destructors)
• ✅ Check edge cases (empty, single element)
• ✅ Consider cache locality
• ❌ Don’t reinvent wheel in production
• ❌ Don’t forget memory leaks

---

Related Articles

• C++ STL Queue/Stack
• C++ STL Set/Unordered Set
• C++ Algorithm Heap

Master data structure implementation for deeper understanding! 🚀