DATA STRUCTURE NOTES FOR DIPLOMA

data structure notes for exam

DATA STRUCTURE NOTES FOR EXAMS

::::::: TOPIC DESCRIPTION :::::::

What is data structure ?

Types of data structure.

Operation on data structure.

What is array and types of array ?

What is linked list and it's type ?

What is stack and operation on stack ?

What is queue and operation on queue ?

What is stack notation ?

primitive vs non primitive data structure

Difference between stack and queue ?

What is tree ?

What is graph ?

Difference between tree and graph

..................................................................

DATA STRUCTURE ( PART_01 )

01. What is data structure ?

Definition : Data structure is a way of organising and retrieving all data item and relationship to each other.

In other words, The logical and mathematical modal of particular organization of a data is known as data structure.

02. Types of data structure : There are two types of data structure :

1. Primitive data structure : It is also known as fundamental or basic or built-in data structure. It is predefined data type . For example : int ,char ,float ,double, void etc.
2. Non primitive data structure :

Non primitive data type is also known as derived data type. It is user define data type . For example : array , structure, union ,stack ,queue ,linked list ,tree graph etc.

There are two types of non primitive data structure :

Linear data structure : For example,array ,stack ,queue ,linked list etc.

Non linear data structure : For example ,Tree and graph .

03. Operation on data structure:

These data structure operation are given below :
1. Insertion : Adding a new data in data structure is known as insertion.
2. Deletion : removing the data from Data Structure is known as deletion.
3. Shorting : arranging the element in increasing or decreasing order is known as sorting.
4. Merging : combining the data of two different sorted files into a single sorted files is known as merging.
5. Searching : finding the location of data in data structure is known as searching.
6. Traversing : accessing each data elements exactly once in the data structure is known as traversing .

......................................................................................................................................

DATA STRUCTURE ( PART_02 )

04. What is array and types of array ?

* Array definition :

Array is a collection of same data type elements.

Array are always stored in consecutive memory location.

Array can be stored multiple value which can be refferenced by a single name .

The size of an array is fixed .

In array , random access is posible .

It takes less searching time and more wastage memory .

* TYPES OF AN ARRAY :

(¡) Single dimensional array

It is also known as one dimmentional array.

It has only one subscript [ ] value .

(¡¡) Multidimentional array

It is also known as two dimentional array.

It has two subscript [ ] value .

* DECLARATION OF AN ARRAY :

Syntax : data_type array_name[10] ;

* INITIALIZATION OF AN ARRAY :

There are two ways to initialize an array

(¡) Compile time initialization :

Syntax : data_type array_name[size] ={list of value} ;

For example : -

data_type array_name[10] ={3,5,2,7,9,1,8} ;

(¡¡) Run time initialization :

Syntax : data_type array_name[size]=value;

For example : data_type array_name[]=10 ;

05. What is linked list and it's type ?

* Definition :

Linked list is a linear data structure in which contiguous memory location is not required.

The size of linked list is not fixed .

It takes more searching time and more memory space .

In linked list , insertion and deletion is easy .

There are mainly three types of linked list : -
(¡) Singly linked list :

In singly linked list , each nodes are divided into two parts first part is known as info and second part is known as address part .

Each nodes are connected to each other .

Address part of the first node is connected to the info part in the second nodes .

The last node has a reference to null. The entry point into a linked list is known as head of the list .

(¡¡) Doubly linked list :

doubly linked list is a type of linked list in which , each nodes are divided into three parts : prev , info and next .

The info part contains the data ,the prev part contains the address of the previous nodes and the next part contains next node .
doubly linked list can be used in navigation systems where both front and back nevigation is required .

It is also used in various application to implement undo and redo functionality .

(¡¡¡) Circular linked list :

Circular linked list is similar to the singly linked list except that the last node points to the first node in the list .

Circular linked list is a types of linked list in which the first elements points to the last elements and the last element points to the first elements.

The circular linked list is used in round robin scheduling algorithms, multiplayer games repeats the songs in playlist to implement undo function .

06. What is stack and operation on stack ?

* Definition :

Stack is a linear data structure in which insertion and deletion is easy.

Stack follows the principle of last in first out (LIFO) .

It is also known as LIFO because the last added element will be the first to be removed from the stack .

In stack , TOP is a variable which contains the position of top most element.

If stack is empty then TOP == -1

If stack is full then TOP ==N-1 .

* OPERATION ON STACK : -

Stack performs two operation they are : -

(¡) . PUSH OPERATION :

It is a process of adding new element to the top of the stack .
Every push operation, TOP is incremented by one .

i.e TOP = TOP +1

If stack is full then you want to adding an element ,this condition is known as stack overflow .

(¡¡). POP OPERATION :

It is a process of deleting an element to the top of the stack .
Every pop operation, TOP is decremented by one .

I.e TOP = TOP -1

If stack is empty then you want to delete an element ,this condition is known as stack underflow .

..............................................................................................................................................

DATA STRUCTURE ( PART_03 )

07. What is queue and operation on queue ?

It is also a linear data structure.

Queue follows the principle of first in first out (FIFO) .

Stack perform two operation : -

(¡). Enqueue operation. : It is used to insert an element.

(¡¡). De queue operation. : -

It is used to delete the element.

08. What is stack notation ?

There are mainly three stack notation :

(¡). Prefix notation :

In this notation , operator is written before the operators .
It is also known as polish notation .
For example : +AB

Here A and B are operands and + is operator .

(¡¡). Infix notation :

In this notation , the operator is written in between the operands.
For example :. A+B.

Here A and B are operands and + is operator .

(¡¡¡). Postfix notation :

It is also known as suffix notation .

In this notation , operator is written after the operands .

09 Difference between primitive non primitive data structure .

* PRIMITIVE DATA STRUCTURE : -

It is also known as fundamental or basic or built-in data structure.

It is pre-defined data structure .

For example : int ,char ,float ,double, void etc.

It is not dependent any other data structure but it depends upon itself .

* NON-PRIMITIVE DATA STRUCTURE : -

Non primitive data type is also known as derived data type.

It is user define data structure .

For example : array , structure, union ,stack ,queue ,linked list ,tree , graph etc
It depends upon primitive data structure .

......................................................................................................................................

DATA STRUCTURE ( PART_04 )

10. Difference between stack and queue ?

* STACK : -

It is a linear data structure.

Stack follows the principle of last in first out (LIFO) .

Stack perform two operation : -

(¡). Push operation. : -

It is used to insert an element.

(¡¡). Pop operation : -

It is used to delete an element.

* QUEUE : -

It is also a linear data structure.

Queue follows the principle of first in first out (FIFO) .

Stack perform two operation : -

(¡). Enqueue operation. :

It is used to insert an element.

(¡¡). De queue operation. : -

It is used to delete the element.

11. What is tree ?

* TREE : -

A tree is a hierarchical data structure which have more than one elements which is known as tree .

Tree is a non linear data structure which have parent child relationship .

Tree is a simple connected acyclic graph .

It is a collection of nodes and edges .

i.e T = {nodes , edges }

Tree is a hierarchical model .

It has (N - 1 ) edges where N is the total number of nodes .

Application of tree :

It is used to taking decision for searching, inserting , deleting and updating any element in the tree .

For example :

* TYPES OF TREE : -

There are various types of tree -

1. BINARY TREE
2. BINARY SEARCH TREE
3. COMPLETE BINARY TREE
4. STRICT BINARY TREE
5. ALMOST COMPLETE BINARY TREE
6. PERFECT BINARY TREE

12. What is graph ?

* GRAPH DATA STRUCTURE : -

It is also a non linear data structure .

In graph data structure, parent child relationship is is not possible .

It is also a collection of nodes and edges .

i.e G = {nodes , edges }

Graph is a network model data structure .

Application of tree :

It is used to taking decision for finding shorted path in the networking graph .

13. Difference between tree and graph .

* TREE DATA STRUCTURE : -

It is a non linear data structure .

In tree data structure, parent child relationship is possible .

It is a collection of nodes and edges .