Difference between Linear and Non-Linear Data Structure in Tabular Form
A data structure is simply the implementation of Abstract Data Types using suitable algorithms.
Mainly Data Structures are classified into two categories :
|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 logically 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.
- 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.
- End at which deletion occurs is known as FRONT end and another end at which insertion occurs is known as a REAR end
- Queue is also called as First in First out (FIFO) data structure.
Nonlinear data structures
- Nonlinear data structures are those data structure 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 requirement.
- 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
- Simple Graph
- Null Graph
- Weighted Graph