Module 30: Data Structures in C++

Introduction

Data Structures are specialized ways of organizing and storing data so that it can be accessed, modified, and processed efficiently. Choosing the right data structure directly impacts the performance, memory usage, and scalability of software.

Almost every modern application—including operating systems, web browsers, databases, compilers, AI frameworks, and game engines—relies on data structures.

This module introduces the most important data structures used in C++ and explains how they work with complete examples.

Learning Objectives

After completing this module, you will understand:

• Linked List
• Stack
• Queue
• Binary Tree
• Binary Search Tree (BST)
• AVL Tree
• Heap
• Hash Table
• Trie
• Graph
• Time Complexity
• Real-world applications

Data Structures Overview

*Average case.

1. Linked List

A Linked List stores elements in nodes connected by pointers.

textCopy
110 → 20 → 30 → nullptr

Node Structure

cppCopy
1#include <iostream>
2
3struct Node
4{
5    int data;
6    Node* next;
7
8    Node(int value)
9        : data(value), next(nullptr)
10    {
11    }
12};
13
14int main()
15{
16    Node* head = new Node(10);
17
18    head->next = new Node(20);
19    head->next->next = new Node(30);
20
21    Node* current = head;
22
23    while(current)
24    {
25        std::cout << current->data << " ";
26
27        current = current->next;
28    }
29
30    while(head)
31    {
32        Node* temp = head;
33        head = head->next;
34        delete temp;
35    }
36}

Output

textCopy
110 20 30

2. Stack

A Stack follows LIFO (Last In, First Out).

textCopy
1Push
2
3↓
4
530
620
710
8
9↓
10
11Pop

Using STL

cppCopy
1#include <iostream>
2#include <stack>
3
4int main()
5{
6    std::stack<int> s;
7
8    s.push(10);
9    s.push(20);
10    s.push(30);
11
12    while(!s.empty())
13    {
14        std::cout << s.top() << " ";
15
16        s.pop();
17    }
18}

Output

textCopy
130 20 10

3. Queue

A Queue follows FIFO (First In, First Out).

textCopy
1Front → 10 20 30 ← Rear

Using STL

cppCopy
1#include <iostream>
2#include <queue>
3
4int main()
5{
6    std::queue<int> q;
7
8    q.push(10);
9    q.push(20);
10    q.push(30);
11
12    while(!q.empty())
13    {
14        std::cout << q.front() << " ";
15
16        q.pop();
17    }
18}

Output

textCopy
110 20 30

4. Binary Tree

A Binary Tree allows each node to have at most two children.

textCopy
1      10
2     /  \
3    5   20

Example

cppCopy
1#include <iostream>
2
3struct Node
4{
5    int data;
6    Node* left;
7    Node* right;
8
9    Node(int value)
10        : data(value), left(nullptr), right(nullptr)
11    {
12    }
13};
14
15void inorder(Node* root)
16{
17    if(root == nullptr)
18        return;
19
20    inorder(root->left);
21
22    std::cout << root->data << " ";
23
24    inorder(root->right);
25}
26
27int main()
28{
29    Node* root = new Node(10);
30
31    root->left = new Node(5);
32    root->right = new Node(20);
33
34    inorder(root);
35}

Output

textCopy
15 10 20

5. Binary Search Tree (BST)

BST property:

textCopy
1Left < Root < Right

Insert Example

cppCopy
1#include <iostream>
2
3struct Node
4{
5    int data;
6    Node* left;
7    Node* right;
8
9    Node(int value)
10        : data(value), left(nullptr), right(nullptr)
11    {
12    }
13};
14
15Node* insert(Node* root, int value)
16{
17    if(root == nullptr)
18        return new Node(value);
19
20    if(value < root->data)
21        root->left = insert(root->left, value);
22    else
23        root->right = insert(root->right, value);
24
25    return root;
26}
27
28void inorder(Node* root)
29{
30    if(root)
31    {
32        inorder(root->left);
33        std::cout << root->data << " ";
34        inorder(root->right);
35    }
36}
37
38int main()
39{
40    Node* root = nullptr;
41
42    root = insert(root, 50);
43    root = insert(root, 20);
44    root = insert(root, 70);
45    root = insert(root, 10);
46
47    inorder(root);
48}

Output

textCopy
110 20 50 70

6. AVL Tree

An AVL Tree is a self-balancing BST.

Balance Factor

textCopy
1Height(Left) - Height(Right)

Must be:

textCopy
1-1, 0, or 1

Left Rotation

cppCopy
1struct Node
2{
3    int key;
4    Node* left;
5    Node* right;
6    int height;
7};
8
9Node* leftRotate(Node* x)
10{
11    Node* y = x->right;
12    Node* t = y->left;
13
14    y->left = x;
15    x->right = t;
16
17    return y;
18}

Note: A complete AVL implementation includes height updates and four balancing cases (LL, RR, LR, RL). This snippet demonstrates the core left rotation operation.

7. Heap

A Heap is a complete binary tree.

Max Heap

textCopy
1      100
2     /   \
3    70    50

Using STL Priority Queue

cppCopy
1#include <iostream>
2#include <queue>
3
4int main()
5{
6    std::priority_queue<int> heap;
7
8    heap.push(10);
9    heap.push(50);
10    heap.push(30);
11
12    while(!heap.empty())
13    {
14        std::cout << heap.top() << " ";
15
16        heap.pop();
17    }
18}

Output

textCopy
150 30 10

8. Hash Table

Hash tables provide average O(1) lookup.

Using unordered_map

cppCopy
1#include <iostream>
2#include <unordered_map>
3
4int main()
5{
6    std::unordered_map<std::string, int> marks;
7
8    marks["Math"] = 95;
9    marks["Science"] = 88;
10
11    std::cout << marks["Math"];
12}

Output

textCopy
195

9. Trie

Trie stores strings efficiently for prefix searching.

textCopy
1        Root
2       /
3      c
4     /
5    a
6   /
7  t

Simple Trie

cppCopy
1#include <iostream>
2#include <map>
3
4struct TrieNode
5{
6    bool isWord = false;
7    std::map<char, TrieNode*> children;
8};
9
10void insert(TrieNode* root, const std::string& word)
11{
12    TrieNode* current = root;
13
14    for(char ch : word)
15    {
16        if(current->children[ch] == nullptr)
17            current->children[ch] = new TrieNode();
18
19        current = current->children[ch];
20    }
21
22    current->isWord = true;
23}
24
25int main()
26{
27    TrieNode root;
28
29    insert(&root, "cat");
30
31    std::cout << "Inserted";
32}

Output

textCopy
1Inserted

10. Graph

A Graph consists of vertices and edges.

textCopy
1A ---- B
2|      |
3|      |
4C ---- D

Adjacency List

cppCopy
1#include <iostream>
2#include <vector>
3
4int main()
5{
6    std::vector<std::vector<int>> graph(4);
7
8    graph[0].push_back(1);
9    graph[0].push_back(2);
10    graph[1].push_back(3);
11    graph[2].push_back(3);
12
13    for(size_t i = 0; i < graph.size(); i++)
14    {
15        std::cout << i << ": ";
16
17        for(int node : graph[i])
18            std::cout << node << " ";
19
20        std::cout << std::endl;
21    }
22}

Output

textCopy
10: 1 2
21: 3
32: 3
43:

Real-World Applications

STL Containers Mapping

Best Practices

• Choose the data structure based on the required operations.
• Prefer STL containers when they satisfy your needs.
• Free dynamically allocated memory or use smart pointers.
• Keep time and space complexity in mind.
• Use balanced trees for frequent search operations.
• Use hash tables when average constant-time lookup is important.

Common Mistakes

Using a Linked List for Random Access

Linked lists require O(n) traversal for indexed access. Use std::vector if frequent random access is needed.

Using a BST Without Balancing

An unbalanced BST can degrade to O(n) operations. Consider AVL Trees or Red-Black Trees for guaranteed logarithmic performance.

Ignoring Hash Collisions

Hash tables provide average O(1) performance, but poor hash functions can increase collisions and reduce performance.

Interview Questions

1. What is the difference between a Linked List and an Array?

Arrays store elements contiguously and provide O(1) indexed access, while linked lists store nodes connected by pointers and allow efficient insertion and deletion at known positions.

2. What is the difference between a Stack and a Queue?

A Stack follows LIFO, whereas a Queue follows FIFO.

3. What is a Binary Search Tree?

A binary tree where every left child is smaller than the parent and every right child is larger.

4. Why is an AVL Tree faster than an ordinary BST?

Because it remains balanced, ensuring O(log n) search, insertion, and deletion.

5. What is a Heap used for?

Priority queues, scheduling, and algorithms such as Dijkstra's shortest path.

6. What is a Hash Table?

A key-value data structure that uses a hash function to provide average O(1) insertion and lookup.

7. What is a Trie?

A tree-like data structure optimized for storing and searching strings by prefixes.

8. What is an adjacency list?

A graph representation where each vertex stores a list of its neighboring vertices.

Module Summary

In this module, you learned:

• How linked lists organize nodes using pointers
• Stack and Queue operations using the C++ Standard Library
• Binary Trees and Binary Search Trees
• Self-balancing AVL Trees
• Heaps and priority queues
• Hash Tables using std::unordered_map
• Trie data structures for efficient string processing
• Graph representation using adjacency lists
• Time complexity considerations and real-world applications

This module provides the foundation for advanced algorithms such as graph traversal, shortest-path algorithms, balanced search trees, dynamic programming, and competitive programming in C++.