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++

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.

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

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

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.

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

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.

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

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.

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

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.

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.

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.

← Prev Next →

C++ Tutorial Index

C++ Control Statements

C++ Functions

C++ Arrays

C++ Strings

C++ Inheritance

C++ Polymorphism

C++ Pointers

C++ Exception Handling

C++ Constructors

C++ File Handling

Miscellaneous

Data Structures Algorithms and Application in C++

What is Data Structure?

Why Data Structure and Algorithms?

Different types of data structures

Linear Data Structure

Non-linear Data Structure

Types of linear data structures

1. Array

Representation of Array

Operations on Array

Data types supported with Array:

Program to understand Array in C++

Applications of Array

2. Stack

Representation of Stack

LIFO Principle of Stack

Working

Operations on Stack

Program to understand concepts on the stack in C++

Application of Stack

3. Linked List

Operations in Linked List

Types of Linked Lists

1. Singly Linked List

2. Doubly Linked List

3. Circular Linked List

Program to illustrate Linked List in C++

Application of Linked List

4. Queue

Operations in Queue

Working of Queue

Program to illustrate Queue in C++

Applications of Queue

Types of Non-Linear Data Structure

1. Trees

Need of Tree Data Structure

Terms used in Tree data structure

Types of tree data structure

Applications of using tree

2. Graphs

Operations on Graphs

Different Data Structure Approaches

1. Greedy Algorithm

Approach to the greedy algorithm

Types of Greedy Algorithms

2. Dynamic Programming

Working on Dynamic Programming

Types of Dynamic programming approach

3. Divide and Conquer

Algorithms based on Divide and Conquer

4. Brute Force Algorithm