Difference between Linear and Non Linear Data Structure

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 :

  1. Linear
  2. Non-Linear

Image Source



Comparison Chart

Linear Data StructureNon-Linear Data Structure
Every item is related to its previous and next timeEvery 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 IneffectiveMemory 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
      • Multi-Graph
      • Simple Graph
      • Null Graph
      • Weighted Graph



LEAVE A REPLY

Please enter your comment!
Please enter your name here