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.
    Graph

    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.

    Graph is written as

    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.