STACK

INTRODUCTION
- Stack is a linear data structure and very much useful in various applications of
computer science. Implementation of majority of the system programs are simplified
using this data structure.

Figure: some examples of stacks

- It is clear that a stack is something which follows the Last - In - First - Out (LIFO)
strategy.

DEFINITION
- A stack is an ordered collection of homogeneous data element where the insertion and
deletion operations take place at only one end.
- Insertion and deletion operations can take place it any position. The insertion and
deletion operation in case of stack is specially termed as push and pop respectively
and the position of the stack where these operations are performed is known as pop of
the stack.
- An element in a stack is termed an ITEM. The maximum number of elements that a
stack can accommodate is termed SIZE.
 Figure: schematic diagram of a stack

REPRESENTATION OF STACK
A stack may be represented in the memory in various ways using there are two ways.
1. One dimensional array
2. Single linked list
One Dimensional Array representation of stack
- To allocate a memory block of size to accommodate the full capacity of the stack.
Then starting from the first location of the memory block. Items of the stack can be
started in sequential following two status can be started
Empty : Pop < 1
Full : Top >= u + i- 1
Linked list representation of stack
- Array representation of stack is very easy and convenient but it allows only
representing a fixed size of stack.
- In several applications size of the stack may very during program execution. Array
representation of stack. Some machines are also known which use built in stack
hardware called machine.
- A single linked list structure is sufficient to represent any stack, here the DATA field
is for the ITEM, and the LINK field is, a usual to point to the next item.

OPERATION ON STACKS
Basic operations required to manipulate a stack are PUSH, POP, and STATUS
PUSH - To insert an item into a stack
POP - To insert an item from a stack
STATUS - To know the present state of the stack

Algorithm Push_Array
Input : the new item ITEM to be pushed into it.
Output : a stack with a newly pushed ITEM at the TOP position
Data Structure : an array A with TOP as the pointer.
If TOP >= Size then
Print" stack is full"
Else
TOP = TOP + 1
A [TOP] = ITEM
Endif
Stop

Algorithm POP_Array
Input : A stack with elements
Output : removes an ITEM from the top of the stack if it is not empty
Data Structure : An array A with TOP as the pointer
If TOP < 1 then
Print" Stack is empty"
Else
 ITEM = A [TOP]
TOP = TOP - 1
Endif
Stop

Algorithm STATUS_Array
Input : A stack with elements
Output : states whether it is empty or full, available free space and item at TOP
Data Structure : An array A with TOP as the pointer
If TOP < 1 then
Print" Stack is empty"
Else
If (TOP >= SIZE) then
Print “stack is full”
Else
Print “The element at TOP is”, A[TOP]
Free = (SIZE - TOP)/SIZE * 100
Print “Percentage of free stack is”, free
Endif
End if
Stop

APPLICATION ON STACK
Evaluation of arithmetic expression
- An arithmetic expression consists of operands and operations.
- Operands are variables or constants. Operators are various types like arithmetic unary
and binary operations.
Ex,
Unary (-)
Addition (+)
Subtraction (-)
Multiplication (*)
Division (/)
Exponentiation ( ^ )
Remainder module (%)

- A simple arithmetic expression

A + B * C/D - E ^ F * G

- There are two ways to fix it

1. Assign to each operator a precedence and associativity

Operators Precedence Associativity

- (unary), + (unary), NOT 6 -
^ (exponentiation) 6 Right to Left
* (multiplication), / (division) 5 Left to Right
+ (addition), - (subtraction) 4 Left to Right
<, <=, +, < >, >= 3 Left to Right
AND 2 Left to Right
OR, XOR 1 Left to Right

^
A + B * C / D - E F * G

1 2

3 4

2. Fixing the order of evaluation is parenthesizing the expression fully; this

allows one to override the rule for precedence and associativity.
Input: ((A + B) * ((C / D) – (E ^ (F * G))))
(A fully parenthesized expression)
- With this paranthesization, the innermost parenthesis part will be evaluated first, then
the next innermost and so on, such a sequence of evaluation is shown below
 ((A + B) * ((C / D) – (E ^ (F * G))))

1 2 3

- Another problem is the ambiguity about how the compiler can resolve to generate a
correct code for a given expression. The last problem mainly occurs for a partially
parenthesized expression. These problem can be solved in the following two steps
1. Conversion of a given expression into a special notation.
2. Evaluation / production of an object code using a stack
Notation for arithmetic expression
There are three notations to represents arithmetic expression,
1. Infix
2. Prefix
3. Postfix
- A classical application deals with evaluation of arithmetic expression here compiler uses
a stack to translate input arithmetic expression into their corresponding object code.
Infix
<Operand> <Operator> <Operand> this notation is called infix.
Ex: A+B, C-D, E*F, G/H etc.
Prefix
<Operator> <Operand> <Operand> this notation is called prefix
Ex: +AB, -CD, *EF, /GH etc.
Postfix
<Operand> <Operand> <Operator> this notation is called postfix
Ex: AB+, CD-, EF*, GH/ etc.

- The following rule is applied to convert an infix expression into a post fix form
 Assume the fully parenthesized version of the infix expression
  Move all operators so that they replace their corresponding right part of
parentheses
 Remove all parentheses.
Input: ((A + ((B ^ C) – D)) * (E – (A/C)))
(a fully parenthesized expression)
( ( A + ( ( B ^ C ) – D ) ) * ( E – ( A / C ) ) )

(Arrows point from operators to their corresponding right parenthesis)

(( A (( B C ^ D - + ( E (AC / - *
(operators are moved to their respective right parentheses)
Output: A B C ^ D - + E A C / - *
(all parentheses are removed yielding the postfix expression)
- A similar technique can be applied to obtain the prefix notation for a given infix notation
but moving the operators corresponds to the left parenthesis.
Three notations for the given arithmetic expression are listed below:
Infix : ((A + ((B ^ C) – D )) * (E – (A/C)))
Prefix : * + A - ^ BCD – E/AC
Postfix : ABC ^ D - + EAC / - *
The following points are observed for three notations
1. In both prefix and postfix equivalents of an infix expression, the variable are the same
relative positions
2. The expression in prefix or postfix form are completely parenthesis free
3. The operators are rearranged according to the rules of precedence of operators

Implementation of recursion
- Recursion is an important tool to describe a procedure having several repetitions of the
same.
- A procedure is termed as recursive of the procedure having is defined by itself. Ex:
calculation of factorial value for an integer n.
n! = n x (n-l) x (n-2) x .........x 3 x 2 x 1
(or)
n!=n x (n-l)!
Algorithm_Factorial_I
Fact = 1
For (i= 1 to N) do
Fact = i*fact
EndFor
Return (fact)
Stop

Factorial Calculation
- Factorial for an integer can be defined recursively as
Algorithm_Factorial(N)
If (N=0) then
fact == l
Else
Fact = N * Factorial (N-l)
EndIf
Return (fact)
Stop
Unit – II
QUEUE
INTRODUCTION
- A queue is a simple but very powerful data structure to solve numerous computer
applications. Like stacks, queues are also useful to solve various system programs.
Ex,
1. Queuing in front of a counter
2. Traffic control at a turning point
3. Process synchronization in multi-user environment
4. Resource sharing in a computer centre

Figure: Queue of Customers

DEFINITION
- A queue is an ordered collection of homogeneous data elements, where the insertion and
deletion operation made at two extreme ends.
- A queue is also a linear data structure like an array, a stack and linked list where the
ordering of elements is in a linear fashion.
- Queue insertion (called ENQUEUE) and deletion (called DEQUEUE) operations can
take place at two ends called the REAR and FRONT of the queue.

Figure: model of a Queue

- An element in a queue is termed ITEM; the number of elements that a queue can
accommodate is termed LENGTH.
 - Queue is termed First-In-First-Out (FIFO)

REPRESENTATION OF QUEUES
There are two ways to represent a queue in memory,
1. Using an array
2. Using a linked list
- The first representation uses a one-dimensional array and it is a better choice where a
queue of fixed size is required. (one dimensional array)
- The other representation uses a double linked list and provides a queue whose size can
vary during processing. (double linked list)

Representation of a Queue using an array

- A one-dimensional array, Q [1…..N], can be used to represent a queue.

Figure: Array representation of a Queue

- With this representation, two pointers, namely FRONT and REAR, are used to indicate
the two ends of the queue.
- For the insertion of the next element, the pointer REAR will be the consultant and for
deletion the pointer FRONT will be the consultant.
Three states of a queue with this representation are
Queue is empty
FRONT = 0
REAR = 0 (and/or)
Queue is full
REAR = N
FRONT = 1 (when full by compact)

Queue contains elements ≥ 1

 FRONT ≤ REAR
Number of elements = REAR – FRONT + 1

Algorithm Enqueue
Input : An element ITEM that has to be inserted
Output : The ITEM is at the REAR of the queue.
Data structure : Q is the array representation of a queue structure; two pointers FRONT and
REAR of the queue Q are known.
If (REAR = N) then
Print “Queue is full”
Exit
Else
If (REAR = 0) and (FRONT = 0) then
FRONT = 1
EndIf
REAR = REAR + 1
Q[REAR] = ITEM
EndIf
Stop

Algorithm Dequeue
Input : A queue with elements. FRONT and REAR are the two pointers of the queue Q.
Output : The deleted element is stored in ITEM.
Data structure : Q is the array representation of a queue structure
If (FRONT = 0) then
Print “Queue is empty”
Exit
Else
ITEM = Q[FRONT]
If (FRONT = REAR)
REAR = 0
FRONT = 0
Else
FRONT = FRONT + 1
Endive
EndIf
Stop
Ex,
from the algorithm of Enqueue and Dequeue, queue size = 10, current state of FRONT = 8,
REAR = 9
1. DEQUEUE 2. ENQUEUE 3. ENQUEUE
4. DEQUEUE 5. DEQUEUE 6. DEQUEUE
7. ENQUEUE 8. ENQUEUE 9. DEQUEUE
10. DEQUEUE

Figure: operations on a queue

Representation of a Queue using a Linked List
- In several applications, the length of the queue cannot be predicted before and it varies
abruptly.
- To overcome this problem, another preferable representation of a queue is with a linked
list.

Figure: A double linked list representation of a queue

- The pointers FRONT and REAR point the first node and the last node in the list.
Two states of the queue either empty or containing some elements, can be judged by the
following tests,
Queue is empty
FRONT = REAR = HEADER
HEADER→RLINK = NULL
Queue contains at least one element
HEADER →RLINK ≠ NULL

VARIOUS QUEUES IN STRUCTURES

There are two different queue structures,
1. Circular Queue
2. Deque
3. Priority Queue

Circular Queue
- Queue representation using an array when the REAR pointer reaches the end, insertion
will be denied even if room is available at the front.
- One way to avoid this is to use a circular array.
- A Circular array is the same as an ordinary array, say A[1…..N], but logically implies
that A[1] comes after A[N] or after A[N], A[1] appears.
 Figure: Logical and Physical views of a circular queue
- Both pointers will move in a clockwise direction. This is controlled by the MOD operation;
for example, if the current pointer is at I then shift to the next location will be I MOD
LENGTH + 1, 1 ≤ i ≤ LENGTH.
- If I = LENGTH, then the next position for the pointer is 1.
With this principle the two states of the queue regarding, i.e. empty or full, will be decided as
follows,
Circular queue is empty
FRONT = 0
REAR = 0 Next position = i MOD LENGTH + 1
Circular queue is full
FRONT = (REAR MOD LENGTH) + 1

Algorithm Enqueue_CQ
Input : An element ITEM to be inserted into the circular queue.
Output : Circular queue with the ITEM at FRONT, if the queue is not full.
Data structure : CQ be the array to represent the circular queue.
Two pointers FRONT and REAR are known.
If (FRONT = 0) then
FRONT = 1
REAR = 1
CQ[FRONT] = ITEM
 Else
next = (REAR MOD LENGTH) + 1
If (next ≠ FRONT) then
REAR = next
CQ[REAR] = ITEM
Else
Print “Queue is full”
EndIf
EndIf
Stop

Algorithm Dequeue_CQ
Input : A queue CQ with elements. Two pointers FRONT and REAR are known.
Output : The deleted element is ITEM if the queue is not empty.
Data structure : CQ be the array to represent the circular queue.
If (FRONT = 0) then
Print “Queue is empty”
Exit
Else
ITEM = CQ[FRONT]
If (FRONT = REAR) then
FRONT = 0
REAR = 0
Else
FRONT = (FRONT MOD LENGTH) + 1
EndIf
EndIf
Stop
Ex,
Circular queue of LENGTH = 4, FRONT = REAR = 0
Different states of circular queue is
1. ENQUEUE (A) 2. ENQUEUE (B)
3. ENQUEUE (C) 4. ENQUEUE (D)
5. DEQUEUE 6. ENQUEUE (E)
 7. DEQUEUE 8. ENQUEUE (F)
9. DEQUEUE 10. DEQUEUE
11. DEQUEUE 12. DEQUEUE

Figure: Tracing insertion and deletion operations on a circular queue

Deque
- Another variation of the queue is known as Deque (pronounced as ‘deck’)
- In Deque, both insertion and deletion operations can be made at either end of the
structure.
- The term Deque has originated from Double Ended QUEue.
 Figure: A Deque structure
- A Deque can be used as a stack as well as a queue.
- There are various ways of representing a Deque on the computer. One simpler way to
represent it is by using a double linked list.
The following four operations are possible on a Deque which consists of a list of items,
1. Push_DQ(ITEM) : To insert ITEM at the FRONT end of a deque.
2. POP_DQ : To remove the FRONT item from a deque.
3. Inject(ITEM) : To insert ITEM at the REAR end of a deque.
4. Eject() : To remove the REAr ITEM from a deque.

Algorithm Push_DQ
Input : ITEM to be inserted at the FRONT.
Output : Deque with a newly inserted element ITEM if it is not full already.
Data Structure : DQ being the circular array representation of a deque.
If (FRONT = 1) then
ahead = LENGTH
Else
If (FRONT = LENGTH) or (FRONT = 0) then
ahead = 1
Else
ahead = FRONT -1
EndIf
If (ahead = REAR) then
Print “Deque is full”
Exit
Else
FRONT = ahead
DQ[FRONT] = ITEM
 EndIf
EndIf
Stop

Algorithm Pop_DQ
Input : A queue CQ with elements. Two pointers FRONT and REAR are known.
Output : The deleted element is ITEM if the queue is not empty.
Data structure : CQ be the array to represent the circular queue.
If (FRONT = 0) then
Print “Queue is empty”
Exit
Else
ITEM = CQ[FRONT]
If (FRONT = REAR) then
FRONT = 0
REAR = 0
Else
FRONT = (FRONT MOD LENGTH) + 1
EndIf
EndIf
Stop

Algorithm Inject_DQ
Input : An element ITEM to be inserted into the circular queue.
Output : Circular queue with the ITEM at FRONT, if the queue is not full.
Data structure : CQ be the array to represent the circular queue.
Two pointers FRONT and REAR are known.
If (FRONT = 0) then
FRONT = 1
REAR = 1
CQ[FRONT] = ITEM
Else
next = (REAR MOD LENGTH) + 1
If (next ≠ FRONT) then
REAR = next
CQ[REAR] = ITEM
Else
Print “Queue is full”
 EndIf
EndIf
Stop

Algorithm Eject_DQ
Input : A deque with elements in it.
Output : The item is deleted from the REAR end.
Data structure : DQ being the circular array representation of deque.
If (FRONT = 0) then
Print “Deque is empty”
Exit
Else
If (FRONT = REAR) then
ITEM = DQ[REAR]
FRONT = REAR = 0
Else
If (REAR = 1) then
ITEM = DQ[REAR]
REAR = LENGTH
Else
If (REAR = LENGTH) then
ITEM =DQ[REAR]
REAR = 1
Else
ITEM = DQ[REAR]
REAR = REAR – 1
EndIf
EndIf
EndIf
EndIf
Stop

There are two known variations of Deque,

1. Input-restricted Deque
It allows insertion at one end, but allows deletion both end
 2. Output-restricted Deque
It allows deletion at one end, but allows insertion both end

Figure: Types of Deque

Priority Queue
- A priority queue is another variation of queue structure. Each element has been assigned
a value, called the priority of the element, and an element can be inserted or deleted not
only at the ends but any position on the queue.
- Insertion and Deletion at any position
- It does not follow First-In-First-Out (FIFO)

Figure: Priority Queue

Particular model of priority queue,
1. An element of higher priority is processed before any element of lower priority.
2. Two elements with the same priority are processed according to the order in which
they were added.
There are various ways of implementing the structure of a priority queue. These are:
a) Using a simple/circular array
 b) Multi-queue implementation
c) Using a double linked list
d) Using heap tree

Priority Queue using an array

- An array can be maintained to hold the item and its priority value.
- The element will be inserted at the REAR end. The deletion operation will be performed
in either of the two following ways:
a) Starting from the FRONT pointer, traverse the array for an element of the
highest priority. Delete this element from the queue.

Figure: deletion operation in an array representation of a priority queue

b) Add the element at the REAR end. Using a stable sorting algorithm, sort the
elements of the queue so that the highest priority element is at the FRONT
end.

Figure: another array implementation of a priority queue

Multi-queue implementation
- This implementation assumes N different priority queue values. For each priority p i there
are two pointers Fi and Ri corresponding to the FRONT and REAR pointers.
- The element F and R are all of equal priority value Pi.
 Figure: Multi-queue representation of a priority queue
This implementation is associated with a number of difficulties,
1. It may lead to a huge shifting in order to make room for an item to be inserted.
2. A large number of pointers are involved when the range of priority values is large.
In addition to the above, there are two other techniques to represent a multi-queue is shown
below:

Figure: Multi-queue implementation with multiple simple queues and matrix

Linked List representation of a priority queue

Figure: Linked list representation of a priority queue

 - LLINK and RLINK are two usual link fields, DATA is to store the actual content and
PRIORITY is to store the priority value of the item.
- FRONT and REAR as two pointers pointing the first and last nodes in the queue.
- All the nodes are in sorted order according to the priority values of the items in the nodes.
- The following algorithm is used to implement the insertion operation on a priority queue.
APPLICATION OF QUEUES
Numerous applications of queue structures are known in Computer Science. They are,
 Simulation
 Multi Programming Environment
 Round Robin Algorithm
Round Robin Algorithm
- The round robin (RR) algorithm is a well known scheduling algorithm and is designed for
time sharing systems.
- The RR algorithm first decides a small unit of time, called a time quantum or time slice.
- A time quantum is from 10 to 100 milliseconds.
- The CPU starts service with P1. P1 gets the CPU for time, afterwards the CPU switches to
P2, and so on.
- When the CPU reaches the end of time quantum of P n it returns to P1 and the same process
will be repeated.

Process Burst Time

P1 7
P2 18
P3 5
- The total CPU time required is 30 unit. Let us assume a time quantum of 4 unit.
The RR scheduling for this will be shown below,
P1 finished P3 finished P2 finished

P1 P2 P3 P1 P2 P3 P2
P2 P2
0 4 8 12 15 19 20 24 28 30
Figure: RR scheduling
Advantage
- RR Scheduling is the average turn around time (not necessarily always true). The turn
around time of a process is the time of its completion minus the time of its arrival
Using FCFS strategy,
Whereas, using RR algorithm

Process Arrival Time Burst Time

P1 0 9
P2 1 3
P3 9 5
P4 14 8

Figure: Deletion of a process from a circular queue

LINKED LIST
DEFINITION
 A linked list is an ordered collection of finite, homogenous data elements called nodes
where the linear order is maintained by links (or) pointers.
 It can be classified into 3 groups,
o Single linked list
o Double linked list
 o Circular linked list
LINK
Link to the next node
DATA

Fig: Node: an element in a linked list

SINGLE LINKED LIST

 In a single linked list each node contains only one link, which points to the subsequent
node in the list.
Header

59 38 64 14
N1 N2 N3 N4

72 80
N5 N6

Fig: A single linked list with six nodes

 HEADER is an empty node and only used to store a pointer to the first node N1.
 This means starting from the first node to the last node whose link field does not contain
any address but has null value.
 It can move from left to right only.
 It is also called one way list.

Representation of Linked List in Memory:

 There are 2 ways to represent a linked list in memory
o Static representation using array
o Dynamic representation using free pool of storage.
Static Representation:
 There are two arrays that are maintained: one array for data and other for links.
 Two parallel arrays are of equal size are allocated which should be sufficient to store the
entire linked list.
 The static representation of the linked list is shown below.

38 50
--
14 47
59 41
80 DATA
-- LINK
41 72 45
42
43
64 43
 44
45
46
47
48
49
50

Memory
Location

Fig: Static representation using arrays of the single linked list

Dynamic Representation:
 The efficient way of representing a linked list is using the free pool of storage.
 In this method there is a memory bank (collection of free memory space) and a
memory manager (a program).
Garbage Collector:
 There is another program called garbage collector; it plays whenever a node is no more in
use;
 It returns the unused node to the memory bank.
 Such a memory management is known as dynamic memory management.
 The Dynamic representation of linked list uses the dynamic memory management policy.
 The mechanism of dynamic memory representation is shown below:
  A list of available memory space is stored in AVAIL.
 For request of a node the AVAIL is search for the block of right size.
 If AVAIL is NULL or if the block of right size is not found, the memory manager will
return a message.
 If the block is found, it is stored in a temporary buffer NEW.
 The newly availed node can be inserted at any position in linked list.

Operations on Single Linked List:

 The operations are linked below:
o Traversing the list
o Inserting node into the list
o Deleting node from the list
o Copying the list to make duplicate of it.
o Merging the list with another one to make a larger list.
o Searching for an element in the list

Traversing a single linked list:

 In traversing we visit every node in the list starting from the first node to last node.

Algorithm Traverse-SL
Input: HEADER is the points to the header node.
Output: According to the process ().
Data structure: A single linked list whose address of the starting node is known from the
HEADER.
STEPS:
1. ptr = HEADER LINK
2. while (ptr ≠ NULL) do
3. process (ptr)
4. ptr=ptr LINK
5. End while
6. Stop.

Inserting a node into Single linked list

 There are various positions where a node can be inserted,
o Inserting at the front
o Inserting at the end
o Inserting at any other position.

Procedure GetNode
Input: NODE is the type of the data for which a memory has to be allocated.
Output: Return a message if the allocation fails else the pointer to the memory block allocated.
Steps:
1. If ( AVAIL = NULL)
2. Return(NULL)
3. Print ”In sufficient memory: unable to allocate memory”.
4. ELSE
5. ptr = AVAIL
6. While(SizeOf (ptr) ≠ Size of(NODE)) and (ptr LINK ≠NULL)DO
7. ptr1=ptr
8. ptr = ptr → LINK
9. End while
10. If(SizeOf (ptr) = SizeOf(NODE)
11. ptr1→ LINK = ptr→ LINK
12. Return(ptr)
13. Else
14. Print “ the memory block is too large to fit”
15. Return(NULL)
16. Endif
17. Endif
18. Stop

Inserting node at the front of Single linked list

 The algorithm InsertFront_SL inserts a node at a front of the single Linked list.
Algorithm InsertFront_SL:
Input: HEADER is the pointer to the header node and x is the data of the node to be
inserted.
Output: A Single linked list with a newly inserted node at the front of the list.
Data structure: Single linked list.

STEPS:
1. new = GetNode (NODE)
2. If(new = NULL) then
3. Print “ Memory underflow : No insertion”
4. Exit
5. Else
6. new → LINK = HEADER → LINK
7. new → DATA=x new
8. HEADER → LINK = new
9. Endif
10. Stop From memory bank

Fig: Inserting a node in the front of a single linked list

Inserting node at the end of Single linked list
 The algorithm InsertEnd_SL inserts a node at the end of a single Linked list.
Algorithm InsertEnd_SL:
Input: HEADER is the pointer to the header node and X is the data of the node to be
inserted.
Output: A Single linked list with a newly inserted node at the front of the list.
Data structure: Single linked list.
STEPS:
1. new = GetNode (NODE)
2. If(new = NULL) then
3. Print “ Memory underflow : No insertion”
4. Exit
5. Else
6. ptr = HEADER
7. While (ptr → LINK ≠NULL) do
8. ptr = ptr → LINK
9. EndWhile
10. ptr → LINK = new
11. new → DATA = x
12. EndIf
13. Stop
14.

Fig: Inserting a node at the end of a single linked list

Inserting node into a Single linked list at any position:

 The algorithm InsertAny_SL inserts a node at any position in a single Linked list.
Algorithm InsertAny_SL:
Input: HEADER is the pointer to the header node and X is the data of the node to be
inserted, and KEY begin the data of the KEY NODE after which the node has to be
inserted.
Output: Newly inserted node having data X after the node with data KEY.
Data structure: Single linked list.
Steps:
1. new = GetNode (NODE)
2. If(new = NULL) then
3. Print “ Memory is insufficient : No insertion”
4. Exit
5. Else
 6. ptr = HEADER
7. While (ptr → DATA ≠KEY) and (ptr → LINK ≠ NULL) do
8. ptr = ptr → LINK
9. EndWhile
10. If (ptr → LINK = NULL) then
11. Print “ Key is not available in the list”
12. Exit
13. Else
14. new → LINK = ptr → LINK
15. new → DATA = x
16. ptr → LINK = new
17. EndIf
18. EndIf
19. Stop new

Fig: Inserting a node at any position in a single linked list

Deleting a node from a Single Linked list

-There are three cases:
 Deleting from the front of the list
 Deleting from the end of the list
 Deleting from any position in the list

ReturnNode (Pointer ptr) returns a node having pointer ptr to the free pool of storage
Procedure ReturnNode
Input: PTR is the pointer of the node to be return to a list pointed by AVAIL.
Output: The Node is inserted into the list at the end.
Steps:
1. ptr1 = AVAIL
2. While (ptr → LINK ≠ NULL) do
3. ptr1 = ptr → LINK
4. EndWhile
5. ptr → LINK = ptr
6. ptr → LINK = NULL
7. Stop

Deleting the node at the front of single linked list

-The algorithm, DeleteFront_SL is used to delete the node at the front of a list.
Algorithm DeleteFront_SL
Input: HEADER is the pointer to the header node.
Output: A Single linked list after eliminating the node at the front of the list.
Data structure: Single linked list
Steps:
 1. ptr = HEADER → LINK
2. If (ptr = NULL) then
3. print “ The list is empty: No deletion”
4. Exit
5. Else
6. ptr1 = ptr → LINK
7. HEADER→ LINK = ptr1
8. ReturnNode(ptr)
9. EndIf
10. Stop

Return to Key .. .. …….

the memory
bank
Fig: Deleting the node at the front of a single linked list

Deleting the node at the end of single linked list

-The algorithm, DeleteEnd_SL is used to delete the node at the end of a list.
Algorithm DeleteEnd_SL
Input: HEADER is the pointer to the header node.
Output: A Single linked list after eliminating the node at the end of the list.
Data structure: Single linked list
Steps:
1. ptr = HEADER
2. If (ptr → LINK = NULL) then
3. print “ The list is empty: No deletion”
4. Exit
5. Else
6. While (ptr → LINK ≠ NULL) do
7. ptr1 = ptr
8. ptr1 = ptr → LINK
9. EndWhile
10. ptr → LINK = NULL
11. ReturnNode(ptr)
12. EndIf
13. Stop

Header Return to the

Memory bank
Ptr1 ptr

Fig: Deleting the node at the end of a single linked list

Copying a Single Linked list:

This algorithm is used to copy an entire linked list into another list.
 Algorithm Copy_SL
Input: HEADER is the pointer to the header node.
Output: HEADER1 is the pointer to the duplicate list.
Data Structure: Single Linked list
Steps:
1. ptr = HEADER
2. HEADER1 = GetNode(NODE)
3. ptr1 = HEADER1
4. ptr1 → DATA = NULL
5. While (ptr ≠ NULL) do
6. new = GetNode(NODE)
7. new → DATA = ptr→ DATA
8. ptr1→ LINK = new
9. new → LINK = NULL
10. ptr1 = new
11. ptr = ptr→ LINK
12. EndWhile
13. Stop

Merging two single linked list into one list

This algorithm is used to merge two single linked list into one single linked list.
Algorithm Merge_SL
Input: HEADER1 and HEADER2 are the pointer to the header nodes to be merged.
Output: HEADER is the pointer to the resultant list
Data Structure: Single linked list
Steps:
1. ptr = HEADER1
2. While (ptr → LINK ≠ NULL) do
3. ptr1 = ptr → LINK
4. EndWhile
5. ptr → LINK = HEADER → LINK
6. ReturnNode(HEADER2)
7. HEADER = HEADER1
8. Stop

Header1
L1

Header2

L2 To memory bank

Fig: Merging two single linked lists into one single linked list
Searching for an element in a single linked list
This algorithm is used to search an item in a single linked list.
Input: KEY, the item to be searched.
Output: Location, The pointer to a node where the KEY belongs to or an error message.
Data structure: Single linked list.
Steps:
1. ptr = HEADER → LINK
2. flag = 0, LOCATION = NULL
3. While (ptr ≠ NULL) and (flag = 0) do
4. If (ptr → DATA = KEY) then
5. flag = 1
6. LOCATION = ptr
7. Print “Search is successful”
8. Return (LOCATION)
9. Else
10. ptr = ptr → LINK
11. EndIf
12. EndWhile
13. If (ptr = NULL) then
14. print “ Search is unsuccessful”
15. EndIf
16. Stop

DOUBLE LINKED LIST

-A double linked list is a “two way list” because one can move in either direction, either
from left to right (or) from right to left.
-This is accomplished by maintaining two links fields
-Structure of a node is.

LLINK RLINK

DATA

Fig: Structure of a node and a double linked list

Operations on a Double linked list

-The operations possible on a Doubly linked list (DLL) are listed below:
 1. Traversing a node
2. Inserting a node
3. Deleting a node
4. Copying the list
5. Merging with another one
6. Searching for an element

Inserting a node into a Double linked list

Let us consider the algorithms of various cases of insertion.
Inserting a node in the front
The following algorithm is used to define the insertion operation in a double linked list.
Algorithm InsertFront_DL
Input: X is the data content of the node to be inserted.
Output: A double linked list enriched with a node in the front containing data X.
Data structure: Double linked list.
Steps:
1. ptr = HEADER → LINK
2. new = GetNode(NODE)
3. If (new ≠ NULL) then
4. new → LLINK = HEADER
5. HEADER→ RLINK = new
6. new→ RLINK = ptr
7. ptr → LLINK = new
8. new → DATA = X
9. Else
10. Print “ Unable to allocate memory: Insertion is not possible”
11. EndIf
12. Stop

Inserting a node in the end

The following algorithm is used to define the insertion operation in a double linked list.
Algorithm InsertEnd_DL
Input: X is the data content of the node to be inserted.
Output: A double linked list enriched with a node in the end containing data X.
Data structure: Double linked list.
Steps:
1. ptr = HEADER
2. While (ptr → RLINK ≠ NULL) do
3. ptr = ptr → RLINK
4. EndWhile
5. new = GetNode9NODE)
6. If (new ≠ NULL) then
7. new → RLINK = ptr
8. ptr → RLINK = new
9. new→ RLINK = NULL
10. new → DATA = X
11. Else
12. Print” Unable to allocate memory: Insertion is not possible”
13. EndIf
14. Stop
Deleting a node from a double linked list
Deleting a node from a double linked list may take place from any position in the list.

Deleting a node from the front of a double linked list

Algorithm DeleteFront_DL
Input: A double linked list with data
Output: A reduce double linked list
Data Structure: Double linked list
Steps:
1. ptr = HEADER → LINK
2. If (ptr = NULL) then
3. Print “:ist is empty: No deletion is made”
4. Exit
5. Else
6. ptr1 = ptr → RLINK
7. HEADER → RLINK = ptr1
8. If (ptr ≠ NULL)
9. ptr → LLINK = HEADER
10. EndIf
11. ReturnNode (ptr)
12. EndIf
13. Stop

Deleting a node from the end of a double linked list

Algorithm DeleteEnd_DL
Input: A double linked list with data
Output: A reduce double linked list
Data Structure: Double linked list
Steps:
1. ptr = HEADER
2. While (ptr → RLINK ≠ NULL)
3. ptr1 = ptr → RLINK
4. EndWhile
5. If (ptr = HEADER) then
6. Print “:List is empty: No deletion is made”
7. Exit
8. Else
9. ptr1 = ptr → LLINK
10. ptr → RLINK = NULL
11. ReturnNode (ptr)
12. EndIf
13. Stop

UNIT III
TREES
 - Where elements appear in a non linear fashion which requires two dimensional
representations is called Tree.

Figure: Tree – a non-linear representation of data

Figure: A family hierarchy in the form of a tree

Basic Terminology
Node This is the main component of any tree structure.
The concept of the node is the same as that used in a linked list.
A node of a tree stores the actual data and links to the other node
Parent The parent of a node is the immediate predecessor of a node.
Child If the immediate predecessor of a node is the parent of the node then all
immediate successors of a node are known as child
The child which is on left side is called Left Child
The child which is on right side is called Right Child
Link This is a pointer to a node in a tree
Root This is a specially designated node which has no parent
Leaf The node which is at the end and does not have any child is called leaf node.
Level Level is the rank in the hierarchy.
The root node has level 0
If a node is at level l, then its child is at level l+1 and the parent is at level l-1.
Height The maximum number of nodes that is possible in a path starting from the root
node to a
leaf node is called the height of a tree.
Degree The maximum number of children that is possible for a node is known as the
degree of a
node
Sibling The nodes which have the same parent are called siblings.

Figure: A tree and its various components

DEFINITION AND CONCEPTS

A tree is a finite set of one or more modes such that
 1. There is a specially designated node called the root.
2. Remaining nodes are partitioned into n (n > 0) disjoint sets T 1, T2, ………… Tn
where each Ti (I = 1, 2, …… n) is a tree, T1, T2, ………… Tn are called subtree of the
root.

Figure: A sample tree T

Binary Trees
- A binary tree is a special form of a tree. To a general tree a binary tree is more important
and frequently used in various application of computer science.
Binary tree can also be defined as
1. T is empty (called the empty binary tree) or
2. T contains a specially designated node called the root of T, and the remaining nodes
of T form two disjoint binary trees T1 and T2 which are called left sub-tree and the
right sub-tree
 Figure: A sample binary tree with 11 nodes
Full binary tree
- A binary tree is a full binary tree if it contains maximum possible number of nodes in all
level.
Complete binary tree
- A binary tree is said to be a complete binary tree if all its levels expect possibly the last
level, have the maximum number of possible nodes, and all the nodes in the last level
appear as far left as possible.

Properties of binary tree

 - Binary tree possesses a number of properties are very much useful
Lemma: In any binary tree maximum number of nodes on level l is 2l, Where l >= 0
Proof: The proof of lemma can be done by induction on l. the root is the only node on
level l=0
hence the maximum number of nodes on level l=0 is 20 = 1 = 2l.
Suppose for all i, 0 ≤ i < l and for some l, the above formula is true, that is the
maximum number of nodes at level i is 2i. Since each node in a binary tree has
degree2, so from each node at level i, there may be at most 2 nodes at level i+1.
Thus, the maximum number of nodes at level i+1 is 2 x 2 i = 2i+1. Therefore, if the
formula is true for any i, then it is also true for i+1.
Hence the proof.

Figure: Binary tree showing above Lemma

REPRESENTATION OF BINARY TREE

- A tree must represent a hierarchical between a parent node and child node.
There are two common methods used for representing the structure,
1. Linear or Sequential representation
2. Linked representation
Linear representation of a Binary tree
- This type of representation is static. In this representation, the nodes are stored level by
level, starting from the zero level.
- The root node is stored in the first memory location.
Rules
1. The root node is at location l
2. for any node with index i, 1 < i ≤ n
a) PARENT (i) = [i/2]
for the node when i=1, there is no parent
b) LCHILD (i) = 2*i
if 2*i > n, then i has no left child
c) RCHILD (i) = 2*i+1
if 2*i+1 > n, then I has no right child.
Let us consider the following expression in the form of a tree is (A - B) + C * (D/E)

Figure: Sequential representation of a binary tree

Figure: A skew binary tree with maximum height

Advantages of linked list
 any node can be accessed from any other node by calculating the index
 Data are stored only without any pointers.
 Programming languages where dynamic memory allocation is not possible.
Disadvantages of linked list
 Other than full binary trees
 It allows only static representation
 Inserting or deleting a node is inefficient with this representation.

Linked representation of binary tree

- Linear representation of binary trees as a number of overheads.

Figure: Structure of a node in linked representation

- LC and RC are two link fields to store the address of left child and right child of a node
- Data is the information content of the node.
- The two forms that are tree structure and linked structure

Figure: Linked representation of a binary tree

OPERATION ON BINARY TREE
The operations on a binary tree can be listed as follows,
1. Insertion: To include a node into an existing binary tree
2. Deletion: To delete a node from a non-empty binary tree
3. Traversal: To visit all the nodes in a binary tree
4. Merge: To merge two binary trees into a larger one

Insertion
- A new node can be inserted into any position in a binary tree
The insertion procedure is a two step process.
1. To search for the existence of the node in the given binary tree. After which an insertion
is made.
2. To establish a link for the new node.

Figure: insertion of a node as an external node into a binary tree

Algorithm InsertBinaryTree_SEQ
Input : KEY be the data of a node after which a new node has to be inserted with data
ITEM.
Output : Newly inserted node with data ITEM has a left or right child of the node KEY.
Data Structure: Array A storing the binary tree.
l = search_SEQ(1,KEY)
if (l = 0) then
Print “search is unsuccessful: No insertion”
Exit
 endif
If (A[2*l] = NULL or (A[2*l+1] = NULL), then
If (option =L) then
If A[2*l] = NULL then
A[2*l] = ITEM
Else
Print “Desired insertion is not possible”
Exit
EndIf
EndIf
If (option =R) then
If (A[2*l+1] = NULL) then
A[2*l+1] = ITEM
Else
Print “Desired operation is not possible”
Exit
EndIf
EndIf
Else
Print “ITEM cannot be inserted”
EndIf
Stop

Deletion
- This operation is delete any node from non empty binary tree

Figure: Deletion of an external node in a binary tree

Algorithm DeleteBinaryTree_SEQ
Input : ITEM as data of the node to be deleted
Output : A binary tree without a node having data ITEM
Data structure : Arrays A storing the binary tree. SIZE denotes the size of A.
flag = FALSE
l = search_SEQ(1,KEY)
If l = 0 Goto step 10
If (A[2*l]=NULL) and (A[2*l+1] = NULL)
flag=True
a[l]=NULL
Else
Print “ITEM is a not a key node”
EndIf
If (flag=FALSE)
Print “node does not exist”
EndIf
stop

Figure: A binary tree representation with three arrays

Traversal
- This operation is used to visit each node in the tree exactly once.
A tree can be traversed in various ways. There are six possible ways
1. R Tl Tr
2. Tl R Tr
 3. Tl Tr R
4. Tr Tl R
5. Tr R Tl
6 R Tr Tl
Out of possible Traversals only three are fundamentals, they are given below
1. R Tl Tr (preorder)
2. Tl R Tr (Inorder)
3. Tl Tr R (Post order)

Preorder traversal
This traversal can be defined as follows
 Visit the root node R
  Traverse the left sub-tree of R
 Traverse the right sub-tree of R
Algorithm Preorder Traversal
Input : Root is the pointer to the root node
Output : Visiting the entire node’s in preorder fashion
Data structure : linked structure
ptr = ROOT
if (ptr ≠ NULL) then
visit (ptr)
preorder (ptr  LC)
preorder (ptr  RC)
EndIf
stop

Inorder Traversal
This traversal can be defined as follows,
 Traverse the left sub-tree of R
 Visit the root node R
 Traverse the right sub-tree of R
Algorithm Inorder Traversal
Input : Root is the pointer to the root node
Output : Visiting all the nodes in the in order fashion
Data structure : linked structure
ptr = ROOT
If (ptr ≠ Null) then
Inorder (ptr  LC)
visit (ptr)
Inorder(ptr  RC)
EndIf
Stop.

Postorder traversal
This traversal can be defined as follows,
 Traverse the left sub-tree of R
  Traverse the right sub-tree of R
 Visit the root node R
Algorithm Postorder Traversal
Input : Root is the pointer to the root node
Output : Visiting all the nodes in the post order fashion
Data structure : linked structure
ptr = ROOT
If (ptr ≠ NULL) then
postorder (ptr  LC)
postorder (ptr  RC)
visit(ptr)
EndIf
Stop

Formation of binary tree from its traversals

The basic principle for such a formation is stated as follows,
 If the preorder traversal is given, then the first node is the root node. If the Postorder
traversal is given, then the last node is the root node.
 Once the root node is identified, all the nodes in the left sub-trees and the right sub-
trees of the root node can be identified.
 The same technique can be applied repeatedly to form sub-trees.
Ex,
Suppose the Inorder and Preorder traversals of a binary tree are as follows.
Inorder D B H E A I F J C G
Preorder A B D E H C F I J G

We have to construct the binary tree. The following steps need to be followed
1. From the preorder traversal, it is evident that A is the root node.
2. In Inorder traversal, all the nodes which are on the left side of A belong to the left sub-
tree and those which are on the right side of A belong to the right sub-tree.
3. Now the problem reduces to form sub-trees and the same procedure can be applied
repeatedly.
 Figure: Formation of a binary tree from its inorder and preorder traversal

Merging together two binary trees

There are two ways to merge,
1. T1, T2 are two binary trees.
T2 can be merged with T1 if all the nodes from T2 are inserted into the binary tree T1.
2. When the entire tree T@ are T1 can be included as a sub-tree of T1 or T2
T(n1+n2) =T1(n1) + T2(n2)

Figure: Merging together two binary trees

Algorithm MergeTrees
Input : Two points Root1 and Root2 are the roots of two binary trees T1 and T2
Output : A binary tree containing all the nodes of T1 and T2 having the pointer ROOT
Data structure : Linked structure
If (ROOT1 = Null) then
ROOT = ROOT2
Exit
Else
If (Root2=Null) then
ROOT = ROOT1
Exit
Else
If (ROOT1->LCHILD + NULL) then
ROOT1->LCHILD=ROOT2
ROOT=ROOT1
Else
if (ROOT1->RCHILD=NULL) then
ROOT1 ->RChILD =ROOT2
ROOT=ROOT1
Else
if(ROOT2->LCHILD=NULL) Then
ROOT2->LCHILD=ROOT!
ROOT=ROOT2
Else
if (ROOT2-> RCHILD=NULL) then
ROOT2->RCHILD=ROOT!
ROOT=ROOT2
else
print “ Trees are not compatible for merge operations”
Exit
Endif
Endif
Endif
Endif
Endif
Endif
Stop.
TYPES OF BINARY TREE
There are several types of binary trees
 Expression trees.
 Binary search tree.
 Heap tree.
 Threaded binary tree
 Huffman tree.
 Height balanced tree. (AVL tree)
 Red black tree
 Splay tree
 Decision tree.

Expression tree
- An expression tree is a binary tree which stores an arithmetic expression.
- The leaves of an expression tree are operands and all internal nodes are operators.
- An expression tree is always a binary tree because an arithmetic expression contains
either binary or unary operators.

Figure: an expression tree

Binary Search Tree
- A Binary tree T is termed binary search tree if each node N of T satisfies the following
property.
- The value at N is operates than every value in the left sub tree of N and is less than every
value in the right sub tree of N.
Operations,
 Searching data
 Inserting data
 Deleting data
 Traversing the tree

Figure: Binary search tree

Heap Tree
- Suppose H is the compute Binary tree. It will be termed Heap tree it is satisfied the
following properties.
1. For each node N in H, the value at N is greater than or equal to the value of each
of the children of N.
2. In other words, N has a value which is greater than or equal to the value of every
successor of N.
There are two heaps
1. Max Heap (all nodes < N)
2. Min Heap (all nodes > N)

Figure: Heap Tree

UNIT IV
GRAPHS
INTRODUCTION
- Graph is important non-linear data structure.
- In tree structure there is a hierarchical relationship between parent and children that is
one parent and many children. On the other hand is relationship is less restricted. Here
relationship is from many parents to many children.
It represents two non-linear data structure,

Figure: Two non-linear data structures: tree and graph

Ex,
Airlines
Cities are connected through airlines. This can be represented through graph structure. Here,
airports are represented by solid dots and airlines by edges.

Source-destination network
A network connection of three commodities: electricity, gas and water among three distant
destinations D1, D2 and D3.

Flowchart of a Program
The flowchart of a program is in fact the graphical representation of an algorithm of a problem.
GRAPHS TERMINOLOGIES
- There are no standard terminologies in graph theory.
 Graph
 Digraph
 Weighted graph
 Adjacent vertices
 self loop
 Parallel edges
 Simple graph
 Complete graph
 Acyclic graph
 Isolated vertex
 Degree of vertex
 Pendant vertex
 Connected graph

Graph
- A Graph G consists of two sets:
i) A set V, called set of all vertices (or nodes)
 ii) A set E, called set of all edges (or arcs). This set E is the set of pair of elements from
V.
For example, let us consider the graph G1
V = {v1,v2,v3,v4}
E = {(v1,v2), (v1,v3), (v1,v4), (v2,v3), (v3,v4)}

Digraph
- A digraph is also called directed graph.
- It is a graph G, such that G = <V, E>, where V is the set of all vertices and E is the set of
ordered pairs of elements from V
Ex,
V = {v1,v2,v3,v4}
E = {(v1,v2), (v1,v3), (v2, v3), (v2,v3), (v3,v4), (v4, v1)}

Weighted Graph
- A Graph is termed as weighted Graph if all the edges in it are labeled with some edges.
 Figure: Various Graph

Adjacent Vertices
- A vertex vi is adjacent to another vertex say vj, if there is an edge from vi to vj.

Self Loop
- If there is an edge whose starting and end vertex are same that is (V i,Vj) is an edge then it is
called a self loop.

Parallel Edges
- If there is more than one edge between the same pair of vertices, then there are known as
parallel edges.
- A graph which has either self loop or parallel edges or both is called multigraph

Simple Graph
- A graph if it does not have any self loop or parallel edges is called a simple graph
(digraph)

Complete Graph
- A complete Graph is set to be complete if each vertex V i is adjacent to every other vertex
Vj in G. In other words there are edges from any other vertex to the vertex.
Acyclic Graph
- If there is a path containing one or more edges which starts from a vertex Vi and
terminates into the same vertex then the path is known as a cycle.
- If a graph (digraph) does not have any cycle then it is called acyclic graph.

Isolated Vertex
- A vertex is isolated if there is no edge connected from any other vertex to the vertex

Degree of Vertex
- The number of edges connected with vertex Vi is called the degree of vertex Vi and is
denoted by degree (vi).
- There are two degrees, indegree and outdegree
- Indegree = number of edges incident into Vi
- Outdegree = number of edges emanating from Vi

Pendant Vertex
- A vertex Vi is pendant if its indegree (vi) = 1 and outdegree (vi) = 0.

Connected Graph
- In a graph (not digraph) G, two vertices Vi and Vj are said to be connected if there is a
path in G from Vi to Vj.
- A graph is said to be connected if for every pair of distinct vertices Vi, Vj in G, there is a
path.

REPRESENTATION OF GRAPHS
1. Set representation
2. Linked representation
3. Sequential (matrix) representation
 Figure: Types of graph
Set Representation
- This is one of the straightforward methods of representing a graph. With this method, two
sets are maintained:
i) V, the set of vertices
ii) E, the set of edges
- Which is the subset of VXV. But if the graph is weighted, the set E is the ordered
collection of 3 tuples, that is, E= W X V X V, where W is the set of weights.
Graph G1
V(G1) = {v1,v2,v3,v4,v5,v6,v7}
E(G1) = {(v1,v2), (v1,v3), (v2,v4), (v2,v5), (v3,v6), (v3,v7) }
Graph G2
V(G2) = {v1, v2, v3, v4, v5, v6, v7}
E(G2) = {(v1,v2), (v1,v3), (v2,v4), (v2,v5), (v3,v4), (v3,v6), (v4,v7), (v5,v7), (v6,v7)}
Graph G3
V(G3) = {A, B, C, D, E}
E(G3) = {(A,B), (A,C), (C,B), (C,A), (D,A), (D,B), (D,C), (D,E), (E,B)}
Graph G4
V(G4) = {A, B, C, D}
E(G4) = { (3,A,C), (5, B, A), (1, B, C), (7, B, D), (2, C, A), (4, C, D), (6, D, B), (8,
D, C)}

Linked Representation
 - Linked representation is another space – saving way of graph representation.

Figure: Linked representation of graph

Matrix Representation
- Matrix representation is the most useful way of representing any graph. This
representation uses a square matrix of order n x n, n being the number of vertices in the
graph.
Entries in the matrix can be decided as follows,
aij = 1, if there is an edge from vi to vj
= 0, otherwise
 - This matrix is known as adjacency matrix because an entry stores the information whether
two vertices are adjacent or not.
- Also, the matrix is alternatively termed as bit matrix or Boolean matrix as the entries are
either 0 or 1.

Figure: Adjacency matrix representation of graph

- Adjacency the matrix is also useful to multigraph incase of multigraph representation
instead of entry one, the entry will be termed as vertex.

OPERATIONS ON GRAPHS
The important operations possible on graph,
Insertion
a. To insert a vertex and hence establishing connectivity with other vertices in the
existing graph.
b. To insert an edge between two existing vertices in the graph.
Deletion
a. To delete a vertex from the graph.
b. To delete an edge from the graph.
Merging
To merge two graphs G1 and G2 into a single graph.
Traversal
To visit all the vertices in the graph.

Operations on Linked List Representation of Graphs

Insertion

Figure: Insertion of a vertex into an undirected graph

Graph Traversal
- Traversing a graph means visiting all the vertices in the graph exactly once
- Several methods are known to traverse a graph systematically
 Breadth First Search (BFS)
This traversal is very similar to the level-by-level traversal of a tree
BFS (G1) = v1 – v2 – v8 – v3 – v4 – v5 – v6 – v7
BFS (G2) = v1 – v2 – v3 – v4 – v5 – v6 – v7 – v8
 Depth First Search (DFS)
Starting from a given node, this traversal visits all the nodes up to the deepest level
and so on.
DFS (G1) = v1 – v2 – v5 – v7 – v4 – v8 – v6 – v3
DFS (G2) = v1 – v2 – v5 – v7 – v4 – v8 – v3 – v6
 Figure: BFS traversal on two graphs G1 (undirected) and G2 (directed)

Operations on Matrix Representation of Graphs

Figure: Insertion of a vertex into an undirected and a directed graph

APPLICATIONS OF GRAPH STRUCTURES

Shortest Path Problem
Input : A graph G whose pointer to its adjacency matrix is Gptr and vertices are labeled
as
1, 2,…., N; N being the number of vertices in the graph.
Output : The path matrix P.
Data structure : Matrix representation of graph with pointer as Gptr.
Algorithm Warshall
For i=1 to N do
For j= 1 to N do
P[i][j] = Gptr[i][j]
EndFor
For k = 1 to N do
For I = 1 to N do
For j = 1 to N do
P[i][j] = P[i][j] (P[i][k] ^ P[k][j])
EndFor
EndFor
EndFor
Return (P)
Stop

Figure: Illustration of Warshall’s algorithm

Minimum Spanning Tree

 Figure: Two spanning tree

UNIT V
SORTING
- Sorting is the process of arranging data items in a particular order (ascending or
descending).
There are two basic categories,
 Internal Sorting - all data item to be sorted are
accommodated in main memory at One time
 External Sorting - these are applied for larger collection
of data which reside on Secondary devices
Three main considerations,
 Programming time
 Execution time of the program
 Memory or auxiliary space needed for the program environment

HEAP SORT
- Heap sort is an improvement over the binary tree sort. It does not create nodes as in
the case of binary tree sort. Instead it builds a heap by adjusting the position of the
elements within the array itself.
The two phases involved in sorting the elements using heap sort,
  Construct a heap by adjusting the array elements
 Replace the root with last node of heap tree
 Keep the last node at proper position
- The root element of a max-heap is always the largest element. The sorting ends when
the root element of each successive heap has been moved to the end of the array.

Figure: Array and its equivalent representation as heap tree

Step – 1

Figure: heap after eliminating root element 70

Here right child of 46 is 52, which is greater than 46, hence replace it with 52

Now the elements of heap tree in array are as follows

Now 27 is the last node. So replace it with root 63 and do the same operations
Step – 2
Step – 3

Step – 4
Step – 5

Step – 6

Step – 7
Step – 8

QUICK SORT
- List is partitioned into lower and upper sub-lists for which all keys are, respectively,
less than some pivot key or greater that the pivot key. The sort then recursively
invokes itself with both lists. Each time when the sort is invoked, it further divides the
elements into smaller sub-lists.
- It first chooses some key from the list for which about half the items will come before
and half after. This selected key is called pivot.

Ex: the following unsorted array is to be sort in quick sort method.

20 55 46 37 9 89 82 32
Pivot is 20,
(9) 20 (55 46 37 89 82 32)
Then, 9 20 (46 37 32) 55 (89 82) pivot is 55
 9 20 (37 32) 46 55 (89 82) pivot is 46
9 20 (32) 37 46 55 (89 82) pivot is 37
9 20 32 37 46 55 (82) 89 pivot is 89
Finally, 9 20 32 37 46 55 82 89

MERGE SORT
- Merge sort is simple to understand but requires as much memory as the original array.
- A file is divided into 2 files, A1 and A2. These 2 files are compared, 1 pair of records
at a time, and merged. This is done by writing them on 2 separate new file B1 and B2.
The elements that do not pair off are simply rewritten into the new file. The records in
B1 and B2 are now blocked with 2 records in each segment.
Ex:
(2 6 3 1 4 31 23 8 11 19 21 37 14 57 28 45 30 9 35 12 13 18 5 89 77)
A1 : 2 6 3 1 4 31 23 8 11 19 21 37
A2 : 14 57 28 45 30 9 35 12 13 18 5 89 77
After 1st pass of segments, length 1
B1 : ((2 14) (3 28) (4 30) (23 35) (11 13) (5 21))
B2 : ((6 57) (1 45) (9 31) (8 12) (18 19) (37 89) (77))
After 2nd pass of segments, length 2
A1 : ((2 6 14 57) (4 9 30 31) (11 13 18 19)
A2 : ((1 3 28 45) (8 12 23 35) (5 21 37 89) (77))
After 3rd pass of segments, length 4
B1 : (( 1 2 3 6 14 28 45 57) (5 11 13 18 19 21 37 89))
B2 : ((4 8 9 12 23 30 31 35) (77))
After 4th pass of segments, length 8
A1 : ((1 2 3 4 6 8 9 12 14 23 28 30 31 35 45 57)
A2 : (5 11 13 18 19 21 37 77 89)
After 5th pass of segments, length 16
B1 : (1 2 3 4 5 6 8 9 11 12 13 14 18 19 21 23 28 30 31 35 37 45 57 77 89)
B2 : empty
SEARCHING
What is searching?
- Locate a particular data item in a database in known as searching. The search is said
to be successful if the desired data item is located otherwise the search is considered
to be unsuccessful.
- Computer systems are used to store large amounts of data from which individual
records may be retrieved according to some search criterion. Thus the efficient
storage of data to facilitate fast searching is very important.
Searching is computer system is of two types
 Internal search - data items are stored entirely within the computer’s main
memory
 External search - tables, records are stored in files kept on disk or tape which
are
External to computer’s main memory

SEQUENTIAL AND BINARY SEARCH

There are two simple techniques
 Linear or Sequential Search
 Binary Search

Linear or Sequential Search

- Sequential search is to find the specific data item in a linear, which is one after others.
It needs traversing each and every element of data items and checking if it is the one
required.
- The sequential search technique is the simplest method but suitable for sorted or
unsorted list of data items.
- In sequential search, each element of an array is compared one by one with the
required ITEM to be searched, until either the desired element is found or the end of
the list is reached.
- A method in which we traverse every item of the array sequentially to locate the
given ITEM is called sequential or linear search.
 Figure: Illustration of linear search

Algorithm Sequential Search

Sequential Search (DATA, N, ITEM, LOC)
Here DATA is a linear array with N elements, and ITEM is a given item of information to be
searched. The algorithm finds the location LOC of ITEM in DATA or sets LOC: = 0 if the
search is unsuccessful
Step 1 Insert ITEM at the end of DATA (Initialize Counter)
Set DATA [N + 1]: = ITEM
Step 2 [Initialize Counter] set LOC: = 1
Step 3 [Search for ITEM]
Repeat while DATA [LOC] ≠ ITEM
Set LOC: = LOC + 1
[End of Loop]
 [End of Loop in Step 2]
Step 4 [Successful?] if LOC = N + 1, then set LOC: = 0
Step 5 Exit.
- The efficiency of the sequential search is very poor. Sequential search is a simple and
easy method, but it is efficient only for small sized array list and highly inefficient for
large sized array list. If the array list is big, then the number of comparison is very
large. In the worst case, we will have to make N comparisons, to search for the record
in the end of the list. Where N is the maximum number of elements in the array.

Binary Search
- The binary search method requires the elements of the array in the sorted order
descending order or ascending order.
- At each stage, the number of elements in the remaining set is decreased by about one
half. Therefore the binary search is faster than the sequential search.
- When to locate an item an ordered or sorted list (array) then, doing some efficiency
by using a binary search. This is a technique in which each comparison either locates
the item or divides the remaining list (array) in to half. Because the array (list) is in
the order (ascending or descending order), it will only be necessary to repeat this
process again on one of the two segments. This is reducing the remaining search
operations very rapidly.
- Binary search, is compare the value of the desired item with the element in the middle
position of the array. If it is match, it found immediately. If the value is less than the
middle element value, this item sough must lie in the lower half of the array. If it is
greater then the item sough, this must lie in the upper half of the array. So it repeat the
procedure on the lower (or upper) half of the array depending upon the value of the
middle element of the array.
Example,
1 5 11 17 23 29 35 52 71 93 are in array
We are to require locate 29 in the array
The following steps for binary search
Step 1 Split the ten element list into half (10/2 = 5), check the fifth element that is
23. Since 29 > 23 it will proceed with the lower half of the array.
Step 2 Split the five elements in the second half of the list into half, the result is
52 but 29 < 52. Thus search is upper half in the list.
Step 3 Split the distance between the fifth and the eighth into half (8-5) / 2 + 5 =
6.5. So check the seventh element. The result is 35 and 29 < 35. So continue with
upper half in the list.
Step 4 Split the distance between the fifth and the seventh element into half
((7-5) / 2 + 5. So check the sixth element which is 29. That is the match.

Algorithm Binary Search (DATA, LB, UB, ITEM, LOC)

Here Data( ) is a sorted array with lower bound LB, and upper bound UB and ITEM is a given
item of information to be searched. The variable BEG, END and MID denote respectively the
beginning, ending and middle location of segment of the elements of array DATA( ). This
algorithm finds the LOC of ITEM in DATA( ) or sets LOC = NULL) if search is unsuccessful.
Step 1 (Initialize the segment variables)
Set BEG = LB, END = UB and MID = INT ((BEG + END) / 2)
Step 2 Repeat steps 3 and 4 while BEG < END
and DATA(MID) ≠ ITEM
Step 3 IF ITEM < DATA(MID) then
SET END = MID – 1
ELSE
SET BEG = MID + 1
END IF
Step 4 set MID = INT [(BEG + END) / 2]
(end of step 2 loop)
Step 5 IF DATA(MID) = ITEM then
Set LOC = MID and Print search successful
 ELSE
Set LOC = NULL and Print Search unsuccessful
END IF
Step 6 EXIT.