What is Data Structure?
A data structure is a storage that is used to store and organize data. It is a way of arranging data on a computer so that it can be accessed and updated efficiently.
Depending on your requirement and project, it is important to choose the right data structure for your project. For example, if you want to store data sequentially in the memory, then you can go for the Array data structure.
Types of Data Structure
There are two types of data structures:
- Primitive data structure
- Non-primitive data structure
Primitive Data structure
The primitive data structures are primitive data types. The int, char, float, double, and pointer are primitive data structures that can hold a single value.
Non-Primitive Data structure
The non-primitive data structure is divided into two types:
- Linear data structure
- Non-linear data structure
Linear data structures
The data structure in which data elements are arranged sequentially or linearly, where each element is attached to its previous and next adjacent elements, is called a linear data structure.
Examples of linear data structures are array, stack, queue, linked list, and more..
- Static data structure: Static data structure has a fixed memory size. It is easier to access the elements in a static data structure. An example of this data structure is an array.
- Dynamic data structure: In the dynamic data structure, the size is not fixed. It can be randomly updated during the runtime which may be considered efficient concerning the memory (space) complexity of the code. Examples of this data structure are queue, stack, and more.
1. Array Data Structure
In an array, elements in memory are arranged in continuous memory. All the elements of an array are of the same type. And, the type of elements that can be stored in the form of arrays is determined by the programming language.
2. Stack Data Structure
In stack data structure, elements are stored in the LIFO principle. That is, the last element stored in a stack will be removed first.
It works just like a pile of plates where the last plate kept on the pile will be removed first.
3. Queue Data Structure
Unlike stack, the queue data structure works in the FIFO principle where the first element stored in the queue will be removed first.
It works just like a queue of people in the ticket counter where the first person in the queue will get the ticket first.
4. Linked List Data Structure
In a linked list data structure, data elements are connected through a series of nodes. And, each node contains the data items and addresses to the next node.
Non-linear data structure
Data structures where data elements are not placed sequentially or linearly are called non-linear data structures. In a non-linear data structure, we can’t traverse all the elements in a single run only.
Examples of non-linear data structures are trees and graphs.
1. Graph Data Structure
In the graph data structure, each node is called vertex and each vertex is connected to other vertices through edges.
Popular Graph Based Data Structures:
- Spanning Tree and Minimum Spanning Tree
- Strongly Connected Components
- Adjacency Matrix
- Adjacency List
2. Trees Data Structure
Similar to a graph, a tree is also a collection of vertices and edges. However, in tree data structure, there can only be one edge between two vertices.
Popular Tree-based Data Structure:
- Binary Tree
- Binary Search Tree
- AVL Tree
- B-Tree
- B+ Tree
- Red-Black Tree
Major Operations Of Data Structure
The major or the common operations that can be performed on the data structures are:
- Traversing: Every data structure contains the set of data elements. Traversing the data structure means visiting each element of the data structure in order to perform some specific operation like searching or sorting. Example: If we need to calculate the average of the marks obtained by a student in 6 different subject, we need to traverse the complete array of marks and calculate the total sum, then we will divide that sum by the number of subjects i.e. 6, in order to find the average.
- Insertion: Insertion can be defined as the process of adding the elements to the data structure at any location. If the size of data structure is n then we can only insert n-1 data elements into it.
- Deletion: The process of removing an element from the data structure is called Deletion. We can delete an element from the data structure at any random location. If we try to delete an element from an empty data structure then underflow occurs.
- Searching: The process of finding the location of an element within the data structure is called Searching. There are two algorithms to perform searching, Linear Search and Binary Search. We will discuss each one of them later in this tutorial.
- Sorting: The process of arranging the data structure in a specific order is known as Sorting. There are many algorithms that can be used to perform sorting, for example, insertion sort, selection sort, bubble sort, etc.
- Merging: When two lists List A and List B of size M and N respectively, of similar type of elements, clubbed or joined to produce the third list, List C of size (M+N), then this process is called merging
Advantages of Data structures
The following are the advantages of a data structure:
- Efficiency: If the choice of a data structure for implementing a particular ADT is proper, it makes the program very efficient in terms of time and space.
- Reusability: The data structure provides reusability means that multiple client programs can use the data structure.
- Abstraction: The data structure specified by an ADT also provides the level of abstraction. The client cannot see the internal working of the data structure, so it does not have to worry about the implementation part. The client can only see the interface.
Need of Data Structures
As applications are getting more complexed and amount of data is increasing day by day, there may arrise the following problems:
Processor speed: To handle very large amout of data, high speed processing is required, but as the data is growing day by day to the billions of files per entity, processor may fail to deal with that much amount of data.
Data Search: Consider an inventory size of 106 items in a store, If our application needs to search for a particular item, it needs to traverse 106 items every time, results in slowing down the search process.
Multiple requests: If thousands of users are searching the data simultaneously on a web server, then there are the chances that a very large server can be failed during that process
In order to solve the above problems, data structures are used. Data is organized to form a data structure in such a way that all items are not required to be searched and required data can be searched instantly.
Frequently Asked Question About Data Structure
Which data structure is used in recursion?
The stack data structure is used in recursion.
Which data structure is used to store a string?
There are three ways to store strings:
- Fixed length (array type structure)
- Variable length but the maximum size is fixed during the running time (pointer type structure)
- Linked list structure
Which data structure may produce an overflow?
A Linear Queue implemented using a static array can throw an overflow error even if its number of elements is less than its size.
A Linear Queue is a linear data structure that works with the First In First Out (FIFO) approach, i.e., the first element to enter the queue will leave the first element to leave the queue. The front of a linear queue is the end from which elements are dequeued from the queue, whereas the rear of a linear queue is the end from which new elements are enqueued into the queue.
Which data structure has a fixed size?
An array is a structure of fixed size, which can hold items of the same data type.
Which data structure is used for balancing symbols?
Stack is used for balancing of symbols. This is extensively used by the compiler to check for missing or additional symbols.
How graphs in data structure can be represented?
A graph can be represented using 3 data structures- adjacency matrix, adjacency list and adjacency set.
Take the test for this lesson
[ld_quiz quiz_id=”237608″]