Data Structures in C++ with Examples and Code Implementation

Data Structures in C++ with Code Implementations

Data structures are essential in programming as they allow us to store, organize, and manipulate data efficiently. In C++, we have various data structures, each suited for different types of problems. This post will cover fundamental data structures, including arrays, linked lists, stacks, queues, trees, graphs, and hash tables, with code implementations in C++.

---

1. Arrays

Arrays are a collection of elements stored in contiguous memory locations.

Implementation:

cpp
#include <iostream>
using namespace std;

int main() {
    int arr[5] = {10, 20, 30, 40, 50};
    for (int i = 0; i < 5; i++) {
        cout << "Element at index " << i << ": " << arr[i] << endl;
    }
    return 0;
}

---

2. Linked List

A linked list consists of nodes where each node contains data and a pointer to the next node.

Implementation:

cpp
#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node* next;

    Node(int val) {
        data = val;
        next = nullptr;
    }
};

void printList(Node* head) {
    Node* temp = head;
    while (temp != nullptr) {
        cout << temp->data << " -> ";
        temp = temp->next;
    }
    cout << "NULL" << endl;
}

int main() {
    Node* head = new Node(1);
    head->next = new Node(2);
    head->next->next = new Node(3);
    printList(head);
    return 0;
}

---

3. Stack

A stack follows the Last In, First Out (LIFO) principle.

Implementation:

cpp
#include <iostream>
#include <stack>
using namespace std;

int main() {
    stack<int> s;
    s.push(10);
    s.push(20);
    s.push(30);

    cout << "Top element: " << s.top() << endl;
    s.pop();
    cout << "Top after pop: " << s.top() << endl;

    return 0;
}

---

4. Queue

A queue follows the First In, First Out (FIFO) principle.

Implementation:

cpp
#include <iostream>
#include <queue>
using namespace std;

int main() {
    queue<int> q;
    q.push(10);
    q.push(20);
    q.push(30);

    cout << "Front: " << q.front() << " Rear: " << q.back() << endl;
    q.pop();
    cout << "Front after pop: " << q.front() << endl;

    return 0;
}

---

5. Binary Tree

A binary tree consists of nodes where each node has at most two children.

Implementation:

cpp
#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node* left;
    Node* right;
    
    Node(int val) {
        data = val;
        left = right = nullptr;
    }
};

void inOrderTraversal(Node* root) {
    if (root == nullptr) return;
    inOrderTraversal(root->left);
    cout << root->data << " ";
    inOrderTraversal(root->right);
}

int main() {
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    
    inOrderTraversal(root);
    return 0;
}

---

6. Graph

A graph consists of nodes (vertices) connected by edges.

Implementation:

cpp
#include <iostream>
#include <vector>
using namespace std;

class Graph {
public:
    vector<vector<int>> adj;
    Graph(int vertices) {
        adj.resize(vertices);
    }
    
    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u); // Undirected Graph
    }
    
    void printGraph() {
        for (int i = 0; i < adj.size(); i++) {
            cout << "Node " << i << ": ";
            for (int neighbor : adj[i]) {
                cout << neighbor << " ";
            }
            cout << endl;
        }
    }
};

int main() {
    Graph g(5);
    g.addEdge(0, 1);
    g.addEdge(0, 4);
    g.addEdge(1, 2);
    g.addEdge(1, 3);
    g.printGraph();
    return 0;
}

---

7. Hash Table

A hash table is a data structure that maps keys to values using a hash function.

Implementation:

cpp
#include <iostream>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<string, int> hashTable;
    hashTable["Alice"] = 25;
    hashTable["Bob"] = 30;

    cout << "Alice's age: " << hashTable["Alice"] << endl;
    cout << "Bob's age: " << hashTable["Bob"] << endl;
    return 0;
}

---

Conclusion

These data structures form the foundation of efficient programming and problem-solving. C++ provides built-in support for most of these structures through the Standard Template Library (STL), making their usage easier and more efficient. Understanding and implementing these structures will improve your ability to solve complex problems effectively.