Data Structures in C++
C++ programming language offers several exciting and useful features and functionalities to its
users. And it also does support object-oriented programming. With this technique, you can
perform some major methods such as Encapsulation, Abstraction, Inheritance, Polymorphism
etc. In C++, data structures are a useful and inescapable part of programming. With the help of
data structures, we perform operations on data such as data representation, storage, organization
and many more.
What are Data Structures
With the help of data structures, you can organize data in a particular way so that it can be used
effectively. There are several ways to organize the data in memory.
Below, we stored a list of items using the array data structure.
Data Types C++
It is just a group of similar data under a single name. Data types that are similar share similar
characteristics and behave in a similar way.
For example, if you want to store the address of a person or house then you should use ‘string’
data type.
Data types are categorized into two broad categories:-
1. Primitive Data Type:- These are pre-defined data types. It is also known as fundamental data
types. Example:- int, float, double, char, string etc.
2. Non-Primitive Data Type:- These are user-defined data types. Example:- array, structures,
unions, structures, linked lists etc.
Types of Data Structures in C++
In C++, data structures are further categorized into 3 types.
1. Simple Data Structures
These data structures are built from primitive data types like int, float, double, char etc.
Example:- An array is a data structure that holds the same data type and the structure is also a
data type that holds different data types.
2. Compound Data Structures
You can also build compound data structures by combining simple data structures. Compound
data structures are classified into:-
a. Linear Data Structure:– If the elements of a data structure are ordered in sequence then it is
a linear data structure. Example:- stacks, queues and linked lists.
b. Non-Linear Data Structure:– These data structures are not linear. These are multilevel data
structures. Example:- trees, graphs etc.
3. Static and Dynamic Data Structures
Static data structures are constant in size and structure. It is associated with specific memory
locations fixed at compilation time.
You can expand or contract a data structure according to your needs during the execution of the
program. And these types of data structures are known as Dynamic Data Structure.
Operations on Data Structures
Below are the basic operations which you can perform on the data structures in C++:-
Insertion: Adding a new data element into the data structure.
Deletion: This operation is about deleting or removing an existing data element from
the data structure.
Traversal: This operation is about processing and displaying all the data elements in
the data structure.
Searching: Searching a specific data element in the data structure.
Sorting: This operation is about arranging all the data elements in the data structure
either in ascending or descending order.
Merging: This operation is about combining similar data elements from two or more
data structures.
C++ ARRAYS
Arrays are simply a collection of similar data types stored at contiguous memory locations. It can
store primitive types of data like int, char, float, double etc. With the help of the arrays, a
programmer can access the elements very easily.
Suppose, you want to store marks of 20 students then you might try to declare 20 variables like
student1_marks, student2_marks etc. But what if i tell you that you can do all those with a single
variable named array. With the help of a few lines of code, you can access those elements.
6 9 8 5 3
0 1 2
3 4
Array of size 5
Syntax for declaring an array:-
dataType array_name[arraySize];
So, if you want to access the second element of the above array, then you have to do:-
cout<<array[1]
Example:-
#include<iostream>
using namespace std;
int main()
{
int numbers[3] = {2, 3, 4};
cout<<"First number is: "<<numbers[0]<<endl;
cout<<"Last number is: "<<numbers[2];
}
Output:-
First number is: 2
Last number is: 4
C++ ARRAY TYPES
Arrays in C++ can be of two types:-
1. One-Dimensional
One-dimensional arrays in C++ are collections of elements of the same data type arranged in a
linear sequence. They are also known as flat arrays.
You can declare a one-dimensional array using the following syntax:-
Syntax
datatype arrayName[arraySize];
Example:
#include <iostream>
using namespace std;
int main() {
int nums[3];
nums[0] = 10;
nums[1] = 20;
nums[2] = 30;
for (int i = 0; i < 3; ++i) {
cout<<nums[i]<<" ";
}
return 0;
}
You can also try this code with Online C++ Compiler
Run Code
This code declares an array of integers, traverses over this array using a for loop and prints the
elements.
Output:
10 20 30
2. Multi-Dimensional
Multi-dimensional arrays in C++ are used for representing data organized in multiple dimensions
such as matrices.
You can declare a multi-dimensional array using the following syntax:-
Syntax
datatype arrayName[dimension1Size][dimension2Size];
When you initialize a 2D array, you must always specify the second dimension(no. of cols), but
providing the first dimension(no. of rows) may be omitted.
Example:
#include <iostream>
using namespace std;
int main() {
int nums[][2] = {{1, 2}, {3, 4}};
for (int i = 0; i < 2; ++i) {
for(int j = 0; j < 2; ++j){
cout<<nums[i][j]<<" ";
}
cout<<"\n";
}
return 0;
}
You can also try this code with Online C++ Compiler
Run Code
This code declares a 2x2 matrix, traverses over it using 2 nested for loops and prints the
elements.
Output:
12
34
C++ Array Declaration
In C++, an array is declared as follows:
data_type array_name[size]
Where size is the number of elements in the array, array_name is the array's name, and data_type
indicates the type of the array's elements.
Access Elements in C++ Array
You can access elements in a C++ array using their respective indices.
You can use the following syntax to access in element in an array using its index:-
Syntax
arrayName[elementIndex]
The following code accesses the elements of a C++ array:-
Example:
#include <iostream>
using namespace std;
int main() {
int nums[5] = {3, 2, 1, 5, 7};
int idx = -1, target = 1;
for (int i = 0; i < sizeof(nums)/4; ++i) {
if(nums[i]==target){ /* access element */
idx = i;
break; /* element found, terminate search */
}
}
if(idx!=-1){
cout<<"Target found at index: "<<idx;
}
return 0;
}
Run Code
This code performs linear search on a one-dimensional array, if the target is found, the index is
printed. Each element of the array is accessed using its index.
Output:
10 20 30
C++ LINKED LIST
A linked list can be defined as a collection of connected nodes. It is a linear data structure. A
linked list contains two parts such as:-
Data Part:- Contains the data of the user.
Pointer Part:- It points to the next member of the linked list.
In the above image, Head contains the address of the first node. And the last node in the linked
list points to NULL.
Nodes are stored at different locations.
There are three types of linked list such as Singly Linked List, Doubly Linked List and Circular
Linked List.
Below, we have created a singly linked list of three members.
// Node Initializing!
struct node *HEAD;
struct node *ONE = NULL;
struct node *TWO = NULL;
struct node *THREE = NULL;
// Allocating memory!
ONE = malloc(sizeof(struct node));
TWO = malloc(sizeof(struct node));
THREE = malloc(sizeof(struct node));
// Assigning the values of data!
ONE->data = 23;
TWO->data = 34;
THREE->data = 90;
// Connecting nodes with each other!
ONE->next = TWO;
TWO->next = THREE;
THREE->next = NULL;
// Saving the address of first node
HEAD = ONE;
A simple Linked List with three items
/* Initialize nodes */
struct node *head;
struct node *one = NULL;
struct node *two = NULL;
struct node *three = NULL;
/* Allocate memory */
one = malloc(sizeof(struct node));
two = malloc(sizeof(struct node));
three = malloc(sizeof(struct node));
/* Assign data values */
one->data = 1;
two->data = 2;
three->data=3;
/* Connect nodes */
one->next = two;
two->next = three;
three->next = NULL;
/* Save address of first node in head */
head = one;
The LinkedList class manages the operations on the linked list such as insertion, deletion, and
traversal.
C++ program structure for insertion, deletion, and traversal.
class LinkedList {
private:
Node* head; // Pointer to the first node (head) of the list
public:
// Constructor to initialize an empty linked list
LinkedList() : head(nullptr) {}
// Function to insert a node at the beginning of the list
void insertAtHead(int value) {
Node* newNode = new Node(value);
newNode->next = head;
head = newNode;
}
// Function to insert a node at the end of the list
void insertAtEnd(int value) {
Node* newNode = new Node(value);
if (head == nullptr) {
head = newNode;
return;
}
Node* temp = head;
while (temp->next != nullptr) {
temp = temp->next;
}
temp->next = newNode;
}
// Function to delete a node by its value
void deleteByValue(int value) {
if (head == nullptr) {
return; // List is empty
}
if (head->data == value) {
Node* temp = head;
head = head->next;
delete temp;
return;
}
Node* current = head;
while (current->next != nullptr && current->next->data != value) {
current = current->next;
}
if (current->next != nullptr) {
Node* nodeToDelete = current->next;
current->next = nodeToDelete->next;
delete nodeToDelete;
}
}
// Function to print the elements of the linked list
void printList() {
Node* temp = head;
while (temp != nullptr) {
cout << temp->data << " -> ";
temp = temp->next;
}
cout << "nullptr" << std::endl;
}
STACK IN C++
Stack is known as a linear data structure. It follows the Last-In-First-Out rule. So, if you push
something to the stack then the last value which you pushed, will be the first to pop out. The
insertion and deletion operation on the stack will only take place from one end which is the top
of the stack.
In 2 ways, you can implement a stack in C++:-
1. Statically:- You can implement a stack using an array. It allows static memory allocation of
its data elements. In this, the stack inherits all the features of the array.
2. Dynamically:- You can also implement a stack using a linked list. It allows dynamic memory
allocation of its data elements. In this, the stack takes over the characteristics of the linked list.
Queue in C++
Queue is known as a linear data structure. It follows the First-In-First-Out rule. So, if you push
something to the stack then the first value of the stack will pop out. In the queue, the insertion
operation is possible from the rear end(back) and the deletion is from the front.
In 2 ways, you can implement the queue:-
1. Statically:- You can implement a queue using an array. It allows static memory allocation of
its data elements. In this, the queue inherits all the features of the array.
2. Dynamically:- You can also implement a queue using a linked list. It allows dynamic memory
allocation of its data elements. In this, the queue takes over the characteristics of the linked list.
PROGRAM TO CREATE STACK OF STRINGS
#include <iostream>
#include <stack>
using namespace std;
int main() {
// create a stack of strings
stack<string> languages;
// add element to the Stack
languages.push("C++");
languages.push("Java");
languages.push("Python");
// print top element
cout << languages.top();
return 0;
}
Run Code
Output
Python
In the above example, we have created a stack of strings named languages .
Here, we have used the push() method to add elements to the stack. We have
then used the top() method to display the top element.
We will learn more about push() and top() method later in the tutorial.
C++ TREES
A tree is known as a finite and non-empty set of elements in mathematical terms. Trees are
hierarchical data structures. A tree includes multiple nodes. This data structure follows the
parent-child relationship. It is not a linear data structure like array, structure, linked lists etc. It is
a non-linear data structure.
C++ Structure
The structure is a user-defined data type. It works similarly like arrays. Structures help you in
grouping items of different types in a single group. It stores the collection of different data types.
Each element of structure is a member.
Binary Tree Representation
A node of a binary tree is represented by a structure containing a data part and two
pointers to other structures of the same type.
struct node
{
int data;
struct node *left;
struct node *right;
}
Defining a structure in C++:-
Before creating variables of structure, you have to define it first. You can use the struct keyword
to define structures.
Syntax:-
struct name_of_the_structure
{
data_type member1;
data_type member2;
...
data_type memberN;
};
Example:-
struct bill
{
float amount;
int id;
char address[100];
};
In the above example, we have defined a structure named bill. And the members of this structure
are amount, id and address.
Accessing members of structures in C++:-
Before using the structure variables, you will have to access the members of the structure. There
are 2 ways to access the member of the structure:-
Use . operator
Use -> operator (structure pointer operator)
Suppose, you want to access the amount member of the p1 variable from the above example then
you can use . operator like below:-
p1.amount;
Example:- Accessing members of structures
#include <iostream>
using namespace std;
struct Tech{
int a = 0;
int b = 1;
};
int main()
{
struct Tech t1;
cout << "a: " << t1.a << " and b: " << t1.b<<endl;
t1.a = 5;
t1.b = 10;
cout << "a: " << t1.a << " and b: " << t1.b;
return 0;
}
Output:-
a: 0 and b: 1
a: 5 and b: 10
Structure as function arguments
You can also pass a function to structures. It helps you in making your coding better and
efficient.
Example:- passing function to structures
#include <iostream>
#include <string.h>
using namespace std;
struct info {
char student_name[50];
char favorite_subject[20];
int id;
};
void display( struct info each_student );
int main() {
struct info s1;
strcpy( s1.student_name, "Tom Sawer");
strcpy( s1.favorite_subject, "English");
s1.id = 20;
// printing first student details!
display(s1);
return 0;
}
void display( struct info each_student ) {
cout<<"Name of first student: "<< each_student.student_name<<endl;
cout<<"Favourite subject of first student: "<<each_student.favorite_subject<<endl;
cout<<"ID of first student: "<<each_student.id<<endl;
}
Output:-
Name of first student: Tom Sawer
Favourite subject of first student: English
ID of first student: 20
