Contents

**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****Linear****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 is a data structure in which insertion and deletion operations are performed at one end only.**Stack**- 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.

: The data structure which permits the insertion at one end and Deletion at another end, known as Queue.*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.
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.*Tree*:- 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 is a collection of nodes (Information) and connecting edges (Logical relation) between nodes.*Graph*:- 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