People have been referring to computer information that is communicated or stored as “data” since the development of computers. On the other hand, order types also contain data. Data might take the shape of printed numbers or sentences and bytes saved in the memory of electrical devices or knowledge that has been mentally preserved. This data became an important part of everyone’s daily lives as the world became more modern, and different implementations allowed people to store it in various ways by using Data structure operations.
Data Structure
Computer science has a subfield called as data structures. Understanding data organization and flow management by studying data structures enables us to optimize any process or program’s efficiency. Data Structure is a specific method of storing and organizing data in the computer’s memory to retrieve and effectively use it later quickly. A data structure is a logical or mathematical representation of a certain type of data organization. Data can be managed in a variety of ways.
A specific data model’s scope is determined by two things:
- The data must first be sufficiently put into the structure to indicate a clear association between the data and a physical item.
- Second, the structure should be so simple that anyone may learn how to analyze the data effectively as needed.
Data structures include things like arrays, linked lists, stacks, queues, trees, etc. Nearly every area of computer science, including compiler design, operating systems, graphics, artificial intelligence, and many others, makes extensive use of data structures.
The essential component of many algorithms in computer science is a data structure, which enables programmers to manage data efficiently. As the primary goal of the software is to save and retrieve user data as quickly as possible, it is essential to enhance the performance of an application or piece of software.
Any software or code is constructed from data structures. It can be very difficult for a programmer to choose the right data structure for a project.
When discussing data structures, the following basic terms are frequently used:
- Data: A collection of values or an elementary value are both acceptable definitions of data. Examples of employee-related data include the name and ID of the employee.
- Data Items: Data Items are single units of value.
- Group Items: Group Items are data items that have subordinate data items. An employee’s name, for instance, could include their first, middle, and last names.
- Elementary Items: Data items classified as elementary cannot be subdivided into other items. Using an employee’s ID as a demonstration.
- Entity and Attribute: An entity represents a class of specific objects. It is made up of several Attributes. Each attribute represents a particular attribute of that entity.
Different Operations on Data Structure
A variety of Data structure operations that can be used to manipulate the data. The following operations are described and shown:
Traversing
A data structure’s elements can be visited by traversing through it. It makes systematic visits to the data. Any DS can be used to accomplish this. The program used to demonstrate traversal in an array, stack, queue, and linked list is shown below:
Array:
#include <iostream>
using namespace std;
int main()
{
int elements[] = { 10, 20, 30, 40 }; // Initialize an array with elements
int arraySize = sizeof(elements) / sizeof(elements[0]); // Calculate the size of the array
for (int index = 0; index < arraySize; index++) {
cout << elements[index] << ' '; // Output each element of the array
}
return 0;
}
Output:
10 20 30 40
Stack:
#include <iostream>
#include <stack>
void displayStack(std::stack<int>& customStack)
{
while (!customStack.empty()) {
std::cout << customStack.top() << ' ';
customStack.pop();
}
}
int main()
{
std::stack<int> myStack;
myStack.push(8);
myStack.push(6);
myStack.push(4);
myStack.push(2);
displayStack(myStack);
return 0;
}
Output:
2 4 6 8
Queue:
#include <iostream>
#include <queue>
void displayQueue(std::queue<int>& que) {
while (!que.empty()) {
std::cout << que.front() << ' ';
que.pop();
}
}
int main() {
std::queue<int> que;
que.push(1);
que.push(2);
que.push(3);
que.push(4);
displayQueue(que);
return 0;
}
Output:
1 2 3 4
Linked List:
#include <iostream>
struct ListNode {
int value;
ListNode* next;
};
ListNode* createNode(int value) {
ListNode* newNode = new ListNode;
newNode->value = value;
newNode->next = nullptr;
return newNode;
}
ListNode* insertAtEnd(ListNode* head, int value) {
if (head == nullptr)
return createNode(value);
else
head->next = insertAtEnd(head->next, value);
return head;
}
void traverseList(ListNode* head) {
if (head == nullptr)
return;
std::cout << head->value << " ";
traverseList(head->next);
}
int main() {
ListNode* listHead = nullptr;
listHead = insertAtEnd(listHead, 1);
listHead = insertAtEnd(listHead, 2);
listHead = insertAtEnd(listHead, 3);
listHead = insertAtEnd(listHead, 4);
traverseList(listHead);
return 0;
}
Output:
1 2 3 4
- Time Complexity: O(N)O(N)
- Auxiliary Space: O(1)O(1)
The program used to demonstrate array traversal is shown below in different programming languages:
C++:
#include <iostream>
int main() {
// Create an array
int numbers[] = { 1, 2, 3, 4 };
// Calculate the size of the array
int arraySize = sizeof(numbers) / sizeof(numbers[0]);
// Iterate through the array elements
for (int index = 0; index < arraySize; index++) {
// Display the current element
std::cout << numbers[index] << " ";
}
return 0;
}
Output:
1 2 3 4
Java:
import java.util.*;
class ArrayTraversal {
public static void main(String[] args) {
int[] arrayValues = { 1, 2, 3, 4 };
int arraySize = arrayValues.length;
for (int index = 0; index < arraySize; index++) {
System.out.print(arrayValues[index] + " ");
}
}
}
Output:
1 2 3 4
Python:
# Python program for traversing an array
# Entry point
if __name__ == '__main__':
# Initialize an array
my_array = [ 1, 2, 3, 4 ]
# Determine the array size
array_size = len(my_array)
# Iterate through array elements
for index in range(array_size):
# Display the element
print(my_array[index], end=" ")
Output:
1 2 3 4
C#:
using System;
public class ArrayTraversal {
public static void Main(string[] args) {
// Initialize the array
int[] numbers = { 1, 2, 3, 4 };
// Get the length of the array
int arrayLength = numbers.Length;
// Iterate through the elements of the array
for (int index = 0; index < arrayLength; index++) {
// Display the current element
Console.Write(numbers[index] + " ");
}
}
}
Output:
1 2 3 4
- 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;
// Function to display the elements in the stack
void displayStack(stack<int> myStack){
// Iterate through the stack
while (!myStack.empty()) {
// Display the top element
cout << myStack.top() <<" ";
// Remove the top element
myStack.pop();
}
}
int main() {
// Initialize a stack
stack<int> myStack;
// Push elements onto the stack
myStack.push(4);
myStack.push(3);
myStack.push(2);
myStack.push(1);
// Display elements in the stack
displayStack(myStack);
return 0;
}
Output:
1 2 3 4
Java:
import java.util.*;
class StackTraversalExample {
// Function to print the elements in the stack
static void printStackElements(Stack<Integer> stack) {
// Traverse the stack
while (!stack.isEmpty()) {
// Print the top element
System.out.print(stack.peek() + " ");
// Remove the top element
stack.pop();
}
}
public static void main(String[] args) {
// Initialize the stack
Stack<Integer> numberStack = new Stack<>();
// Add elements to the stack
numberStack.add(9);
numberStack.add(7);
numberStack.add(5);
numberStack.add(3);
// Print elements in the stack
printStackElements(numberStack);
}
}
Output:
3 5 7 9
Python:
# Custom function to display stack elements
def display_stack(stack):
# Iterate through the stack
while stack:
# Display the top element
print(stack.pop(), end=' ')
# Example usage of the function
stack_example = []
stack_example.append(4)
stack_example.append(3)
stack_example.append(2)
stack_example.append(1)
display_stack(stack_example)
Output:
1 2 3 4
C#:
using System;
using System.Collections.Generic;
public class StackTraversal {
static void PrintStack(Stack<int> stack) {
while (stack.Count != 0) {
Console.Write(stack.Peek() + " ");
stack.Pop();
}
}
public static void Main(String[] args) {
Stack<int> myStack = new Stack<int>();
myStack.Push(4);
myStack.Push(3);
myStack.Push(2);
myStack.Push(1);
PrintStack(myStack);
}
}
Output:
1 2 3 4
- Time Complexity: O(N)
- Auxiliary Space: O(1)
Searching
Searching is locating a specific piece within a given data structure. When the necessary component is located, the attempt becomes successful. We may execute searches on various data structures, including arrays, linked lists, trees, graphs, etc. The program to find an element in an array, stack, queue, and linked list is shown below.
Array:
#include <iostream>
using namespace std;
void searchArray(int array[], int size, int target)
{
for (int index = 0; index < size; index++)
{
if (array[index] == target)
{
cout << "Target element found!";
return;
}
}
cout << "Target element not found!";
}
int main()
{
int data[] = {1, 2, 3, 4};
int targetValue = 3;
int arraySize = sizeof(data) / sizeof(data[0]);
searchArray(data, arraySize, targetValue);
return 0;
}
Output:
Target element found!
Stack:
#include <iostream>
#include <stack>
void searchInStack(std::stack<int>& customStack, int target)
{
while (!customStack.empty())
{
if (customStack.top() == target)
{
std::cout << "Target element found!" << std::endl;
return;
}
customStack.pop();
}
std::cout << "Target element not found." << std::endl;
}
int main()
{
std::stack<int> customStack;
customStack.push(4);
customStack.push(3);
customStack.push(2);
customStack.push(1);
int targetElement = 3;
searchInStack(customStack, targetElement);
return 0;
}
Output:
Target element found!
Queue:
#include <iostream>
#include <queue>
void searchInQueue(std::queue<int>& myQueue, int target) {
while (!myQueue.empty()) {
if (myQueue.front() == target) {
std::cout << "Target element found!" << std::endl;
return;
}
myQueue.pop();
}
std::cout << "Target element not found." << std::endl;
}
int main() {
std::queue<int> myQueue;
myQueue.push(1);
myQueue.push(2);
myQueue.push(3);
myQueue.push(4);
int targetElement = 3;
searchInQueue(myQueue, targetElement);
return 0;
}
Output:
Target element found!
Linked List:
// C++ program to traverse a linked list
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
};
Node* createNode(int data) {
Node* new_node = new Node;
new_node->data = data;
new_node->next = nullptr;
return new_node;
}
Node* insertAtEnd(Node* head, int data) {
if (head == nullptr)
return createNode(data);
else
head->next = insertAtEnd(head->next, data);
return head;
}
bool search(Node* head, int target) {
if (head == nullptr)
return false;
if (head->data == target)
return true;
return search(head->next, target);
}
int main() {
Node* head = nullptr;
head = insertAtEnd(head, 1);
head = insertAtEnd(head, 2);
head = insertAtEnd(head, 3);
head = insertAtEnd(head, 4);
int target = 3;
if (search(head, target)) {
cout << "Target element found!";
} else {
cout << "Target element not found!";
}
return 0;
}
Output:
Target element found!
- Time Complexity: O(N)
- Auxiliary Space: O(1)
Deletion
It is a method we use on all data structures. A data structure’s element can be deleted using deletion. When the necessary element is removed from the data structure, the deletion operation is successful. A deletion in a data structure, such as an array, linked list, graph, tree, etc., has the same name. This procedure is known as Pop in a stack. Dequeue is the name of this operation in Queue.
The program to demonstrate dequeue in a stack, queue and LinkedList is provided below.
Stack:
// C++ program for demonstrating stack insertion
#include <iostream>
#include <stack>
using namespace std;
// Function to display the elements in a stack
void displayStack(stack<int> s)
{
// Traverse the stack
while (!s.empty()) {
// Display the top element
cout << s.top() << ' ';
// Remove the top element
s.pop();
}
}
// Main function
int main()
{
// Initialize a stack
stack<int> s;
// Insert elements into the stack
s.push(9);
s.push(7);
s.push(5);
s.push(3);
// Display elements before performing
// pop operation on the stack
displayStack(s);
cout << endl;
// Perform pop operation on the stack
s.pop();
// Display elements after pop operation
displayStack(s);
return 0;
}
Output:
3 5 7 9
5 7 9
Queue:
#include <iostream>
#include <queue>
using namespace std;
void displayQueue(queue<int> q) {
while (!q.empty()) {
cout << q.front() << ' ';
q.pop();
}
}
int main() {
queue<int> myQueue;
for (int i = 1; i < 5; i++) {
myQueue.push(i);
}
cout << "Queue elements before pop: ";
displayQueue(myQueue);
cout << endl;
myQueue.pop();
cout << "Queue elements after pop: ";
displayQueue(myQueue);
return 0;
}
Output:
Queue elements before pop: 1 2 3 4
Queue elements after pop: 2 3 4
LinkedList:
#include <bits/stdc++.h>
using namespace std;
struct ListNode {
int value;
ListNode* next;
};
ListNode* createNode(int value) {
ListNode* new_node = new ListNode;
new_node->value = value;
new_node->next = NULL;
return new_node;
}
ListNode* insertAtEnd(ListNode* head, int value) {
if (head == NULL)
return createNode(value);
else
head->next = insertAtEnd(head->next, value);
return head;
}
void traverseList(ListNode* head) {
if (head == NULL)
return;
cout << head->value << " ";
traverseList(head->next);
}
int main() {
ListNode* head = NULL;
head = insertAtEnd(head, 1);
head = insertAtEnd(head, 2);
head = insertAtEnd(head, 3);
head = insertAtEnd(head, 4);
// Print elements before removing the first element
traverseList(head);
// Move head pointer forward to remove the first element
if (head->next != NULL) {
head = head->next;
} else {
head = NULL;
}
cout << endl;
// Print elements after removing the first element
traverseList(head);
}
Output:
1 2 3 4
2 3 4
- Time Complexity: O(N)
- Auxiliary Space: O(1)
Insertion
It is a method we use on all data structures. Insertion refers to the act of adding a new element to a data structure. When the required element is added to the required data structure, the insertion operation is successful. In other instances, it fails because there is no more room to add any more elements to the data structure because it is already full. The insertion is known by the same term as an insertion into an array, linked list, graph, or data tree. This action is referred to as Push in a stack. This action is referred to as Enqueue in the queue.
The program to demonstrate insertion in an array, stack, queue, and linked list is provided below.
Array:
#include <iostream>
using namespace std;
// Function to display array elements
void displayArray(int elements[], int size) {
for (int index = 0; index < size; index++) {
// Display the element
cout << elements[index] << ' ';
}
}
// Main function
int main() {
// Initialize an integer array
int numbers[4];
// Size of the array
int size = 4;
// Populate the array with elements
for (int i = 1; i < 5; i++) {
numbers[i - 1] = i;
}
// Display array elements
displayArray(numbers, size);
return 0;
}
Output:
1 2 3 4
Stack:
#include <iostream>
#include <stack>
using namespace std;
void displayStack(stack<int>& myStack)
{
while (!myStack.empty()) {
cout << myStack.top() << ' ';
myStack.pop();
}
}
int main()
{
stack<int> myStack;
myStack.push(4);
myStack.push(3);
myStack.push(2);
myStack.push(1);
displayStack(myStack);
return 0;
}
Output:
1 2 3 4
Queue:
#include <iostream>
#include <queue>
void displayQueue(std::queue<int>& myQueue) {
while (!myQueue.empty()) {
std::cout << myQueue.front() << ' ';
myQueue.pop();
}
}
int main() {
std::queue<int> myQueue;
myQueue.push(10);
myQueue.push(20);
myQueue.push(30);
myQueue.push(40);
displayQueue(myQueue);
return 0;
}
Output:
10 20 30 40
Linked List:
#include <iostream>
struct Node {
int data;
Node* next;
};
Node* createNode(int value) {
Node* newNode = new Node;
newNode->data = value;
newNode->next = nullptr;
return newNode;
}
Node* insertAtEnd(Node* head, int value) {
if (head == nullptr)
return createNode(value);
else
head->next = insertAtEnd(head->next, value);
return head;
}
void printLinkedList(Node* head) {
if (head == nullptr)
return;
std::cout << head->data << " ";
printLinkedList(head->next);
}
int main() {
Node* head = nullptr;
head = insertAtEnd(head, 1);
head = insertAtEnd(head, 2);
head = insertAtEnd(head, 3);
head = insertAtEnd(head, 4);
printLinkedList(head);
return 0;
}
Output:
1 2 3 4
- Time Complexity: O(N)
- Auxiliary Space: O(1)
Create
Declaring them sets aside memory for program elements.
Data structures can be created during the following:
- Compile-time
- Run-time
The malloc() function is available.
Selection
It chooses particular data from the current data. By including a condition in the loop, you can choose any particular piece of data.
Update
The data in the data structure is updated. By including a condition in the loop, similar to the select approach, you may also update any particular data.
Sort
Sorting is the action of ordering the data items in a data structure by particular key values in a predetermined order (ascending or descending). Sorting the student records in an array is possible using the students’ names, registration numbers, or test scores. To meet the user’s processing requirements, each sorting will employ a distinct set of criteria.
Sorting data in a particular order (ascending or descending) order. To sort data quickly, we can use a variety of sorting methods. A bubble sort, for instance, sorts data in O(n2)O(n2) time. There are many kinds of algorithms, including quick sort, insertion sort, merge sort, and selection sort.
Below is the table of different sorting techniques along with their time complexity:
| Algorithm | Best Time Complexity | Average Time Complexity | Worst Time Complexity | Space Complexity |
|---|---|---|---|---|
| Selection Sort | $Ω(n^2)$ | $θ(n^2)$ | $O(n^2)$ | $O(1)$ |
| Bubble Sort | $Ω(n)$ | $θ(n^2)$ | $O(n^2)$ | $O(1)$ |
| Insertion Sort | $Ω(n)$ | $θ(n^2)$ | $O(n^2)$ | $O(1)$ |
| Heap Sort | $Ω(n log(n))$ | $θ(n log(n))$ | $O(n log(n))$ | $O(1)$ |
| Quick Sort | $Ω(n log(n))$ | $θ(n log(n))$ | $O(n^2)$ | $O(n)$ |
| Merge Sort | $Ω(n log(n))$ | $θ(n log(n))$ | $O(n log(n))$ | $O(n)$ |
| Bucket Sort | $Ω(n +k)$ | $θ(n +k)$ | $O(n^2)$ | $O(n)$ |
| Radix Sort | $Ω(nk)$ | $θ(nk)$ | $O(nk)$ | $O(n + k)$ |
| Count Sort | $Ω(n +k)$ | $θ(n +k)$ | $O(n +k)$ | $O(k)$ |
| Shell Sort | $Ω(n log(n))$ | $θ(n log(n))$ | $O(n^2)$ | $O(1)$ |
| Tim Sort | $Ω(n)$ | $θ(n log(n))$ | $O(n log (n))$ | $O(n)$ |
| Tree Sort | $Ω(n log(n))$ | $θ(n log(n))$ | $O(n^2)$ | $O(n)$ |
| Cube Sort | $Ω(n)$ | $θ(n log(n))$ | $O(n log(n))$ | $O(n)$ |
Merge
It is possible to merge data from two different orders in an ascending or descending order. To combine sorts of data, we utilize merge sort.
Merging can be considered simply appending a group of elements from one data structure after elements from another data structure with the same element structure. For instance, two arrays with the same fields and student information from two distinct classes can be combined to make one list. Sorting may or may not be present in the final data structure.
Split Data
Dividing data into many sub-components to speed up the process.
FAQs
Q. What are the three fundamental Data structure operations?
A. Examples of basic operations include adding a data item to the data structure, removing a data item from the data structure, and accessing a specific data item.
Q. What is a fundamental Data structure operations?
A. Print each individual array element in a traversal operation. Insertion: Inserts a new element at the specified index. Deletes the element at the specified index. Use the provided index or value to search for an element. updates the element at the specified index.
Q. What are the six data structure operations?
A. Traversal, Insertion, Deletion, Searching, Sorting, and Merging are some operations that can be performed on a linear data structure. Stack and queue are two examples of linear data structures.
Conclusion
- Algorithms are constructed from data structures. Data structure operations are the foundation for understanding algorithms.
- Data is arranged in data structures in memory. They specify how different bits of data relate to one another and make it easy to access and change that data.
- We suggest reading a series of articles on Scaler if you want to learn more about Data structure operations in-depth.
- Finally, we advise choosing a language like
JavaorC++when you are prepared to begin building Data structure operations. You can implement data structures in these languages however you like. - We hope that this post has given you a better understanding of data structures and how to use them to solve issues. Please get in touch if you have any queries on how to begin using data structures.
Supercharge Your Coding Skills! Enroll Now Our Scaler Academy DSA Course and Master Algorithmic Excellence.
