Last Updated on January 9, 2023 by Prepbytes
In this article, we will be discussing the main types of data structures that are used along with their working and real-world application as a part of computer science. A detailed spectrum of different types of data structures is mentioned to give a clear and helpful overview. By the end of this article, the reader will have strong concepts of the aforementioned types of data structures.
Types of Data Structures
There are two different types of data structures which can be termed as follow:-
- Linear Data Structures
- Non-Linear Data Structures
Let’s look at how these two are different from each other with the help of a flow diagram and the key points mentioned below.
| Linear Data Structures | Non-Linear Data Structures |
|---|---|
| 1. Elements are placed adjacent to each other. | 1. Elements not linearly placed but hierarchical. |
| 2. Easy to implement | 2. Less easier to implement than Linear Data Structures |
| 3. Extra memory is created not holding any elements | 3. No extra memory is created with creation performed as per need. |
| 4. Elements can be traversed in a single go | 4. Elements can not be traversed in a single go |
| 5. Only a single level is involved in storage. | 5. Multiple levels are involved for storage. |
Linear Data Structure Types
Array
It consists of one or many elements situated at contiguous memory locations. Array can be assumed as a group of elements of normal integer data type that can be traversed in a single level.
Properties of an Array:
-
First element of array can be accessed with subscript 0 as the first element follows 0 indexing in most of the programming languages in general.
-
Array can include sub-arrays as its elements paving the way for multi-dimensional array that has extensive usages.
-
Abstract data structures like stacks, queue can be implemented with the help of array that has its unique operations.
-
For storage of elements of similar data types, arrays are the most preferred data structures.
Applications of an Array:
- Arrays are an handy option for sorting hence all majority of sorting algorithms are performed using array.
- Image Processing has an extensive use of array with pixels formed using arrays in an image.
- Traversal of matrix and grid-related are commonly implemented using Arrays.
- Most management systems overlooking libraries, hostel and restaurants are functioning using arrays.
- Tasks executed by the Operating Systems like Scheduling is carried out with assistance of an Array.
Linked Lists
Linked List is another linear data structure among the many types of data structure. It is not stored contiguously but dynamic memory allocation is done where the data is stored in the heap memory unlike arrays that utilizes the stack memory for data storage.
Linked List information is divided into two parts, the first is the actual data and other is the address of the next node to which it is linked. To traverse a linked list, we must have the address of the next node at each of the nodes present in the linked list.
There are different variations of the linked list described as follow:
1. Single Linked List
The nodes are interconnected with nodes containing the address to the next linked node and the last node in the linked list pointing to NULL.
2. Circular Linked List
The nodes are interconnected with nodes containing the address to the next linked node and the last node in the linked list pointing to the head node ( or the first node) in the linked list making it a circular linked list.
3. Doubly Linked List
The nodes are interconnected with nodes containing the address to the next linked node as well as the previous node making it a two way address linked list. The previous of the head node points to NULL and next of the last node points to NULL.
4. Circular Doubly Linked List
The nodes are interconnected with nodes containing the address to the next linked node as well as the previous node whilst the previous of the head node points to last node and next of the last node points to head node or the first node making it a circular as well as a doubly linked list.
Properties of a Linked List:
- Linked Lists are stored in heap memory and enable dynamic allocation of storage.
- The end of the linked list is not predetermined but checked at each node whether the address pointing to next node is NULL.
- The initial node of linked list is known as Head while the last node is known as Tail.
- Insertion and Deletion in Linked Lists are less costly as compared to Arrays.
Applications of a Linked List:
- Linked List can be used to implement various types of data structure like Stacks and Queues etc.
- Sorting algorithms like Bucket Sort can be implemented with the help of a linked list.
- It is used for linked files in memory as gallery images have the address to next and previous images.
- Polynomial operations are performed using a linked list where polynomial expressions portray as nodes.
- Linked list are used in scheduling algorithms like Round Robin Scheduling.
Stack
A Stack is a data structure implemented as Abstract Data Tyand follows the Last In First Out Principle (LIFO). The two operations performed on Stack are Push and Pop. The element is removed from the top of the stack and when push is called, an element is inserted at the top of the stack.
In case the stack is empty and pop is performed, the stack will be unharmed as it will return with an assertion on the stack being empty. Top is defined as the element at the top of the stack and in case the stack is empty, the top is undefined or set to -1.
Properties of Stack
- If the stack exceeds the maximum limit of elements, stack overflow error is thrown.
- Recursion is performed under the hood with a stack.
- Insertion and deletion on a stack is performed from only one end. I.e. top of the stack
- Stack is implemented with a linked list or a stack.
Applications of Stack
- Stack is used to check validity of parenthesis
- Reverse Polish and Polish Notation can be obtained with the help of a Stack.
- Stack is helpful in evaluation of an arithmetic expression.
- Redo and Undo operations are real world applications of Stack.
Queue
Queue is another ADT ( Abstract Data Type) that follows the principle of First In First Out ( shortened as FIFO). As the name suggests, it shares similarities with an actual queue where a person at the front leaves and people keep on adding to the queue from the back.
The operation where an element is added to the queue is known as enqueue while the removal of element is termed as dequeue.
Properties of Queue
- Queue can be represented by an array.
- All the elements must be removed from the front to remove the last element.
- Queue has two operations, enqueue and dequeue and follows First in First Out Principle.
Applications of Queue
- Popular Scheduling Algorithm, First Come First Serve follows a queue to execute tasks.
- In music player, queue is maintained to play the songs where the songs added first to the queue are played.
- Interrupts are handled in Operating System using a Queue.
Tree
Tree is a non-linear data structure that contains data and reference to its child nodes (note that a binary tree has reference to two nodes while generic tree can have reference to multiple nodes). The data is arranged hierarchically with data spread across multiple levels.
Here are few of the terminologies used in Tree, node at the top is known as Root Node while the children nodes that share the same parent are known as Siblings. Node with no children is known as Leaf Node.
Properties of Tree
- Tree has nodes connected with each other through edges. The reference is programming made through the address of the child node can be assumed as an edge.
- The distance between a node to the root node can be framed as the depth of the tree.
- The distance between the root node and the deepest possible bode is defined as the height of the tree.
Applications of Tree
- Trees are used to implement folder structures to navigate.
- Binary Search Tree – A variation of the tree is used for fast searching of elements.
- Spanning Trees are used in finding the minimum cost in a tree.
- Decision Tree is used in Machine Learning for decision analysis and study of the data.
Graph
Graph is a non-linear data structure where the vertex (node) is connected by edges. A Graph can be directed or undirected, depicting one way and two way paths respectively.
Properties of Graph
- Edges connect the vertices or the nodes in a graph
- Degree of node is defined as the total connected edges to the node.
- Neighbor node is the adjacent connected nodes with a particular node.
Applications of Graph
- Graphs are extensively used in Google Maps.
- Social Networking Sites function with the help of graph algorithms.
- Modelling in computation is done with techniques involving the Graph Data Structure.
Conclusion
Now that we have come to the end of the article on types of data structure, I hope you have a clear understanding of how these data structures function, their properties and their application. With this, we bind up with the types of data structures.
We hope to see you at PrepBytes again with another helpful information. Thank You
FAQs related to Types of Data Structures
1. Are types of data structures asked for interviews?
Data structures are an essential topic asked in interviews and it is necessary to know the main types of data structures.