Data Structures
The way to organize data
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.
The data structure name indicates organizing the data in memory. There are many ways of organizing the data in the memory, e.g. array in Java language. An array is a collection of memory elements in which data is stored sequentially, i.e., one after another. In other words, we can say that array stores the elements in a continuous manner. This organization of data is done with the help of an array of data structures. There are also other ways to organize the data in memory. Let’s see the different types of data structures.
The data structure is not any programming language like C, C++, java, etc. It is a set of algorithms that we can use in any programming language to structure the data in the memory.
To structure the data in memory, ’n’ number of algorithms were proposed, and all these algorithms are known as Abstract data types. These abstract data types are a set of rules.
Classification of Data Structure:
- Linear data structure: A 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, etc. - 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, etc. - 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.
For example, we can store a list of items having the same data type using the array data structure.
Let’s learn about each type in detail.
Linear data structures
In linear data structures, the elements are arranged in sequence one after the other. Since elements are arranged in a particular order, they are easy to implement.
However, when the complexity of the program increases, the linear data structures might not be the best choice because of operational complexities.
Popular linear data structures are:
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 the 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 at 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 structures
Unlike linear data structures, elements in non-linear data structures are not in any sequence. Instead, they are arranged in a hierarchical manner where one element will be connected to one or more elements.
Non-linear data structures are further divided into graph and tree-based data structures.
1. Graph Data Structure
In the graph data structure, each node is called a 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 a 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
Data structures can also be classified as:
- Static data structure: It is a type of data structure where the size is allocated at the compile time. Therefore, the maximum size is fixed.
- Dynamic data structure: It is a type of data structure where the size is allocated at the run time. Therefore, the maximum size is flexible.
Major Operations:
The major or common operations that can be performed on the data structures are:
- Searching: We can search for any element in a data structure.
- Sorting: We can sort the elements of a data structure either in an ascending or descending order.
- Insertion: We can also insert a new element in a data structure.
- Updation: We can also update the element, i.e., we can replace the element with another element.
- Deletion: We can also perform the delete operation to remove the element from the data structure.
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.
