Common operations on various Data Structures
Last Updated :
27 Mar, 2023
Data Structure is the way of storing data in computer’s memory so that it can be used easily and efficiently. There are different data-structures used for the storage of data. It can also be defined as a mathematical or logical model of a particular organization of data items. The representation of particular data structure in the main memory of a computer is called as storage structure.
For Examples: Array, Stack, Queue, Tree, Graph, etc.
Operations on different Data Structure:
There are different types of operations that can be performed for the manipulation of data in every data structure. Some operations are explained and illustrated below:
- Traversing: Traversing a Data Structure means to visit the element stored in it. It visits data in a systematic manner. This can be done with any type of DS.
Below is the program to illustrate traversal in an array, stack, queue and linkedlist:
Array
#include <iostream>
using namespace std;
int main()
{
int arr[] = { 1, 2, 3, 4 };
int N = sizeof(arr) / sizeof(arr[0]);
for (int i = 0; i < N; i++) {
cout << arr[i] << ' ';
}
return 0;
}
|
Stack
#include <bits/stdc++.h>
using namespace std;
void printStack(stack<int>& St)
{
while (!St.empty()) {
cout << St.top() << ' ';
St.pop();
}
}
int main()
{
stack<int> St;
St.push(4);
St.push(3);
St.push(2);
St.push(1);
printStack(St);
return 0;
}
|
Queue
#include <bits/stdc++.h>
using namespace std;
void printQueue(queue<int>& Q)
{
while (!Q.empty()) {
cout << Q.front() << ' ';
Q.pop();
}
}
int main()
{
queue<int> Q;
Q.push(1);
Q.push(2);
Q.push(3);
Q.push(4);
printQueue(Q);
return 0;
}
|
LinkedList
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
Node* next;
};
Node* newNode(int data)
{
Node* new_node = new Node;
new_node->data = data;
new_node->next = NULL;
return new_node;
}
Node* insertEnd(Node* head, int data)
{
if (head == NULL)
return newNode(data);
else
head->next = insertEnd(head->next, data);
return head;
}
void traverse(Node* head)
{
if (head == NULL)
return;
cout << head->data << " ";
traverse(head->next);
}
int main()
{
Node* head = NULL;
head = insertEnd(head, 1);
head = insertEnd(head, 2);
head = insertEnd(head, 3);
head = insertEnd(head, 4);
traverse(head);
}
|
Time Complexity: O(N)
Auxiliary Space: O(1)
Below is the program to illustrate traversal in an array:
C++
#include <bits/stdc++.h>
using namespace std;
int main()
{
int arr[] = { 1, 2, 3, 4 };
int N = sizeof(arr)/sizeof(arr[0]);
for (int i = 0; i < N; i++) {
cout << arr[i] << " ";
}
return 0;
}
|
Java
import java.util.*;
class GFG{
public static void main(String[] args)
{
int arr[] = { 1, 2, 3, 4 };
int N = arr.length;
for (int i = 0; i < N; i++) {
System.out.print(arr[i] + " ");
}
}
}
|
Python3
if __name__ == '__main__':
arr = [ 1, 2, 3, 4 ];
N = len(arr);
for i in range(N):
print(arr[i], end=" ");
|
C#
using System;
public class GFG {
public static void Main(String[] args) {
int []arr = { 1, 2, 3, 4 };
int N = arr.Length;
for (int i = 0; i < N; i++) {
Console.Write(arr[i] + " ");
}
}
}
|
Javascript
<script>
var arr = [ 1, 2, 3, 4 ];
var N = arr.length;
for (i = 0; i < N; i++) {
document.write(arr[i] + " ");
}
</script>
|
Time Complexity: O(N)
Auxiliary Space: O(1)
Below is the program to illustrate traversal in a Stack:
C++
#include <iostream>
#include <stack>
using namespace std;
void printStack(stack<int> St){
while (!St.empty()) {
cout << St.top() <<" ";
St.pop();
}
}
int main() {
stack<int> St;
St.push(4);
St.push(3);
St.push(2);
St.push(1);
printStack(St);
return 0;
}
|
Java
import java.util.*;
class GFG{
static void printStack(Stack<Integer> St)
{
while (!St.isEmpty()) {
System.out.print(St.peek() +" ");
St.pop();
}
}
public static void main(String[] args)
{
Stack<Integer> St = new Stack<>() ;
St.add(4);
St.add(3);
St.add(2);
St.add(1);
printStack(St);
}
}
|
Python3
def print_stack(St):
while St:
print(St.pop(), end=' ')
St = []
St.append(4)
St.append(3)
St.append(2)
St.append(1)
print_stack(St)
|
C#
using System;
using System.Collections.Generic;
public class GFG {
static void printStack(Stack<int> St) {
while (St.Count != 0) {
Console.Write(St.Peek() + " ");
St.Pop();
}
}
public static void Main(String[] args)
{
Stack<int> St = new Stack<int>();
St.Push(4);
St.Push(3);
St.Push(2);
St.Push(1);
printStack(St);
}
}
|
Javascript
<script>
function printStack(St)
{
while (St.length != 0)
{
document.write(St.pop() + " ");
}
}
var St = [];
St.push(4);
St.push(3);
St.push(2);
St.push(1);
printStack(St);
</script>
|
Time Complexity: O(N)
Auxiliary Space: O(1)
- Searching: Searching means to find a particular element in the given data-structure. It is considered as successful when the required element is found. Searching is the operation which we can performed on data-structures like array, linked-list, tree, graph, etc.
Below is the program to illustrate searching an element in an array, stack, queue and linkedlist:
Array
#include <iostream>
using namespace std;
void findElement(int arr[], int N, int K)
{
for (int i = 0; i < N; i++) {
if (arr[i] == K) {
cout << "Element found!";
return;
}
}
cout << "Element Not found!";
}
int main()
{
int arr[] = { 1, 2, 3, 4 };
int K = 3;
int N = sizeof(arr) / sizeof(arr[0]);
findElement(arr, N, K);
return 0;
}
|
Stack
#include <bits/stdc++.h>
using namespace std;
void findElement(stack<int>& St, int K)
{
while (!St.empty()) {
if (St.top() == K) {
cout << "Element found!";
return;
}
St.pop();
}
cout << "Element Not found!";
}
int main()
{
stack<int> St;
St.push(4);
St.push(3);
St.push(2);
St.push(1);
int K = 3;
findElement(St, K);
return 0;
}
|
Queue
#include <bits/stdc++.h>
using namespace std;
void findElement(queue<int>& Q, int K)
{
while (!Q.empty()) {
if (Q.front() == K) {
cout << "Element found!";
return;
}
Q.pop();
}
cout << "Element Not found!";
}
int main()
{
queue<int> Q;
Q.push(1);
Q.push(2);
Q.push(3);
Q.push(4);
int K = 3;
findElement(Q, K);
return 0;
}
|
LinkedList
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
Node* next;
};
Node* newNode(int data)
{
Node* new_node = new Node;
new_node->data = data;
new_node->next = NULL;
return new_node;
}
Node* insertEnd(Node* head, int data)
{
if (head == NULL)
return newNode(data);
else
head->next = insertEnd(head->next, data);
return head;
}
bool traverse(Node* head, int K)
{
if (head == NULL)
return false;
if (head->data == K)
return true;
return traverse(head->next, K);
}
int main()
{
Node* head = NULL;
head = insertEnd(head, 1);
head = insertEnd(head, 2);
head = insertEnd(head, 3);
head = insertEnd(head, 4);
int K = 3;
if (traverse(head, K)) {
cout << "Element found!";
}
else {
cout << "Element Not found!";
}
}
|
Time Complexity: O(N)
Auxiliary Space: O(1)
- Insertion: It is the operation which we apply on all the data-structures. Insertion means to add an element in the given data structure. The operation of insertion is successful when the required element is added to the required data-structure. It is unsuccessful in some cases when the size of the data structure is full and when there is no space in the data-structure to add any additional element. The insertion has the same name as an insertion in the data-structure as an array, linked-list, graph, tree. In stack, this operation is called Push. In the queue, this operation is called Enqueue.
Below is the program to illustrate insertion in array, stack, queue and linkedlist :
Array
#include <iostream>
using namespace std;
void printArray(int arr[], int N)
{
for (int i = 0; i < N; i++) {
cout << arr[i] << ' ';
}
}
int main()
{
int arr[4];
int N = 4;
for (int i = 1; i < 5; i++) {
arr[i - 1] = i;
}
printArray(arr, N);
return 0;
}
|
Stack
#include <bits/stdc++.h>
using namespace std;
void printStack(stack<int>& St)
{
while (!St.empty()) {
cout << St.top() << ' ';
St.pop();
}
}
int main()
{
stack<int> St;
St.push(4);
St.push(3);
St.push(2);
St.push(1);
printStack(St);
return 0;
}
|
Queue
#include <bits/stdc++.h>
using namespace std;
void printQueue(queue<int>& Q)
{
while (!Q.empty()) {
cout << Q.front() << ' ';
Q.pop();
}
}
int main()
{
queue<int> Q;
Q.push(1);
Q.push(2);
Q.push(3);
Q.push(4);
printQueue(Q);
return 0;
}
|
LinkedList
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
Node* next;
};
Node* newNode(int data)
{
Node* new_node = new Node;
new_node->data = data;
new_node->next = NULL;
return new_node;
}
Node* insertEnd(Node* head, int data)
{
if (head == NULL)
return newNode(data);
else
head->next = insertEnd(head->next, data);
return head;
}
void traverse(Node* head)
{
if (head == NULL)
return;
cout << head->data << " ";
traverse(head->next);
}
int main()
{
Node* head = NULL;
head = insertEnd(head, 1);
head = insertEnd(head, 2);
head = insertEnd(head, 3);
head = insertEnd(head, 4);
traverse(head);
}
|
Time Complexity: O(N)
Auxiliary Space: O(1)
- Deletion: It is the operation which we apply on all the data-structures. Deletion means to delete an element in the given data structure. The operation of deletion is successful when the required element is deleted from the data structure. The deletion has the same name as a deletion in the data-structure as an array, linked-list, graph, tree, etc. In stack, this operation is called Pop. In Queue this operation is called Dequeue.
Below is the program to illustrate dequeue in Stack, Queue and Linkedlist:
Stack
#include <bits/stdc++.h>
using namespace std;
void printStack(stack<int> St)
{
while (!St.empty()) {
cout << St.top() << ' ';
St.pop();
}
}
int main()
{
stack<int> St;
St.push(4);
St.push(3);
St.push(2);
St.push(1);
printStack(St);
cout << endl;
St.pop();
printStack(St);
return 0;
}
|
Queue
#include <bits/stdc++.h>
using namespace std;
void printQueue(queue<int> myqueue)
{
while (!myqueue.empty()) {
cout << myqueue.front() << ' ';
myqueue.pop();
}
}
int main()
{
queue<int> myqueue;
for (int i = 1; i < 5; i++) {
myqueue.push(i);
}
printQueue(myqueue);
cout << endl;
myqueue.pop();
printQueue(myqueue);
return 0;
}
|
LinkedList
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
Node* next;
};
Node* newNode(int data)
{
Node* new_node = new Node;
new_node->data = data;
new_node->next = NULL;
return new_node;
}
Node* insertEnd(Node* head, int data)
{
if (head == NULL)
return newNode(data);
else
head->next = insertEnd(head->next, data);
return head;
}
void traverse(Node* head)
{
if (head == NULL)
return;
cout << head->data << " ";
traverse(head->next);
}
int main()
{
Node* head = NULL;
head = insertEnd(head, 1);
head = insertEnd(head, 2);
head = insertEnd(head, 3);
head = insertEnd(head, 4);
traverse(head);
if (head->next != NULL) {
head = head->next;
}
else {
head = NULL;
}
cout << endl;
traverse(head);
}
|
Time Complexity: O(N)
Auxiliary Space: O(1)
Some other method :
Create: –
It reserves memory for program elements by declaring them. The creation of data structure
Can be done during
- Compile-time
- Run-time.
You can use malloc() function.
Selection:-
It selects specific data from present data. You can select any specific data by giving condition in loop .
Update
It updates the data in the data structure. You can also update any specific data by giving some condition in loop like select approach.
Sort
Sorting data in a particular order (ascending or descending).
We can take the help of many sorting algorithms to sort data in less time. Example: bubble sort which takes O(n^2)time to sort data. There are many algorithms present like merge sort, insertion sort, selection sort, quick sort, etc.
Merge
Merging data of two different orders in a specific order may ascend or descend. We use merge sort to merge sort data.
Split Data
Dividing data into different sub-parts to make the process complete in less time.
Please Login to comment...