# Difference between Linear and Non Linear Data Structure

## Difference between Linear and Non-Linear Data Structure in Tabular Form

### Comparison Between Linear and Non-Linear Data Structure

• A data structure is simply the implementation of Abstract Data Types using suitable algorithms.
• Mainly Data Structures are classified into two categories
1. Linear
2. Non-Linear

### Comparison Chart

Linear Data Structure Non-Linear Data Structure
Every item is related to its previous and next time Every item is attached with many other items.
Data is arranged in a linear sequence. Data is not arranged in sequence
Data items can be traversed in a single run. Data cannot be traversed in a single run.
Examples: Linked List, Stack, Queue, etc. Examples: Trees, graphs, etc.
Implementation is easy. Implementation is difficult.
Memory utilization Ineffective Memory utilization Effective

### Linear data structures

• A data structure is said to be linear if its elements are connected in a linear fashion by means of logical or in sequence memory locations.
• There are two ways to represent a linear data structure in memory,
• Static memory allocation
• Dynamic memory allocation
• The possible operations on the linear data structure are Traversal, Insertion, Deletion, Searching, Sorting and Merging.
• Examples of Linear Data Structure are Stack and Queue.
• Stack: Stack is a data structure in which insertion and deletion operations are performed at one end only.
• The insertion operation is referred to as ‘PUSH’ and deletion operation is referred to as ‘POP’ operation.
• A stack is also called as Last in First out (LIFO) data structure.
• Queue: The data structure which permits the insertion at one end and Deletion at another end, known as Queue.
• The end at which deletion occurs is known as FRONT end and another end at which insertion occurs is known as a REAR end
• A queue is also called a First in First out (FIFO) data structure.

### Nonlinear data structures

• Nonlinear data structures are those data structures in which data items are not arranged in a sequence.
• Examples of Non-linear Data Structure are Tree and Graph.
• Tree: A tree can be defined as a finite set of data items (nodes) in which data items are arranged in branches and sub-branches according to requirements.
• Trees represent the hierarchical relationship between various elements
• Tree consists of nodes connected by an edge, the node represented by a circle and edge lives connecting to the circle.
• Graph: Graph is a collection of nodes (Information) and connecting edges (Logical relation) between nodes.
• A tree can be viewed as a restricted graph.
• Graphs have many types:
• Un-directed Graph
• Directed Graph
• Mixed Graph
• Multi-Graph
• Simple Graph
• Null Graph
• Weighted Graph