In this post, we are going to discuss Introduction to Data Structures, different types of data structures and it’s applications as well.
I will try to give overview of all types of data structures used in the real world. So let’s start.
What is Data Structure..?
In simple words, Data Structure is just a way to store and organize data so that it can be used efficiently.
Basically, these are some structures where we store data so that we can access those data in an efficient way. For different purpose, different data structures are used.
Some of the common Data Structures are Array, Structure, Linked List, Stack, Queue, priority queues, Tree, Graph, etc.
So, let’s discuss each and every data structure, it’s advantages and disadvantages as well. We will start from basic data structures and gradually we will move to Advance ones too. (Introduction to data structures)
Types of Data Structures
Data Structures are classified as shown in the diagram below,
Primitive Data Structure includes basic data types like integer, character, float, pointers.
It is also called built-in data structure as these are the basic data types in which data are stored.
Non- Primitive Data structure also called user-defined data structure includes Arrays, Linklist, stack, Trees etc.
Basically we define non-primitive data structures according to our usage to store and manipulate data.
Linear Data Structures
The linear data structure is one of the types of data structure where data are stored and accessed in a sequential manner, however, the elements can be stored in these data structures in any order.
Examples of the linear data structure are Array, Linked List, Stack, Queue, Hashing, etc.
Let me give you an overview of the above linear data structures,
An array is a collection of similar type of data. By similar type, we mean all the data present in the array will be of a single data type.
If we talk about memory, they are stored in a contiguous memory location. For details visit here.
Linked List is also a linear data structure but unlike arrays, linked list elements are not stored at a contiguous memory location, here the elements are linked using pointers.
Linklist also gives benefit over the array, in array searching operation requires O(1) time complexity but insertion and deletion take O(n) time complexity which is a bit costly but these operations in Linked lists are fast.
I will discuss the link list in detail in some other post, but for introduction just remember Linklist is used in a real-world data structure like Graphs and Binary Search tree.
The stack is a linear data structure that follows the LIFO order. LIFO stands for (Last in First Out).
There are some basic operations performed on stack like push(), pop(), top(), isempty() etc. Stack has an enormous number of applications.
push() : Insert element into top of the stack.
pop() : Delete element from top of the stack.
top() : Return the topmost element of the stack.
isempty() : Checks whether stack is empty or not.
size() : Returns the size of the stack.
The queue is also a linear data structure that follows the FIFO order (First in First Out).
In real life, anyone who comes first gets the first priority, queue in computer science depicts the same meaning.
The queue also has the same sets of operations which are defined for stack only instead of top(), the queue has front() and rear() which helps us to retrieve first and last data of the queue.
In a simple queue, we insert data from the rear side and delete data from the front side. There is also a special kind of queue named deque where we can insert and delete from both the sides.(introduction to data structures)
Non-Linear Data Structure
In non – Linear data Structures, elements are not stored in linear manner. In this, the data elements have hierarchical relationship which involves the relationship between the child, parent, and grandparent.
Most common non linear data structures are Trees, Binary Search Trees, Graphs, Heaps, Trie, Segment Tree etc.
In trees, data are stored and accessed in a hierarchical manner.
The most commonly used tree is a Binary tree in which each node has at most two children, which are referred to as the left child and the right child. It is implemented mainly using Links.
I have discussed trees in detail in this post.
Like trees, the Graph is also a nonlinear data structure. The graph has huge applications in the real world. Google Maps, Social Networking sites all works on Graph.
I have discussed the graph in this post. Please go through it for the basic concepts of Graph.
Binary Search Trees
BST is a special type of tree where searching, insertion, and deletions take O(log n) time and for this feature, it is the most efficient data structure for managing data.
The main logic behind BST is that we store elements smaller than root node in left part and elements greater than root in the right part and we maintain this property from very beginning which gives us the advantage of manipulating data in O(log n) time.
Heaps / Priority Queue:
A Heap is a special Tree-based data structure in which the tree is a complete binary tree.
Generally, Heaps are of two types,
In a Max-Heap the key present at the root node must be greatest among the keys present at all of its children. The same property must be recursively true for all sub-trees in that Binary Tree.
In a Min-Heap the key present at the root node must be minimum among the keys present at all of its children. The same property must be recursively true for all sub-trees in that Binary Tree.
Priority Queue is an application of heap. It is basically a queue where priority to superior elements are given while popping element from queue. We will discussed about priority queue in detail later.
There are some advanced data structures as well as Tries, Segment Trees as well which is a bit advance to grasp. This is an introduction to Data structures. Hope you got the basic idea of all data structures.
That’s all folks..!!!