In this article, we will learn about basic and important difference between linear and non linear data structure along with types of data structure with it’s examples.
Data structure is a way to organize or to store a data in computer so that it can be used or retrieved efficiently (quickly) whenever it is needed.
Data Structure is a representation of logical relationship exiting between individual elements of data.
For example: Data stored in dictionary always organized in sorted order so that they can be searched very easily when reader wants to find some words from it. On the other hand, think if the data do not stored in sorted order in word dictionary then how much it might be difficult for everyone to find something from dictionary. In this case, Dictionary is useful for us only when all information that we want from dictionary is organized in proper manner so that it can be searched effectively in short time.
In computer science, Data Structure is classified into two categories : Linear and Non Linear Data Structure
- Linear Data Structure
- Non Linear Data Structure
Classifications of Data Structure : Linear and Non Linear Data Structure | Image Source
Linear Data Structure
The data structure where data items are organized sequentially or linearly where data elements attached one after another is called linear data structure. Data elements in a liner data structure are traversed one after the other and only one element can be directly reached while traversing. All the data items in linear data structure can be traversed in single run.
These kind of data structures are very easy to implement because memory of computer is also organized in linear fashion.
Examples of linear data structures are Arrays, Stack, Queue and Linked List.
- An array is a collection of data items having the same data types.
One Dimensional Array
All the data elements stored in the array is of same type like char, int, float, double. Data in the array can be accessed by index of an array and this index generally starts from 0 to n-1, where n is size of an array.
Types of Array:
- Single dimension array
- Multi dimension array
- A stack is a LIFO (Last In First Out) data structure where element that added last will be deleted first. All operations on stack are performed from on end called TOP. A TOP is a pointer which points to the top element- the element which entered last in the stack.
Basic Operations on Stack :
Insertion of element in the stack is called as PUSH and Deletion of element from the stack is called POP operation.
- A queue is a FIFO (First In First Out) data structure where element that added first will be deleted first. In queue, insertion is performed from one end called REAR and deletion is performed from another end called FRONT.
Basically there a four types of Queue.
- Simple Queue
- Circular Queue
- Dequeue (Double Ended Queue)
- Priority Queue
Basic Operations on Queue :
Insertion of element in the queue is called as ENQUEUE and deletion of element from the queue is called DEQUEUE operation.
- A linked list is a collection of nodes, where each node is made up of a data element and a reference to the next node in the sequence.
Singly Linked List
It is a linear collection of data elements. These elements are called nodes. Linked list can also be used to implement other data structures like stack and queue.
Basically there a four types of Linked List.
- Singly Linked List
- Doubly Linked List
- Circular Singly Linked List
- Circular Doubly Linked List
Basic Operations on Linked List :
Non Linear Data Structure
The data structure where data items are not organized sequentially is called non linear data structure. In other words, A data elements of the non linear data structure could be connected to more than one elements to reflect a special relationship among them. All the data elements in non linear data structure can not be traversed in single run.
Examples of non linear data structures are Trees and Graphs.
- A tree is collection of nodes where these nodes are arranged hierarchically and form a parent child relationships.
A tree is recursively defined as a set of one or more nodes where one node is designated as the root of the tree and all the remaining nodes can be partitioned into non empty sets each of which is a sub tree of the root.
Types of Trees
- General trees
- Binary trees
- Binary search trees
- Expression trees
- Tournament trees
- A Graph is a collection of a finite number of vertices and an edges that connect these vertices. Edges represent relationships among vertices that stores data elements.
Types of Graphs
- Directed Graph
- Undirected Graph
- Weighted Graph