Following are different types of data structures:
A. Primitive and non-primitive.
Primitive data structure:
The integers, reals, logical data, character data, pointers and reference are primitive data structures.
These data types are available in most programming languages as built in type. data objects of primitive data types can be operated upon by machines level instructions.
These data structures are derived from primitive data structures, A set of homogeneous and heterogeneous data elements are stored together.
Examples of non primitive data structures are array, structures, union, linked list, stack, queue, tree, graph, etc.
B. Linear and non-linear.
Linear data structure:
Elements are arranged in a linear fashion (one dimension)
All one to one relation can be handled through linear data structure.
Stacks and queues are examples of linear data structure.
Non linear data structure:
All one many, many one or many many relations are handled through non linear data structures.
Every data element can have many number of predecessors as tell as successors.
Tree, graph are the example of non linear data structure.
B. Graph and representation of graph:
A graph is an abstract data structure that is used to implement the graph concept from mathematics. it is basically a collection of vertices (also called as notes) and edges that connect these vertices.
A graph G is defined as an ordered set (V,E) where V(G) represent set of vertices and E(G) represents the edges that connect the vertices.
Representation of Graph:
- There are 2 common ways of storing graphs in the computer memory, They are:
A. Sequential representation using adjacency matrix:
An adjacency matrix is used to represent which nodes are adjacent to one another. by definition, two nodes are said to be adjacent, if there is an edge connecting them.
In a directed graph G, if node V D adjacent to node U, then there definitely an edge from u to v. That is, if X is adjacent to u, he can get from u to x by one edge. for any graph a having n nodes, the adjacency matrix will have the dimensions n x n.
In an adjacency matrix, the rows and columns are labeled by graph vertices, an entry aij in the adjacency matrix will contain 1, if vertices vi and vj are adjacent to each other, however if the nodes are not adjacent, aij will be set to zero.
B. Adjacency list:
This structure consists of a lot of all nodes in G, furthermore, every node is in turn linked to its own list that contains the names of all other nodes that are adjacent to it.
For directed graphs, the sum of the lengths of all adjacency lists is equal to the number of edges in G.
However, for an un-directed graph, the sum of the lengths of all adjacency list is equal to twice the number of edges in G, because on edge (u,x) means an edge from node u to v as hell as an edge from v to u.