What are data structures?
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.
A data structure is not only used for organizing the data. It is also used for processing, retrieving, and storing data. There are different basic and advanced types of data structures that are used in almost every program or software system that has been developed.
Classification of Data Structure:
Data structures are basically of two types:
1. Linear Data Structure 2. Non-linear Data Structure
Linear Data Structure:
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, etc.
It is of two types :
Static Data structures: The 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 structures: 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.
Need Of Data structure:
The structure of the data and the synthesis of the algorithm are relative to each other. Data presentation must be easy to understand so the developer, as well as the user, can make an efficient implementation of the operation.
Data structures provide an easy way of organizing, retrieving, managing, and storing data.
The data structure is needed as:
Data structure modification is easy.
It requires less time.
Save storage memory space.
Data representation is easy.
Easy access to the large database.
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.
Linear Data structures:
1. Array Data Structure:
An array is a collection of data items stored at contiguous memory locations. The idea is to store multiple items of the same type together. This makes it easier to calculate the position of each element by simply adding an offset to a base value, i.e., the memory location of the first element of the array (generally denoted by the name of the array).
2. Linked list:
A linked list is a linear data structure that includes a series of connected nodes. Here, each node stores the data and the address of the next node.
3. Stack Data Structure:
In the stack data structure, elements are stored in the LIFO(Last In Fast Out) or FILO(First In Last Out) principle. That is, the last element stored in a stack will be removed first.
Mainly the following three basic operations are performed in the stack:
Initialize: Make a stack empty.
Push: Adds an item in the stack. If the stack is full, then it is said to be an Overflow condition.
Pop: Removes an item from the stack. The items are popped in the reversed order in which they are pushed. If the stack is empty, then it is said to be an Underflow condition.
Peek or Top: Returns the top element of the stack.
isEmpty: Returns true if the stack is empty, else false.
3. Queue Data Structures:
Like Stack, Queue is a linear structure that follows a particular order in which the operations are performed. The order is First In First Out (FIFO). In the queue, items are inserted at one end and deleted from the other end. A good example of a queue is any queue of consumers for a resource where the consumer that came first is served first. The difference between stacks and queues is in removing. In a stack we remove the item the most recently added; in a queue, we remove the item the least recently added.
A queue is an object (an abstract data structure - ADT) that allows the following operations:
Enqueue: Add an element to the end of the queue
Dequeue: Remove an element from the front of the queue
IsEmpty: Check if the queue is empty
IsFull: Check if the queue is full
Peek: Get the value of the front of the queue without removing it
Non-Linear Data Structure:
1. Graph:
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:
2. Trees Data Structure
Similar to a graph, a tree is also a collection of vertices and edges. However, in the tree data structure, there can only be one edge between two vertices.
Popular Tree-based Data Structure
