Data Structures Algorithms and Application in C++
What is Data Structure?
Data Structure is a method of arranging and storing data in a computer’s memory to be quickly and effectively accessed when needed. A data structure is a particular type of organization for data that can be managed in various ways, including logically or mathematically.
Not only for organizing the data but also is used for data processing, retrieval, and archiving. Almost all software systems and programs use various basic and complex forms of data structures.
Why Data Structure and Algorithms?
Applications nowadays encounter many issues as they are getting more complex and data-rich:
- Search Speed: As data is increasing daily and getting more complex, it is now more challenging to search for a single item from a vast amount of data. It takes much time resulting in a slower speed of searching.
- Processing Speed: Despite having high-speed processors,the processor sometimes fails due to a massive volume of data.
- Multiple Queries: Fastest web servers can also fail while searching the data when thousands of users do it simultaneously.
To solve problems like this, data structures can help a lot. Data structures organize the data so that there is no need to search all the data; we can get the required data immediately.
Different types of data structures
![Data Structures Algorithms and Application in C++](https://static.tutorialandexample.com/cpp/data-structures-algorithms-and-application-in-cpp1.png)
Data structures give us a variety of algorithms to organize the data in the memory for the programmer’s ease.
Data Structures can be divided into 2 categories:
- Linear data structure
- Non-linear data structure
Linear Data Structure
In this type of data structure, elements are placed sequentially, one after the other. There is a specific order in which linear data structures can be used. Some of the linear data structures are Arrays, Linked Lists, Queues, and Stack.
Non-linear Data Structure
The elements are stored in a hierarchy in this type of data structure. There is no specific order; one element is connected with one or more elements. Trees and graphs are the best examples of non-linear data structures.
Types of linear data structures
1. Array
An array is a linear data structure to collect items with similar data types. An array can be of single dimensions and multi-dimensions. We can randomly access array elements using their index.
![Data Structures Algorithms and Application in C++](https://static.tutorialandexample.com/cpp/data-structures-algorithms-and-application-in-cpp2.png)
Representation of Array
Syntax of Array in C++:
data_type array_name[size_of_array]={elements stored separated by commas};
We can store multiple data items inside curly braces, separated by commas. It can be blank if we don’t want to store any element.
The array index starts from 0 to n-1, where n is the number of elements in an array. If the array stores 10 items, the index will start from 0 to 9, and the Array's length will be 10. Each element in the Array is 4 bytes. The array size can be determined by the total number of elements multiplied by 4. We can calculate the address of each element using the base address and the data element’s size as elements in the Array are stored at a particular memory location.
Example:
int arr[10]={1, 2, 3, 4, 5, 6, 7, 8, 9, 0};
This is a single-dimension array named arr of integer type that can store a maximum of 10 elements.
int a[3][3]= {(1,2,3),(4,5,6),(7,8,0)};
This multi-dimension Array (2-D) named a has 3 rows and 3 columns and can store 9 elements of integer data type.
Operations on Array
We can perform various operations on an array, like insertion, deletion, searching, display, updation, etc.
Data types supported with Array:
- BINARY
- CHAR
- VARCHAR
- DATE
- DECIMAL
- DOUBLE
- FLOAT
- INTEGER
- TIME
Program to understand Array in C++
CODE
This code will take input from users and store the elements in the Array.
#include <iostream>
using namespace std;
int main() {
int num[5];
cout << "Enter 5 numbers: " << endl;
//store input from the user to an array
for (int i = 0; i < 5; ++i) {
cin >> num[i];
}
cout << "The numbers are: ";
//printing array elements
for (int n = 0; n < 5; ++n) {
cout << num[n] << " ";
}
return 0;
}
OUTPUT
![Data Structures Algorithms and Application in C++](https://static.tutorialandexample.com/cpp/data-structures-algorithms-and-application-in-cpp3.png)
CODE 2:
This code will show updation using Array.
#include <iostream>
using namespace std;
int main(){
int ARR[] = {1,13,25,7,8};
int item = 10, k = 3, n = 5;
int i = 0, j = n;
cout << "The original array elements are:\n";
for(i = 0; i<n; i++)
cout << "ARR[" << i << "] = " << ARR[i] << endl;
ARR[2] = item;
ARR[3]= k+5;
ARR[0]= n-9;
cout << "The array elements after updation are:\n";
for(i = 0; i<n; i++)
cout << "ARR[" << i << "] = " << ARR[i] << endl;
return 0;
}
OUTPUT
![Data Structures Algorithms and Application in C++](https://static.tutorialandexample.com/cpp/data-structures-algorithms-and-application-in-cpp4.png)
Applications of Array
When storing data for mathematical computations, an array is utilized. Additionally, it aids in box ordering, record management, and picture processing. Additionally, book pages are an example of a data structure array.
2. Stack
Stacks use the LIFO (Last-In-First-Out) principle, a linear data structure type. A queue has two ends (forward and backward), but a stack has only one. It has a single pointer, the top pointer, pointing to the stack’s top element. When an item is added to the stack, it is always added to the top and can only be removed from the stack. In other words, a stack is a container that allows for insertions and deletions at the bottom of the stack, called the top of the stack.
![Data Structures Algorithms and Application in C++](https://static.tutorialandexample.com/cpp/data-structures-algorithms-and-application-in-cpp5.png)
Representation of Stack
An array, structure, pointer, or linked list can implement a stack. A stack may have a sense of dynamic resizing, or it may have a fixed size. It is a stack because it functions like stacks, such as heaps of books. As an abstract data type with a predetermined capacity, a stack can only store components of a specific size. It is a data structure that inserts and deletes elements in a specific order, either LIFO or FILO. It is a stack because it functions like stacks, such as heaps of books. As an abstract data type with a predetermined capacity, a stack can only store components of a specific size.
It is a data structure that inserts and deletes elements in a specific order, either LIFO or FILO.
LIFO Principle of Stack
LIFO means LAST IN FIRST OUT, which means the element inserted in the last will be removed first and vice-versa.
Working
- A pointer TOP is initialized to trace the top element in the stack.
- In starting value of TOP=-1 means the stack is empty.
- While pushing, an element value of TOP is increased, and a new element is inserted into the position of TOP.
- While popping, the element pointed to TOP is returned, and the value is reduced.
- Check if the stack is full while pushing, and check if it is empty while popping.
Operations on Stack
We may carry out various activities on a stack using a few fundamental operations.
- Push: Adding a component on top of a stack.
- Pop: Remove the top element from the stack.
- IsEmpty: to check if the stack is empty
- IsFull: to check if the stack is full.
Program to understand concepts on the stack in C++
CODE
#include <iostream>
using namespace std;
int stack[100], n=100, top=-1;
void push(int val) {
if(top>=n-1)
cout<<"Stack Overflow"<<endl;
else {
top++;
stack[top]=val;
}
}
void pop() {
if(top<=-1)
cout<<"Stack Underflow"<<endl;
else {
cout<<"The popped element is "<< stack[top] <<endl;
top--;
}
}
void display() {
if(top>=0) {
cout<<"Stack elements are:";
for(int i=top; i>=0; i--)
cout<<stack[i]<<" ";
cout<<endl;
} else
cout<<"Stack is empty";
}
int main() {
int ch, val;
cout<<"1) Push in stack"<<endl;
cout<<"2) Pop from stack"<<endl;
cout<<"3) Display stack"<<endl;
cout<<"4) Exit"<<endl;
do {
cout<<"Enter choice: "<<endl;
cin>>ch;
switch(ch) {
case 1: {
cout<<"Enter a value to be pushed:"<<endl;
cin>>val;
push(val);
break;
}
case 2: {
pop();
break;
}
case 3: {
display();
break;
}
case 4: {
cout<<"Exit"<<endl;
break;
}
default: {
cout<<"Invalid Choice"<<endl;
}
}
}while(ch!=4);
return 0;
}
OUTPUT
![Data Structures Algorithms and Application in C++](https://static.tutorialandexample.com/cpp/data-structures-algorithms-and-application-in-cpp6.png)
Application of Stack
The layer of dishes stacked on the other is the ideal example of how data structures stack. If one wants to arrange the top dish at the bottom, all the other dishes must be removed. Additionally, browsers employ stack data structures to track previously visited websites.
3. Linked List
A linear dynamic data structure that is used to store data elements is known as a linked list. It has several connected nodes, and each node keeps the data and address of the next node. Every node is interconnected using pointers.
![Data Structures Algorithms and Application in C++](https://static.tutorialandexample.com/cpp/data-structures-algorithms-and-application-in-cpp7.png)
Operations in Linked List
We can perform basic operations in a linked list. They are as follows:
- Creating: create the first node
- Insertion: adding a new element
- Deletion: deleting an element
- Search: finding a node
- Traverse: traversing through each node
- Sort: sorting the list in a particular order
Types of Linked Lists
There are mainly three types of linked lists:
- Singly-linked list
- Doubly linked list
- Circular linked list
1. Singly Linked List
A singly linked list is referred to as a linked list in which we can traverse it from one direction and is thus also known as a unidirectional linked list. When talking about a linked list, it simply means a singly linked list.
2. Doubly Linked List
It contains two pointers. The doubly linked list is a data structure with three parts, data, and two addresses. A doubly linked list is a list with three parts in a single node: one data part, a pointer to the previous node, and one pointer to the next node.
3. Circular Linked List
A circular linked list is a single list connecting the last node to the first node. It does not have any starting and ending nodes. The circular list can be traversed in any direction.
Program to illustrate Linked List in C++
CODE
#include <stdlib.h>
#include <iostream>
using namespace std;
// Create a node
struct Node {
int data;
struct Node* next;
};
void insertAtBeginning(struct Node** head, int new_data) {
// Allocate memory to a node
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
//Insert the data
new_node->data = new_data;
new_node->next = (*head);
// Move head to a new node
(*head) = new_node;
}
// Insert a node after a node
void insertAtPos(struct Node* prev_node, int new_data) {
if (prev_node == NULL) {
cout << "the given previous node cannot be NULL";
return;
}
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = prev_node->next;
prev_node->next = new_node;
}
// Insert at the end
void insertAtEnd(struct Node** head, int new_data) {
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
struct Node* last = *head; /* used in step 5*/
new_node->data = new_data;
new_node->next = NULL;
if (*head == NULL) {
*head = new_node;
return;
}
while (last->next != NULL) last = last->next;
last->next = new_node;
return;
}
// Delete a node
void deleteNode(struct Node** head, int key) {
struct Node *temp = *head, *prev;
if (temp != NULL && temp->data == key) {
*head = temp->next;
free(temp);
return;
}
// Find the key to be deleted
while (temp != NULL && temp->data != key) {
prev = temp;
temp = temp->next;
}
// If the key is not present
if (temp == NULL) return;
// Remove the node
prev->next = temp->next;
free(temp);
}
// Search a node
bool search(struct Node** head_ref, int key) {
struct Node* current = *head_ref;
while (current != NULL) {
if (current->data == key) return true;
current = current->next;
}
return false;
}
// Sort the linked list
void sort(struct Node** head_ref) {
struct Node *current = *head_ref, *index = NULL;
int temp;
if (head_ref == NULL) {
return;
} else {
while (current != NULL) {
// index points to the node next to current
index = current->next;
while (index != NULL) {
if (current->data > index->data) {
temp = current->data;
current->data = index->data;
index->data = temp;
}
index = index->next;
}
current = current->next;
}
}
}
// Print the linked list
void printList(struct Node* node) {
while (node != NULL) {
cout << node->data << " ";
node = node->next;
}
}
// Driver program
int main() {
struct Node* h = NULL;
cout<<"INSERTING AT END :";
insertAtEnd(&h, 1);
printList(h);
cout<<"\nINSERTING 6 AT BEGINNING: ";
insertAtBeginning(&h, 6);
printList(h);
cout<<"\nNSERTING 10 AT BEGINNING: ";
insertAtBeginning(&h, 10);
printList(h);
cout<<"\nINSERTING 3 AT END: ";
insertAtEnd(&h, 3);
printList(h);
cout<<"\nINSERTING 2 AT NEXT NODE: ";
insertAtPos(h->next, 2);
cout << "\n\nLINKED LIST: ";
printList(h);
cout<<"\n\nDELETION: ";
cout<<"\nDELETING 3RD NODE";
cout << "\nLINKED LIST AFTER DELETION: ";
deleteNode(&h, 3);
printList(h);
cout<<"\n\nSEARCHING";
cout<<"\nSEARCHING 3 IN THE LIST";
int item_to_find = 3;
if (search(&h, item_to_find)) {
cout << endl << item_to_find << " is found";
}
else
{
cout << endl << item_to_find << " is not found";
}
cout<"\n\nSORTIG THE LINKED LIST";
sort(&h);
cout << "\nSORTED LIST: ";
printList(h);
}
OUTPUT
![Data Structures Algorithms and Application in C++](https://static.tutorialandexample.com/cpp/data-structures-algorithms-and-application-in-cpp8.png)
Application of Linked List
They can implement queues, graphs, and stacks. Additionally, they are employed to carry out mathematical operations on more extended integers. Linked lists can also be used to represent sparse matrices.
4. Queue
Similar to a stack, the queue is a linear data structure. The fact that a queue is open at both ends distinguishes it from a stack. As a result, it adheres to the First-In-First-Out (FIFO) structure, meaning that the data item inserted first will also be accessed. Data is added to the queue via one end and removed via the other.
A queue is an ordered list with two ends, the REAR and the FRONT, where operations can be done for insert and deletion, respectively.
![Data Structures Algorithms and Application in C++](https://static.tutorialandexample.com/cpp/data-structures-algorithms-and-application-in-cpp9.png)
Operations in Queue
Some queue operations are initializing a queue, using it, and permanently erasing the data from memory.
The queue’s most common actions are: enqueue(), dequeue(), peek(), isFull(), and isEmpty(). These are all built-in operations to manipulate data and determine the queue's status.
Front and rear pointers are used in the queue. While the rear pointer accesses data from the rear end, the front pointer accesses data from the front end.
Working of Queue
- Initializing two pointers, FRONT, and REAR
- FRONT is the first element
- REAR is the last element
- Assign the value of both pointers to -1
- For insertion (enqueue), check if the queue is full
- Assign the FRONT value to 0
- Increase REAR by 1
- Add new elements with the use of pointer REAR
- For deletion (dequeue), check if the queue is empty
- Return the FRONT value
- Increase FRONT by 1
- Reset FRONT and REAR to -1 for the last element
Program to illustrate Queue in C++
CODE
#include <iostream>
using namespace std;
int search(int arr[], int n, int x) {
for (int i = 0; i < n; i++)
if (arr[i] == x)
return i;
return -1;
}
int main() {
int array[] = {21, 14, 0, 1, 9};
int x = 1;
int n = sizeof(array) / sizeof(array[0]);
int result = search(array, n, x);
(result == -1) ? cout << "Element not found" : cout << "Element found at index: " << result;
}
#include <iostream>
using namespace std;
const int max_s = 100;
class queue {
private: int frnt; //front
int r; //rear
int arr[max_s];
public: queue() {
frnt = -1;
r = -1;
}
bool isFull() {
return (r == max_s - 1);
}
bool isEmpty() {
return (frnt == -1 && r == -1);
}
void enqueue(int x) {
if (isFull()) {
cout << "Queue is full" << endl;
return;
}
if (isEmpty()) {
frnt = 0;
r = 0;
} else {
r++;
}
arr[r] = x;
}
void dequeue() {
if (isEmpty()) {
cout << "Queue is empty" << endl;
return;
}
if (frnt == r) {
frnt = -1;
r = -1;
} else {
frnt++;
}
}
int peek() {
if (isEmpty()) {
cout << "Queue is empty" << endl;
return -1;
}
return arr[frnt];
}
void display() {
if (isEmpty()) {
cout << "Queue is empty" << endl;
return;
}
cout << "Elements in the Queue are: ";
for (int i = frnt; i <= r; i++) {
cout << arr[i] << " ";
}
cout << endl;
}
};
int main() {
queue q;
cout << "\nAdding elements into the queue:" << endl;
q.enqueue(1);
q.enqueue(22);
q.enqueue(31);
q.enqueue(4);
q.enqueue(15);
q.display();
cout << "\nValue of front element is " << q.peek() << endl;
cout << "\nRemoving two elements from the Queue" << endl;
q.dequeue();
q.dequeue();
q.display();
cout << "\nValue of Front element is " << q.peek() << endl;
return 0;
}
OUTPUT
![Data Structures Algorithms and Application in C++](https://static.tutorialandexample.com/cpp/data-structures-algorithms-and-application-in-cpp10.png)
Applications of Queue
- Queues are frequently used as waiting lists for a single shared resource, such as a printer, disc, or CPU.
- Queues are
- employed when data is not being transferred between two processes at the same rate, such as using pipes, file IO, or sockets.
- In the majority of applications, including MP3 media players and CD players, queues serve as buffers.
- To add and remove music from the playlist, media players use queues to keep the list up to date.
Types of Non-Linear Data Structure
1. Trees
An abstract non-linear data type with a hierarchy-based structure is a tree. It comprises links connecting nodes (where the data is kept). Starting from a single node called the Root node, it connects with its subtrees.
![Data Structures Algorithms and Application in C++](https://static.tutorialandexample.com/cpp/data-structures-algorithms-and-application-in-cpp11.png)
Need of Tree Data Structure
Other linear data structures that store data sequentially include arrays, linked lists, stacks, and queues. Any operation in a linear data structure requires more time to complete as the size of the data increases. As a non-linear data structure, different tree data structures make it possible to access the data more quickly.
Terms used in Tree data structure
- Root: The topmost node in the tree data structure is called Root.
- Child: The branch of any node is the child node.
- Parent: The node having sub-nodes is the parent node.
- Sibling: Nodes having the same parent are siblings.
- Leaf Node: The node which doesn’t has its child node is the leaf node.
Types of tree data structure
- General Tree: General trees are unordered tree data structures with a minimum of 0 and a maximum of 'n' subtrees at the root node. The hierarchy of the General trees is unrestricted. As a result, the root node behaves like the superset of every other subtree.
- Binary Tree: The root node of a binary tree, a type of general tree, can only support a maximum of two subtrees: the left and right.
- Binary Search Tree: A non-linear data structure called a binary search tree connects one node to n other nodes. It is a data structure based on nodes. In a binary search tree, a node can be represented by its data component, left-child, and right-child fields. In a binary search tree, a node can connect to its top two child nodes, resulting in the node having two pointers (a left child pointer and a right child pointer).
Applications of using tree
- Data storage for naturally hierarchical structures: Trees are employed to store the data. The files and folders in the file system saved on the disc drive are stored as trees and take the shape of organically hierarchical data.
- Data organization is done to facilitate effective data insertion, deletion, and searching. For instance, searching one element in a binary tree takes logN time.
- Trie: The dictionary is kept in a particular form of a tree.
- Heap: A tree data structure that is also built using arrays. Priority queues are implemented using it.
2. Graphs
An abstract data type, a graph, comprises a collection of items linked. These things are called vertices, and their connections are called edges. Typically, a graph is denoted by the formula G = V, E, where V denotes the set of vertices and E denotes the set of edges. The graph is referred to as a forest if E is empty.
![Data Structures Algorithms and Application in C++](https://static.tutorialandexample.com/cpp/data-structures-algorithms-and-application-in-cpp12.png)
Operations on Graphs
- Depth First Search Traversal: A traversal technique called Depth First Search traverses each vertex in a graph in the order of decreasing depth. This algorithm starts at any node and moves back and forth around the network, marking unvisited nearby nodes until it reaches all of the vertices.
- Breadth-First Search Traversal: Before going to the next level of depth, the breadth-first search traversal algorithm visits each graph vertex at that level. This approach starts at any node and traverses the graph by stopping at each subsequent vertex on the same depth level and marking it until no vertex remains.
Different Data Structure Approaches
There are various approaches to data structures to find the optimum solution to a problem.
1. Greedy Algorithm
A greedy algorithm is a method of problem-solving that chooses the best choice at the time. It is unconcerned with whether the most excellent result at the moment will produce the final best result.
Even if the option was erroneous, the algorithm never goes back and changes its mind. It functions in a top-down manner.
Not all problems can be solved using this approach. It does this because it always seeks to create the optimal outcome at the local level.
Approach to the greedy algorithm
- The solution set, which contains the answers, is initially blank.
- Until a solution is found, an item is added to the solution set at each stage.
- The present item is retained if the solution set is workable.
- If not, the proposal is rejected and never again considered.
Types of Greedy Algorithms
- Selection Sort
- Knapsack Problem
- Minimum Spanning Tree
- Job Scheduling Problem
- Prim's Minimal Spanning Tree Algorithm
- Kruskal's Algorithm
- Dijkstra's Tree Algorithm
- Huffman Coding
2. Dynamic Programming
A dynamic programming technique aids in the speedy resolution of a class of problems with overlapping subproblems and optimal substructure properties.
Any problem's solutions can be kept for later use if they can be broken down into smaller subproblems, which can then be broken down into even smaller subproblems, and if there is an overlap between the subproblems. The CPU's efficiency can be improved in this way. To identify the best solution for these issues, it is necessary to repeatedly calculate the value of the same subproblems.
Working on Dynamic Programming
To access subproblem solutions when needed without recalculating them, dynamic programming stores the results of subproblems. Memorization is the term for this method of storing the value of subproblems. Saving the Array's values lets us speed up computations for minor issues.
We can also implement dynamic programming in a bottom-up fashion by flipping the algorithm's direction, i.e., by starting from the base case and moving toward the solution.
Types of Dynamic programming approach
- Fibonacci number series
- Knapsack problem
- All pair shortest path by Floyd-Warshall
- Shortest path by Dijkstra
- Project scheduling
3. Divide and Conquer
A problem is broken down into several sub-problems using the divide and conquer strategy repeatedly until it can no longer be divided. First, these sub-problems are resolved, and then the results are combined to create the complete solution.
Following is the process for the divide and conquer design technique:
- To further divide the original problem, we divide it into several more minor problems.
- Conquer Recursion is then used to tackle each of these subproblems separately.
- After each subproblem has been resolved, it is combined to create an honest answer to the initial problem.
Algorithms based on Divide and Conquer
- Merge Sort
- Quick Sort
- Binary Search
- Strassen's Matrix Multiplication
- Closest Pair
4. Brute Force Algorithm
It takes a lot of time to run and is inefficient, but the brute force approach is a strategy that guarantees solutions for issues in any domain. It helps with more straightforward problems and provides a solution to be used as a benchmark for evaluating other design techniques.