Data structure can be defined as the group of data elements which provides an efficient way of storing, organizing, accessing and manipulating data in the computer.
- Storing data means how data is actually stored in computer.
- Organizing data means the practice of categorizing and classifying data to make it more usable.
- Accessing data means how data can be accessed from the storage.
- Manipulating data means the modification of information to make it easier to read.
Data structures are computer algorithms used to store and organize data. They are used to store data in a way that makes it easier to access, modify, and manage. Data structures are used in a variety of applications, such as databases, search engines, computer graphics, and artificial intelligence. Data structures can also be used to create efficient algorithms for solving problems. Examples of data structures include linked lists, trees, stacks, queues, and graphs.
Advantages of Data Structures:
1. Improved Data Organization: Data structures provide a way to organize data in a logical and efficient manner. This makes it easier to access and modify data, resulting in improved data organization.
2. Faster Data Retrieval: Data structures can be used to store data in such a way that it can be retrieved quickly. This helps improve performance and reduce the time needed to access and process data.
3. Better Memory Utilization: Data structures can be used to reduce the amount of memory used to store data. This helps improve memory utilization and reduce the amount of memory needed for a given task.
4. Algorithm Design: Data structures can be used to design efficient algorithms. By using the appropriate data structure for a given task, algorithms can be designed to run faster and more efficiently.
5. Improved Data Security: Data structures can be used to make data more secure. By organizing data in a secure manner, it can make it harder for unauthorized users to access and modify the data.
Terms Used in Data Structure:
Data: Data is information that has been organized for a specific purpose. For example, a list of customer names and emails is data.
Group Item: A group item is an item that is grouped together with other related items. For example, a list of books and their authors can be grouped together as books.
Record: A record is a collection of data elements that describes a single entity. For example, a customer record might include the customer’s name, address, phone number, and email address.
Entity: An entity is a real-world object or concept that can be represented in a database. For example, a customer is an entity.
Attribute or Field: An attribute or field is the smallest unit of data within a record. For example, a customer’s name is an attribute.
File: A file is a collection of related data stored in a computer system. For example, a customer database is a file.
Need of Data Structures:
- Data structures are essential for efficient data storage and retrieval.
- Data structures help in organizing data in the form of records, which makes it easier to access information.
- Data structures provide algorithms for searching, sorting and manipulating data.
- Data structures help in reducing the time complexity of a program by providing efficient solutions for data manipulation.
- Data structures also help in reducing space complexity by using appropriate data structures that take up lesser memory.
- Data structures help in providing efficient solutions for solving complex problems.
- Data structures help in developing efficient algorithms to solve problems.
- Data structures are used in the development of various software applications.
Types of Data Structures:
- Linear Data Structure:
Linear data structure is a type of data structure in which data elements are arranged in a linear fashion. It is a type of data structure in which data elements are connected to each other in a sequential manner.
Features of Linear Data Structures:
• Linear data structures are easy to understand and implement.
• Linear data structures are easier to traverse than non-linear data structures.
• Linear data structures provide faster access to data elements than non-linear data structures.
• Linear data structures are memory efficient.
• Linear data structures are not suitable for large datasets.
Types of Linear Data Structure:
I. Array:
An array is a data structure that stores a collection of items in a specific order. It is a fundamental data structure that is used in many different algorithms and is often used to store collections of objects. Arrays can be indexed, meaning that each element can be accessed directly by its numerical index. Arrays can also be multi-dimensional, meaning that each element is itself an array.
Features of an array include:
-Fast lookup: Arrays are indexed, meaning that elements can be quickly accessed by their numerical index.
–Constant time insertion and deletion: Elements can be added and removed from the beginning or end of an array in constant time.
-Order preservation: Elements in an array are stored in the order in which they were added.
–Dynamic resizing: Arrays can be dynamically resized, meaning that elements can be added or removed without needing to reallocate memory.
ii. Linked List:
A linked list is a data structure that consists of a series of nodes. Each node contains data elements and a link to the next node. The last node in a linked list points to a null value. Linked lists are used to store data in a linear fashion, and are often used to implement other data structures such as stacks and queues.
Features of a linked list include:
1. Dynamic size: Linked lists can grow or shrink in size as needed. This makes it a great choice when you do not know how many elements you will need to store ahead of time.
2. Insertion and removal: It is easy to add and remove nodes from a linked list, making it a great choice for applications that requires frequent changes.
3. Sequential access: All of the elements in a linked list are stored sequentially, which makes it easy to traverse the list and access data.
4. Memory usage: Linked lists require less memory than other data structures since they only store the data and the link to the next node.
Types of Linked List:
1. Singly Linked List: A singly linked list is a type of data structure in which each node is composed of a data field and a reference(link) to the next node in the list. It is a linear data structure, and each node is not connected to the previous node, only the next node.
Features:
• Easy to insert and delete elements.
• Faster access time than array.
• Memory usage is more efficient than array.
• Can be used to implement stacks and queues.
2. Doubly Linked List: A doubly linked list is a type of data structure in which each node is composed of a data field, a reference (link) to the next node in the list, and a reference (link) to the previous node in the list. It is a linear data structure, and each node is connected to the previous and next nodes.
Features:
• Easy to insert and delete elements.
• Faster access time than array.
• Memory usage is more efficient than array.
• Can be used to implement stacks and queues.
• Easy to traverse in both directions.
iii. Stack:
A stack is a type of data structure that follows the Last-In-First-Out (LIFO) principle, meaning the last element added to the stack is the first element removed from it. It is an abstract data structure consisting of a collection of elements, each identified by an index, where the primary operations are push and pop as follows:
Push: The push operation adds an element to the top of the stack.
Pop: The pop operation removes an element from the top of the stack.
Peek: The peek operation returns the value at the top of the stack without removing it.
IsEmpty: The isEmpty operation checks if the stack is empty or not.
iv. Queue:
A queue is a type of data structure that follows the First-In-First-Out (FIFO) principle, meaning the first element added to the queue is the first element removed from it. It is an abstract data structure consisting of a collection of elements, each identified by an index, where the primary operations are enqueue and dequeue.
Enqueue: The enqueue operation adds an element to the end of the queue.
Dequeue: The dequeue operation removes an element from the front of the queue.
Peek: The peek operation returns the value at the front of the queue without removing it.
IsEmpty: The isEmpty operation checks if the queue is empty or not.
- Non Linear Data Structure:
Non-linear data structures are data structures that are not organized in a linear fashion, such as in a linked list or array. Non-linear data structures are used to store and organize data in a way that allows for efficient search and retrieval of data. The two most common non-linear data structures are trees and graphs.
Features:
1. Flexibility: Nonlinear data structures offer great flexibility in terms of data organization. For example, a graph, which is a nonlinear data structure, can be used to represent relationships between elements in a network.
2. Storage Efficiency: Nonlinear data structures can often store data more efficiently than linear structures. For example, a tree can store data in a hierarchical structure, which allows for quick retrieval of data elements.
3. Dynamic Memory Allocation: Nonlinear data structures allow for dynamic memory allocation and deallocation, making them more suitable for applications that require frequent updates of data.
4. Complexity: Nonlinear data structures are often more complex than linear data structures, as they involve relationships between elements. This complexity can make them difficult to analyze and understand.
Tree:
A tree is a hierarchical data structure that can be used to store data in an organized manner. Trees consist of nodes and edges, where each node represents an item of data and each edge represents a connection between two nodes. A tree typically has a root node, which is the topmost node in the tree, and each node can have any number of children.
Graph:
A graph is a non-linear data structure that consists of nodes and edges, where each node represents an item of data and each edge represents a connection between two nodes. Unlike trees, graphs do not have a root node and can contain cycles, meaning that a node can be connected to itself. Graphs are commonly used to represent networks, such as social networks or transportation networks.
Differences between tree and graph:
Basic Operations in Data Structure:
Searching:
Searching in an array is a process of finding a particular element in an array. An array is a data structure that stores a collection of elements, each of which can be accessed by an index. To search an array, you can iterate through the array, checking each element to see if it is the element you are searching for.
Example of Linear search in C:
#include<stdio.h>
#include<conio.h>
void main()
{
clrscr();
int list[20],size,i,key;
printf(“Enter the required list size: “);
scanf(“%d”,&size);
printf(“Enter any %d numbers: “,size);
for(i = 0; i < size; i++)
{
scanf(“%d”,&list[i]);
}
printf(“Enter the element you want to Search: “);
scanf(“%d”,&key);
// Linear Search Logic
for(i = 0; i < size; i++) {
if(key == list[i]) {
printf(“Searched Element is found at %d index”, i);
break;
}
}
if(i == size)
printf(“Searched element is not found in the list!!!”);
getch();
}
Example of Binary Search in C:
#include<stdio.h>
#include<conio.h>
void main()
{
clrscr();
int c, f, l, m, n, s, a[100];
printf(“Enter number of elements\n”);
scanf(“%d”, & n);
printf(“Enter %d integers\n”, n);
for (c = 0; c < n; c++)
{
scanf(“%d”, & a[c]);
}
printf(“Enter value to find\n”);
scanf(“%d”, &s);
f = 0;
l= n – 1;
m = (f + l) / 2;
while (f <= l)
{
if (a[m] < s)
f = m + 1;
else if (a[m] == s)
{
printf(“%d found at location %d.\n”, s, m + 1);
break;
}
else {
l = m – 1;
}
m = (f + l) / 2;
}
if (f> l)
printf(“Not found! %d is not present in the list.\n”, s);
getch();
}
Sorting:
Sorting is the process of arranging elements of an array in a certain order. This can be done in several ways, such as ascending, descending, or alphabetical order.
For example, here is a program written in C that sorts an array of integers in ascending order:
#include <stdio.h>
int main()
{
int arr[10] = {1, 5, 3, 9, 4, 2, 8, 7, 6, 0};
int i, j, a;
printf(“Given array is: \n”);
for(i=0; i<10; i++)
{
printf(“%d “, arr[i]);
}
printf(“\n”);
/* Sort the array in ascending order */
for(i=0; i<10; i++)
{
for(j=i+1; j<10; j++)
{
if(arr[i] > arr[j])
{
a = arr[i];
arr[i] = arr[j];
arr[j] = a;
}
}
}
printf(“Sorted array is: \n”);
for(i=0; i<10; i++)
{
printf(“%d “, arr[i]);
}
return 0;
}
Output:
Given array is:
1 5 3 9 4 2 8 7 6 0
Sorted array is:
0 1 2 3 4 5 6 7 8 9
Insertion:
In the insertion operation, we are adding one or more elements to the array. Based on the requirement, a new element can be added at the beginning, end, or any given index of array.
#include <stdio.h>
#include<conio.h>
#define MAX 5
void main()
{
Clrscr();
int array[MAX] = {2, 3, 4, 5};
int N = 4; // number of elements in array
int i = 0; // loop variable
int value = 1; // new data element to be stored in array
// print array before insertion
printf(“Printing array before insertion −\n”);
for(i = 0; i < N; i++) {
printf(“array[%d] = %d \n”, i, array[i]);
}
// now shift rest of the elements downwards
for(i = N; i >= 0; i–) {
array[i+1] = array[i];
}
// add new element at first position
array[0] = value;
// increase N to reflect number of elements
N++;
// print to confirm
printf(“Printing array after insertion −\n”);
for(i = 0; i < N; i++) {
printf(“array[%d] = %d\n”, i, array[i]);
}
getch();
}
Output:
Deletion:
Deleting an item from an array in a C program can be done by shifting all elements after the item to be deleted one position back, and then reducing the size of the array by 1. For example, let’s say we have an array arr[] and we want to delete arr[2]. The following C program demonstrates how to do this:
#include<stdio.h>
#include<conio.h>
void main()
{
clrscr();
int array[100], position, c, n;
printf(“Enter number of elements in array\n”);
scanf(“%d”, &n);
printf(“Enter %d elements\n”, n);
for (c = 0; c < n; c++)
{
scanf(“%d”, &array[c]);
}
printf(“Enter the location where you wish to delete element\n”);
scanf(“%d”, &position);
if (position >= n+1)
printf(“Deletion not possible.\n”);
else
{
for (c = position – 1; c < n – 1; c++)
{
array[c] = array[c+1];
}
printf(“Resultant array:\n”);
for (c = 0; c < n – 1; c++)
{
printf(“%d\n”, array[c]);
}
}
getch();
}
Traversing:
Traversing an array is the process of iterating over the elements in an array and performing an operation on each element. This could involve retrieving data from the array, modifying the elements, or both.
// Example of traversing an item from an array in C
#include <stdio.h>
#include<conio.h>
void main()
{
int arr[5] = {1, 2, 3, 4, 5}; // initialize array
int i;
// traverse through the array
for (i = 0; i < 5; i++)
{
printf(“%d\n”, arr[i]); // print the item of the array
}
getch();
}
Exercise:
- What is data structure and why is it important in computer programming?
- What are the different types of data structures and how are they classified?
- What are arrays and how do they differ from linked lists?
- Differentiate between queue and stack.
- Explain different operations performed on queue and stack.
- What are the differences between tree and graph?
- Explain linked list in detail.
- WAP to input any 10 numbers and search any item based on user requirement using linear search.
- WAP to input any 10 numbers and display them in descending order.
- WAP to input any t10 numbers and delete the 5th item from the array and display the result.
End of Chapter I