Linear and Non-Linear Data Structure

Data structure

Data is organized in many different ways. The logical and mathematical model of a particular organization of data is called data structure.

There are two types of data structure
  • Liner data structure
  • Non-linear data structure

  • Linear data structure

    A data structure whose element form a sequence means the element are processed one after the other. And every element has a unique predecessor or successor.

    Four major operations on linear data structure

    Traversal: it is the process of visiting each element or item in the data structure exactly one.
    Searching: it is the process of finding the particular element in the data structure with a given key value.
    Inserting: it is the process of adding a new element in the data structure.
    Deleting: is the process of deleting the existing element from the data structure.

    Two example of Linear data structure
  • Queue
  • Stack
  • Applications of Queue
    • Queues are frequently used in computer programming and the typical example is the creation of job queue by an operating system. If the operating system does not use priorities, then the jobs are processed in the order they enter the system.
    • A queue also stores key stroke data as we type at the keyboard.
    • When the jobs are submitted to a network printer, they are arranged in order of arrival. Thus essentially jobs went to a printer are placed on a queue.
    • Virtually every rear life time a queue, for example lines at ticket counter at cinema halls, railway station, bus stands etc. are queues because their service is provided on first come first serve basis.
    Applications of Stack
    • Stacks are used for the evaluation of applications which are of the postponed natures.
    • used for the conversion of infix notation to postfix notation.
    • Stacks are used for the quick sort.
    • used for the replacement of recursion in case of game of Towers of Hanoi.
    • Stacks are used as a intermediate data structure in case of all the traversals of trees.

    Non-linear data structure:

    Non-linear data structures are those types in which the representing of data is not on sequence basis.

    The following are the types of non-linear data structures
  • Trees
  • Graphs
  • Trees

    Tree is one of the most important non-linear data structures. It is extremely useful whenever data naturally fit together in a hierarchical structure.
    Data contained in the tree exist in a logical relationship i.e like that of parents to children. Each node, or child in the tree may have on, many, or no children.

    Types of trees are
  • Binary tree
  • Expression tree
  • Tournament tree
  • Binary search tree
  • Threaded tree
  • AVL tree
  • B-trees
  • Applications of Tree
    • The trees are used to implement mathematical expression:
      Algebraic expression such as ((5+z)/8)*(4^2) has an inherent tree like structure.
      The expression trees are usually binary tree. Three traversal method are in-order, post-order and preorder.
      The in-order traversal of the tree visit the node in the order as ((5+z)/8*(4^2))
    • Heep trees are used to implement heap sort and priority queue.
    • The trees are used to implement binary search tree: Binary search is a special form of binary tree whose nodes are arranged in such a way that for every node N of T has the following property:
      • The value contained in all the nodes in its left. Sub-tree are less than the value contained in the node N.
      • The value contained in all the nodes in its right sub-tree are greater than or equal to the value contained in the node N.
    • Huffman tree are used to generate Hufffman code which makes the character storage and transmission more efficient.

    The tree structure is a special kind of graph in which the relationship between parent and child is hierarchical. A general graph is a structure that represents a less restrictive relationship between data elements. A graph is a set of points and wet of lines, with each line joining and pointing to another. The points are called nodes or vertices of the graph and lines are called edges.

    G = (V E)
    V = Set of Vertices or nodes
    E = Set of edges

    Applications of Graph
  • They can be used to model many types of relations and process dynamics in physical, biological and social systems. Many problems of practical interest can be represented by graph.
  • In computer science, graph are used to represent networks of communication, data organization, computational devices, the flow of computation, etc.
  • Graph theory is also used to study molecules in chemistry and physics.
  • Graphs are used for dynamically modeling the status of a set of routes by which traffic might be directed over the internet.