Fundamentals of Data Structures in C++
Data structures in any language are very essential. Data structures help organize and store data efficiently and determine how operations are performed on data. Each structure has its own characteristics and use cases. They are used in many algorithms and programs.
The data structure is classified into two types
- Linear data structure
- Non-linear data structure
Linear data structure
Linear data structure is an arrangement where elements are sequentially placed, with each element having a unique predecessor and successor, except the first and last. These structures are simple and follow a one-dimensional arrangement of data elements. The primary characteristic of linear data structures is that elements are ordered and accessed sequentially.
Examples of linear data structures include:
- Arrays
- Stacks
- Queues
- LinkedList
1. Arrays
Arrays are a fundamental and powerful data structure in C++. They allow you to store a collection of similar elements in a contiguous block of memory. Array elements are indexed starting from 0, and you can access them directly using their index.
Arrays have a fixed size determined at the time of declaration. The constant-time access to elements makes arrays efficient for random access operations. However, it is important to note that arrays cannot be resized once created, and adding or removing elements can be difficult.
In C++, arrays can be declared using square brackets ([]), specifying the data type and initializing them with values if needed. Remember that it is crucial to be mindful of array bounds to avoid accessing elements outside the allocated memory.
Syntax:
return_type array_name[sizeof the array];
[or]
return_type array_name[sizeof the array]={elements};
Examples:
float values[30];
int arr[4]={101, 202, 303, 404};
Example 1:
Let us see an example program on an array.
Program:
#include <iostream>
int main() {
const int MAX_SIZE = 100; // Maximum size of the array
double numbers[MAX_SIZE]; // Declare an array to store numbers
int numCount; // To keep track of the number of elements entered
double sum = 0; // To store the sum of numbers
// Ask the user for the number of elements they want to enter
std::cout << "Enter the number of elements (up to " << MAX_SIZE << "): ";
std::cin >> numCount;
// checks if the user has entered a valid number of elements.
if (numCount <= 0 || numCount > MAX_SIZE) {
std::cout << "Invalid input. Please enter a number between 1 and " << MAX_SIZE << "." << std::endl;
return 1; // Exit with an error code
}
// Input loop: Prompt the user to enter each number
std::cout << "Enter " << numCount << " numbers, one at a time:" << std::endl;
for (int i = 0; i < numCount; ++i) {
std::cout << "Enter number " << i + 1 << ": ";
std::cin >> numbers[i];
sum += numbers[i]; // Add the entered number to the sum
}
// Calculate and display the average
double average = sum / numCount;
std::cout << "The average of the " << numCount << " numbers is: " << average << std::endl;
return 0; // Exit with a success code
}
Output:
Explanation:
The above program demonstrates the use of an array to calculate the data entered by a user.
The program first prompts the user to input the number of elements they want to enter and checks that the input is within a valid range. Once confirmed, the program enters a loop where each number is inputted one by one and then added to a sum variable. After all the numbers are inputted, the program calculates the average of the entered numbers and displays it to the user.
2. Stacks
In C++, a stack is a data structure that follows the Last-In-First-Out (LIFO) principle. Think of it like a stack of books, where the last book you put on top is the first one you take off. It is a container that allows you to access only the topmost element.
There are two main operations that you can perform on a stack:
- Push: To add an element to the stack, this operation pushes the element to the top of the stack.
- Pop: This operation involves the removal of the element located at the top of the stack.
In addition to the main operations like push and pop, stacks may also provide other useful functions, such as
- Peek (or top): This allows you to examine the top element without altering the stack's state.
- Size(or Length): The Size (or Length) operation can determine the number of elements currently in the stack,
- IsEmpty: This operation is useful in checking whether the stack is empty. It returns true if the stack has no elements and false otherwise.
Stacks are commonly used in various applications, such as expression evaluation, backtracking algorithms, and managing function calls in programming languages.
Syntax:
You must import the <stack> module to use a stack.
#include<stack>
std::stack<DataType> stack_name;
Example:
Let us see an example program on stack operations using the stack module.
Program:
#include <iostream>
#include <stack>
int main() {
std::stack<int> myStack; // Create an empty stack of integers
// Push elements onto the stack
myStack.push(10);
myStack.push(20);
myStack.push(30);
//Display stack size
std::cout<<"Stack size is: "<<myStack.size()<<std::endl;
// Display the top element without removing it (peek)
if (!myStack.empty()) {
std::cout << "Top element: " << myStack.top() << std::endl;
} else {
std::cout << "Stack is empty." << std::endl;
}
// Pop elements from the stack and display them
std::cout << "Popped elements: ";
while (!myStack.empty()) {
std::cout << myStack.top() << " ";
myStack.pop();
}
std::cout << std::endl;
// Check if the stack is empty
if (myStack.empty()) {
std::cout << "Stack is empty." << std::endl;
} else {
std::cout << "Stack is not empty." << std::endl;
}
return 0;
}
Output:
Explanation:
The above program demonstrated the stack operations
First, we created an empty stack and then
- We pushed the elements using the push() method
- We displayed the stack size using the size() method
- We displayed the peek element using the top() method. Before displaying, we checked whether the stack was empty.
- We popped all the elements of the stack until the stack was empty
- Finally, we checked whether the stack was empty.
3. Queues
In C++, a queue is a data structure that follows the First-In-First-Out (FIFO) principle. It can be visualized as a queue of people waiting in line, where the person who arrived first is the first one to be served.
There are two main operations you can perform on a queue:
- Enqueue: Adds an element to the back of the queue.
- Dequeue: Removes the frontmost element from the queue.
Excluding the main operations, some basic operations are also on a queue.
To clarify, the following are the functionalities of a queue:
- Peek: This returns the element at the front of the queue without removing it.
- Empty: This checks if the queue is empty and returns a boolean value (true if empty, false if not).
- Size: This returns the current number of elements in the queue.
Queues are commonly used in scenarios where the order of elements is crucial, such as scheduling tasks, handling requests, or implementing breadth-first search algorithms.
Syntax:
You must import the <queue> module to use a queue.
std::queue<DataType> queue_name;
Example:
Let us see an example program on the operations of a queue.
Program
#include <iostream>
#include <queue>
int main() {
std::queue<int> myQueue; // Create an empty queue of integers
// Enqueue elements into the queue
myQueue.push(10);
myQueue.push(20);
myQueue.push(30);
// Get the size of the queue
size_t queueSize = myQueue.size();
std::cout << "Size of the queue: " << queueSize << std::endl;
// Display the front element without removing it (peek)
if (!myQueue.empty()) {
int frontElement = myQueue.front(); // Get the front element
std::cout << "Front element (peek): " << frontElement << std::endl;
} else {
std::cout << "Queue is empty." << std::endl;
}
// Dequeue and display elements from the queue
std::cout << "Dequeued elements: ";
while (!myQueue.empty()) {
int frontElement = myQueue.front(); // Get the front element
std::cout << frontElement << " ";
myQueue.pop(); // Remove the front element
}
std::cout << std::endl;
// Check if the queue is empty
if (myQueue.empty()) {
std::cout << "Queue is empty." << std::endl;
} else {
std::cout << "Queue is not empty." << std::endl;
}
// Get the size of the queue
queueSize = myQueue.size();
std::cout << "Size of the queue: " << queueSize << std::endl;
return 0;
}
Output:
Explanation:
The above program demonstrates the operations on the queue.
- To use the inbuilt functions of the queue, we imported <queue>
- Then, we created an empty queue.
- We pushed the elements into the queue using the push() method
- We use the front method to peek at the front element without removing it.
- We use a while loop and the front method to dequeue (remove) and display elements from the front of the queue.
- The empty method is used to check if the queue is empty before peeking or dequeuing.
- We also use the size method to get the current size of the queue.
4. Linked list
The linked list is classified as a linear data structure. It is defined as a collection of nodes and links where each node consists of data and the address of the next node. Linked lists are dynamic so that we can add as many nodes as possible. The size is not fixed.
There are two types of linked list
- Singly-linked list
- Doubly-linked list
The main difference between a singly-linked list and a doubly-linked list is
- In a singly-linked list, there is only one reference link to the next node, whereas, in a doubly-linked list, there are two references: one is to the predecessor and the second to a successor.
- There is no possibility of traversing in the backward direction of a singly-linked list. We can traverse both directions in a doubly-linked list, as each node refers to its predecessor and successor.
- Doubly-linked lists consume more memory than singly-linked lists due to the extra reference per node.
- In a singly linked list, removing a node can be less efficient compared to a doubly linked list.
Let us see a simple program on the linked list
Program
#include <iostream>
// Define node structure
struct Node {
int value;
Node* next;
Node(int val) : value(val), next(nullptr) {}
};
// Define the LinkedList class
class CustomList {
private:
Node* head;
public:
CustomList() : head(nullptr) {}
// Function to insert a new element at the beginning of the list
void addElement(int val) {
Node* newNode = new Node(val);
newNode->next = head;
head = newNode;
}
// Function to delete an element with a given value from the list
void removeElement(int val) {
if (head == nullptr) {
std::cout << "List is empty. Cannot delete.\n";
return;
}
if (head->value == val) {
Node* temp = head;
head = head->next;
delete temp;
return;
}
Node* current = head;
while (current->next != nullptr && current->next->value != val) {
current = current->next;
}
if (current->next == nullptr) {
std::cout << "Element not found in the list.\n";
} else {
Node* temp = current->next;
current->next = current->next->next;
delete temp;
}
}
// This is a function that can be used to print out the elements of a list.
void displayList() {
Node* current = head;
while (current != nullptr) {
std::cout << current->value << " ";
current = current->next;
}
std::cout << "\n";
}
// Destructor to free the memory used by the linked list
~CustomList() {
while (head != nullptr) {
Node* temp = head;
head = head->next;
delete temp;
}
}
};
int main() {
CustomList myList;
myList.addElement(3);
myList.addElement(2);
myList.addElement(1);
std::cout << "Custom List: ";
myList.displayList();
myList.removeElement(2);
std::cout << "Custom List after removing 2: ";
myList.displayList();
return 0;
}
Output:
Explanation:
- In the main() function, an instance of the LinkedList class named myList is created.
- Three elements (1, 2, and 3) are inserted at the beginning of the list using addElement().
- The current state of the list is printed using displayList().
- The element with the value 2 is deleted using removeElement().
- The updated list is printed again to demonstrate the deletion.
When you run this program, you will see the operations performed on the linked list and the resulting output.
Non-Linear Data structure
Non-linear data structures are a type of data structure where the elements are not arranged sequentially. These structures offer a more versatile organization and efficient operations. They are highly valuable for solving complex problems and optimizing algorithms. Since the data structure is non-linear, its elements cannot be traversed in a single run.
Types of non-linear data structures include
- Trees
- Graphs
- hash tables
Trees
A tree is a hierarchical data structure composed of nodes connected by edges or branches. Trees are widely used in file systems, data organization, and algorithms to represent hierarchical relationships.
Some key elements to know in a tree
- Node: Each element is called a "node" in a tree. A node can hold data and may have zero or more "child nodes."
- Edge: An "edge" is a bridge between two nodes in a tree and represents a relationship, usually indicating a parent-child relationship.
- Root: The highest node in a tree is called the "root," which serves as the starting point for traversing the tree.
- Parent node: The root is also the only node with no parent. A "parent node" is a node that has one or more child nodes.
- Child node: A "child node" is directly connected to another node.
- Leaf node: Nodes connected to the same parent are called "siblings." A "leaf node" is a node that has no children, meaning it has zero out-degree.
Based on the Number of Children per Node, trees are classified into these types:
- Binary Tree: Each node has at most two children, a left child and a right child.
- Ternary Tree: Each node has at most three children.
- K-ary Tree: Each node has at most k children.
Understanding the Basic Operations of a Tree Data Structure is essential. Here are the primary operations:
1. Create: This operation helps create a tree in the data structure.
2. Insert: This operation inserts data into a tree.
3. Search: The Search operation helps find specific data in a tree to check whether it is present.
Traversal is an essential aspect of a Tree Data Structure. The following are the traversal methods:
1. Pre-order Traversal: This method performs Traveling a tree in a pre-order manner(root node, left node, then right node ) in the data structure.
2. In-order Traversal: This method performs Traveling a tree in an in-order manner(left node, root node, then right node).
3. Post-order Traversal: This method performs Traveling a tree in a post-order manner(left node, right node, then root node).
Example
Let us see an example program on binary trees
Program
#include <iostream>
// Define a structure for a binary tree node
struct TreeNode {
int data;
TreeNode* left;
TreeNode* right;
TreeNode(int value) : data(value), left(nullptr), right(nullptr) {}
};
// Function which inserts a new node into the binary tree
TreeNode* insert(TreeNode* root, int value) {
if (root == nullptr) {
return new TreeNode(value);
}
if (value < root->data) {
root->left = insert(root->left, value);
} else if (value > root->data) {
root->right = insert(root->right, value);
}
return root;
}
// Function for in-order traversal (left-root-right)
void inorderTraversal(TreeNode* root) {
if (root == nullptr) {
return;
}
inorderTraversal(root->left);
std::cout << root->data << " ";
inorderTraversal(root->right);
}
// Function for pre-order traversal (root-left-right)
void preorderTraversal(TreeNode* root) {
if (root == nullptr) {
return;
}
std::cout << root->data << " ";
preorderTraversal(root->left);
preorderTraversal(root->right);
}
// Function for post-order traversal (left-right-root)
void postorderTraversal(TreeNode* root) {
if (root == nullptr) {
return;
}
postorderTraversal(root->left);
postorderTraversal(root->right);
std::cout << root->data << " ";
}
// Function to search for a value in the binary tree
bool search(TreeNode* root, int value) {
if (root == nullptr) {
return false;
}
if (root->data == value) {
return true;
} else if (value < root->data) {
return search(root->left, value);
} else {
return search(root->right, value);
}
}
int main() {
TreeNode* root = nullptr;
root = insert(root, 50);
insert(root, 30);
insert(root, 20);
insert(root, 40);
insert(root, 70);
insert(root, 60);
insert(root, 80);
std::cout << "In-order traversal: ";
inorderTraversal(root);
std::cout << std::endl;
std::cout << "Pre-order traversal: ";
preorderTraversal(root);
std::cout << std::endl;
std::cout << "Post-order traversal: ";
postorderTraversal(root);
std::cout << std::endl;
int searchValue = 40;
if (search(root, searchValue)) {
std::cout << searchValue << " found in the tree." << std::endl;
} else {
std::cout << searchValue << " not found in the tree." << std::endl;
}
return 0;
}
Output
Explanation:
The above program demonstrated the creation of a binary tree, then showcased different traversals and showed whether the element was present in a tree.
Graphs
A graph is a collection of nodes(vertices) and edges that connect these nodes. Graphs represent and model different relationships, connections, or networks between objects. They are widely used in computer science, data analysis, transportation planning, social network analysis, and many other fields to visualize and analyze data.
components
Vertices (Nodes):
Vertices are the fundamental building blocks of a graph. Each vertex represents an entity or an element in the graph.
Edges:
Edges are the connections or relationships between pairs of vertices.
Weights (Optional):
Some graphs have weights associated with their edges. These weights can be numerical values that represent various attributes or costs associated with the connections between vertices.
Types of graphs
1. Directed Graph (Digraph):
A directed graph(digraph) is a graph where the edges have a direction, representing one-way relationships between vertices.
2. Undirected Graph:
In an undirected graph, edges have no direction and represent symmetric relationships between vertices.
3. Weighted Graph:
A weighted graph is where each edge is assigned a numerical value, or weight, representing different attributes such as cost, distance, or any other relevant factor.
Traversal Techniques
1. Breadth-first search (BFS)
Breadth-first search, or BFS, is an algorithm used to traverse a graph. It explores all of the vertices in the graph one level at a time, starting from a specified source vertex.
The term "breadth-first" is used because it examines all the neighbours at the current level before progressing to the vertices at the next level. This algorithm is frequently used in graph theory and computer science applications to solve problems such as shortest path finding in unweighted graphs. BFS is one of the graph traversal algorithms that explore a graph's vertices in a breadth ward motion, level by level, starting from a specified source vertex. It is called "breadth-first" because it explores all the neighbours at the current depth level before moving on to the vertices at the next level.
2. Depth-first search (DFS)
DFS is one of the graph traversal algorithms that explores a graph's vertices by following a depthward motion, visiting as far as possible along one branch before backtracking. DFS is implemented using either recursion or an explicit stack data structure. It is called "depth-first" because it explores the deepest unvisited vertices before moving to shallower levels.
The BFS algorithm is used to traverse graphs. It helps to visit all the nodes of a graph systematically. The BFS algorithm is used to traverse graphs.
Example:
Let us see an example program on graphs
Program:
#include <iostream>
#include <list>
#include <vector>
#include <queue>
using namespace std;
// Define a class for representing a graph
class Graph {
private:
int numVertices; // Number of vertices in the graph
list<int> *adjacencyList; // Adjacency list for storing graph edges
public:
// Constructor to initialize the graph with a given number of vertices
Graph(int vertices) {
numVertices = vertices;
adjacencyList = new list<int>[numVertices]; // Create an array of lists
}
// Add an edge between two vertices (src and dest) in the graph
void addEdge(int src, int dest) {
adjacencyList[src].push_back(dest);
// For an undirected graph, add the reverse edge as well.
adjacencyList[dest].push_back(src);
}
// Print the graph by listing vertices and their neighbors
void printGraph() {
for (int i = 0; i < numVertices; ++i) {
cout << "Vertex " << i << " --> ";
for (int neighbor : adjacencyList[i]) {
cout << neighbor << " ";
}
cout << endl;
}
}
// Depth-First Search (DFS) function to explore and print vertices
void DFS(int vertex, vector<bool>& visited) {
visited[vertex] = true;
cout << vertex << " ";
for (int neighbor : adjacencyList[vertex]) {
if (!visited[neighbor]) {
DFS(neighbor, visited);
}
}
}
// Depth-First Search (DFS) traversal of the entire graph
void depthFirstSearch() {
vector<bool> visited(numVertices, false);
cout << "Depth-First Search: ";
for (int i = 0; i < numVertices; ++i) {
if (!visited[i]) {
DFS(i, visited);
}
}
cout << endl;
}
// Breadth-First Search (BFS) traversal starting from a given vertex
void breadthFirstSearch(int startVertex) {
vector<bool> visited(numVertices, false);
queue<int> q;
cout << "Breadth-First Search: ";
visited[startVertex] = true;
q.push(startVertex);
while (!q.empty()) {
int currentVertex = q.front();
q.pop();
cout << currentVertex << " ";
for (int neighbor : adjacencyList[currentVertex]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
q.push(neighbor);
}
}
}
cout << endl;
}
};
int main() {
// Create an instance of the Graph class with 6 vertices
Graph graph(6);
// Add edges to define the graph's connectivity
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 3);
graph.addEdge(2, 4);
graph.addEdge(3, 5);
graph.addEdge(4, 5);
// Print the graph's adjacency list
cout << "Graph: " << endl;
graph.printGraph();
// Perform Depth-First Search (DFS) traversal
graph.depthFirstSearch();
int startVertex = 0;
// Perform Breadth-First Search (BFS) traversal starting from a specified vertex
cout << "Starting from vertex " << startVertex << ": ";
graph.breadthFirstSearch(startVertex);
return 0;
}
Output:
Explanation:
The above C++ program demonstrates the implementation of a simple graph using an adjacency list representation and showcases two fundamental graph traversal algorithms: Depth-First Search (DFS) and Breadth-First Search (BFS).
Hash Tables
A hash table, also known as a hash map, is a crucial data structure utilized in computer science and programming to store and retrieve data efficiently. Its primary aim is to offer quick access to values connected to keys, making it an ideal tool for tasks like data searching, insertion, and deletion.
A hash table comprises two primary elements:
Keys: The key is a unique integer used to index the values.
Value - data that is linked to specific keys for easy access
Example:
Let us see an example program on hash tables
Program:
#include <iostream>
#include <unordered_map>
#include <string>
int main() {
// Create an unordered_map to represent the phone book
std::unordered_map<std::string, std::string> phoneBook;
// Insert entries into the phone book
phoneBook["Alice"] = "123-456-7890";
phoneBook["Bob"] = "987-654-3210";
phoneBook["Charlie"] = "555-123-4567";
// Look up a phone number by name
std::string nameToLookup = "Bob";
if (phoneBook.find(nameToLookup) != phoneBook.end()) {
std::cout << "Phone number for " << nameToLookup << ": " << phoneBook[nameToLookup] << std::endl;
} else {
std::cout << nameToLookup << " not found in the phone book." << std::endl;
}
// Add a new entry
phoneBook["David"] = "111-222-3333";
std::cout << "Added David's entry to the phone book." << std::endl;
// Print the entire phone book
std::cout << "Phone Book:" << std::endl;
for (const auto& entry : phoneBook) {
std::cout << entry.first << ": " << entry.second << std::endl;
}
return 0;
}
Output:
Explanation:
We represent the phone book using a std::unordered_map named phoneBook. The keys are the names of type strings, and the values are the phone numbers stored as strings. We use the square bracket operator ([]) to insert entries into the phone book.
We use the find method to look up a phone number by name. We print the associated phone number if the name is in the phone book.
We added a new entry for "David" to the phone book. Finally, we print the entire phone book by iterating through its entries.
Conclusion
Data structures form a fundamental concept in the field of computer science. They provide a systematic way to organize and store data efficiently, enabling the design and implementation of efficient algorithms and solving complex computational problems.
Choosing the appropriate data structure can significantly impact the efficiency of your algorithms. Different data structures excel in different operations, and it is crucial to understand their time and space complexities for optimizing code.
The choice of data structure should be driven by the specific requirements and constraints of the problem you are trying to solve. Data structures provide an abstraction layer that simplifies how data is stored and accessed, making it easier to work with complex data, enabling the design and implementation of efficient algorithms, and solving complex computational problems.
Data structures are vital for computer science and programming. Databases use B-trees, social networks use graph structures, and search engines use complex structures for indexing. Understanding fundamental and advanced structures like arrays, linked lists, stacks, queues, trees, graphs, and hash tables is crucial.
In summary, data structures are the building blocks of algorithms and software systems.