Data Structures Using C++ | Arrays, Linked Lists, Stacks, Queues, Trees, Graphs, Hashing, Heap

This complete tutorial on Data Structures Using C++ covers arrays, strings, linked lists, stacks, queues, deques, trees, heaps, hashing, and graphs. It explains implementation, operations, and best practices for each data structure, helping learners write efficient and optimized C++ programs for competitive programming and real-world applications.

Data Structures Using C++ – Complete Tutorial

1. Arrays

Arrays are fixed-size, contiguous memory data structures.

Example:


#include <iostream>
using namespace std;

int main() {
int arr[5] = {1, 2, 3, 4, 5};
for(int i=0; i<5; i++) cout << arr[i] << " ";
}

Operations: insertion, deletion, traversal, searching, sorting

2. Strings

Strings store sequences of characters. Can use char arrays or std::string.

Example:


#include <iostream>
#include <string>
using namespace std;

int main() {
string str = "Hello";
str += " World";
cout << str << endl; // Output: Hello World
}

Operations: concatenation, length, access, substring, comparison

3. Linked List

a) Singly Linked List

  1. Nodes contain data + pointer to next node

struct Node {
int data;
Node* next;
};

b) Doubly Linked List

  1. Nodes contain data + next + prev pointers

struct Node {
int data;
Node* next;
Node* prev;
};

c) Circular Linked List

  1. Last node points back to head node
  2. Can be singly or doubly linked

Operations: insertion, deletion, traversal

4. Stack

Stack is LIFO (Last In First Out) structure.

Using array:


#include <stack>
stack<int> st;
st.push(10);
st.pop();
cout << st.top();

Operations: push, pop, top, isEmpty

5. Queue

Queue is FIFO (First In First Out) structure.

Using STL:


#include <queue>
queue<int> q;
q.push(1);
q.push(2);
q.pop();
cout << q.front();

Operations: enqueue, dequeue, front, back, isEmpty

6. Deque

Deque is double-ended queue, can insert/remove from both ends.

Example:


#include <deque>
deque<int> d;
d.push_back(1);
d.push_front(0);
cout << d.front() << " " << d.back();

7. Trees

Hierarchical structures with root and child nodes.

Binary Tree


struct Node {
int data;
Node* left;
Node* right;
};

Binary Search Tree (BST)

  1. Left child < parent < right child

Operations: insertion, deletion, traversal (inorder, preorder, postorder)

8. Heap

Heap is a complete binary tree satisfying:

  1. Max-heap: parent ≥ children
  2. Min-heap: parent ≤ children

Using STL priority_queue


#include <queue>
priority_queue<int> maxHeap; // Max-heap
priority_queue<int, vector<int>, greater<int>> minHeap; // Min-heap

9. Hashing

Hashing allows O(1) average time complexity for insertion/search.

Example: Using unordered_map


#include <unordered_map>
unordered_map<int, string> map;
map[1] = "One";
cout << map[1];

Applications: fast lookup, frequency counting, caching

10. Graphs

Graphs store nodes (vertices) and edges.

Representation:

  1. Adjacency Matrix – 2D array
  2. Adjacency List – array of lists

Example: Adjacency List


#include <vector>
vector<int> adj[5]; // 5 vertices
adj[0].push_back(1); // edge 0->1

Algorithms: BFS, DFS, Dijkstra, Prim, Kruskal

Best Practices

  1. Prefer STL containers for simple operations
  2. For large data, optimize memory and time complexity
  3. Use smart pointers for dynamic nodes
  4. Modularize code for trees, graphs, and linked lists

Common Mistakes

  1. Not updating pointers correctly in linked lists
  2. Off-by-one errors in arrays and loops
  3. Forgetting to free dynamic memory
  4. Using stack/queue incorrectly for LIFO/FIFO

Summary

In this chapter, you learned Data Structures Using C++, including:

  1. Arrays, strings, stacks, queues, deques
  2. Linked lists (singly, doubly, circular)
  3. Trees, BST, heaps
  4. Hashing and graphs

Mastering these data structures is essential for competitive programming, algorithm design, and real-world software development.