Mastering Data Structures in C++: Interview Survival Guide

In coding interviews, you are often asked to implement data structures from scratch rather than using the STL (std::vector, std::map, etc.). This tests your understanding of memory management, pointers, and algorithmic complexity.

This guide provides clean, modern C++ implementations for the “Big 4”: Linked Lists, Trees, Graphs, and Hash Maps.

1. Linked Lists

The classic interview staple. You must be comfortable manipulating next pointers without causing memory leaks or segfaults.

The Node Struct

struct Node {
    int data;
    Node* next;

    Node(int val) : data(val), next(nullptr) {}
};

Reversing a Linked List

This is arguably the most common pointer manipulation question.

Node* reverseList(Node* head) {
    Node* prev = nullptr;
    Node* current = head;
    Node* next = nullptr;

    while (current != nullptr) {
        next = current->next;  // Store next node
        current->next = prev;  // Reverse pointer
        prev = current;        // Move prev forward
        current = next;        // Move current forward
    }
    return prev; // New head
}

2. Binary Search Trees (BST)

Trees are recursive by nature. Most interview solutions will use recursion.

The TreeNode Struct

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

Depth First Search (DFS) Traversals

Knowing the difference between In-Order, Pre-Order, and Post-Order is crucial.

void inorderTraversal(TreeNode* root) {
    if (!root) return;
    
    inorderTraversal(root->left);
    std::cout << root->val << " "; // Process Node
    inorderTraversal(root->right);
}

void preorderTraversal(TreeNode* root) {
    if (!root) return;

    std::cout << root->val << " "; // Process Node
    preorderTraversal(root->left);
    preorderTraversal(root->right);
}

Tip: In-Order traversal of a BST yields sorted values!

3. Graphs

You typically represent graphs using an Adjacency List or Adjacency Matrix. In C++, std::vector<std::vector<int>> is the standard way to implement an adjacency list.

Graph Representation (Adjacency List)

#include <vector>
#include <iostream>

class Graph {
    int V; // Number of vertices
    std::vector<std::vector<int>> adj;

public:
    Graph(int V) : V(V) {
        adj.resize(V);
    }

    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u); // For undirected graph
    }
};

Breadth First Search (BFS)

BFS is used for finding the shortest path in an unweighted graph. Usage of std::queue is mandatory here.

#include <queue>
#include <vector>

void bfs(int startNode, int V, const std::vector<std::vector<int>>& adj) {
    std::vector<bool> visited(V, false);
    std::queue<int> q;

    visited[startNode] = true;
    q.push(startNode);

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        std::cout << u << " ";

        for (int v : adj[u]) {
            if (!visited[v]) {
                visited[v] = true;
                q.push(v);
            }
        }
    }
}

4. Hash Maps (Hash Tables)

While you almost always use std::unordered_map, you might be asked to design one to demonstrate how collisions are handled (usually via Chaining).

#include <list>
#include <vector>

class HashTable {
    int buckets;
    std::vector<std::list<int>> table;

    int hashFunction(int key) {
        return key % buckets;
    }

public:
    HashTable(int b) : buckets(b) {
        table.resize(buckets);
    }

    void insert(int key) {
        int index = hashFunction(key);
        table[index].push_back(key);
    }

    bool search(int key) {
        int index = hashFunction(key);
        for (int x : table[index]) {
            if (x == key) return true;
        }
        return false;
    }
};

Summary for Interviews

1. Pointers: If you segfault, you fail. Always check for nullptr.
2. Memory: In C++, remember who owns the memory. In an interview, usually raw pointers are fine for simple questions, but mentioning smart pointers (std::unique_ptr) grabs bonus points.
3. Complexity: Know your Big-O.
   • BST Search: O(log n) avg, O(n) worst.
   • Hash Map Search: O(1) avg, O(n) worst.