### 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

#### 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

##### 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

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

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

- The value contained in all the nodes in its left. Sub-tree are less than the
- 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

in physical, biological and social systems. Many problems of practical interest

can be represented by graph.

communication, data organization, computational devices, the flow of

computation, etc.

which traffic might be directed over the internet.