Data Structures
The data structure represents the logical relationship of the particular data sets. In this section you are going to learn about some of the data structures which we will discuss in detail in further units.
Data structures can be divided in to two types
- Linear data structure
- Non Linear data structure
Linear data structure
When the data is stored in the memory in linear or sequential form is called linear data structure. Examples of linear data structures include Array, Stack, Queue, Linked list.
Non Linear data structure
When the data is stored in the memory in dispersed or non sequential order is called non linear data structure. Example of non linear data structures includes trees, graphs, files etc.
Arrays
Linear array (one dimensional array) is the simplest type of data structures. Linear array means a list of a finite number n of similar data type referenced respectively by a set of n consecutive numbers 1, 2, 3… n. For example, if the name of the array is A then the elements of array A are denoted by the bracket notation.
A [1], A [2], A [3]… A [N]
Where the number N in A [N] is called a subscript and A [N] is called a subscripted variable.
Linked Lists
Linked list is a way to store data in memory. A linked list consists of a series of nodes, which are not necessarily adjacent in memory. Each node contains the data field which has the element and the next field which has the link to the node containing its successor.
Generally in linked list the elements are connected by the link field which contains the address of the next node. The link field of last node is marked by null pointer which indicates the end of the list and a START variable which contains the address of the first node in the list. The figure shows the linked list.
Stack
It is a linear list in which insertions and deletions are restricted at one end, called the top. The following figure shows a stack with 5 elements and the top pointer where both insertion and deletion are performed.
Stack contains two operation push and pop. Push is used to insert an element into stack and pop is used to remove an element from stack. It is also called as last- in first- out (LIFO), because the element pushed last need to be popped out first.
Queue
It is a linear list in which insertion and deletion will take place in different end. As shown in figure the end where we insert an element is called the “rear” end and deletion at “front” end. The element entered first need to be removed first, so it is also called as first- in first- out (FIFO).
Trees
Tree is a nonlinear data structure which contains the hierarchical relationship between various elements is called a tree. One node is distinguished as a root, every other node is connected by a directed edge from exactly one other node, with the direction of parent -> children as referred in the figure.
Graph
Data sometimes contain a relationship between pairs of elements which is necessarily hierarchical in nature. The data structure referred in figure 1.8 reflects this type of relationship is called a graph.
