ALGORITHM OF

LINKED LIST

72
 1. Single_Linked_List_Traverse[Info,link,Ptr]

START 210

85 310 55 350 11 x
210 310 350

1. Ptr = Start

2. Repeat Steps 3 to 4 while Ptr != NULL

3. Process/Print info[Ptr]

4. Ptr = Link[Ptr]

[end while]

5. Exit.

73
 2. Single_Linked_List_ Search[Info, Ptr,Link,Item,Loc]

START 210

85 310 55 350 11 x
210 310 350

1. Ptr = Start, Loc = NULL

2. Repeat step 3 while Ptr != NULL

3. If Info[Ptr] == Item, then

print: Item found , Loc = Ptr

goto step 4

else

Ptr = Link[Ptr]

[end if else]

[end while]

4. If Loc == NULL, then

print: Item not found

[end if]

5. Exit.

74
 3. Single_Linked_List_Insert_Beg[Avail,item,new]

START 210

85 310 55 350 11 x
210 310 350

FREE POOL
77 100
450
item = 77 x 505 x
450 505

x 505
Dynamic Memory Allocation
x 505
#Here, Avail is the free pool of memory for dynamic memory allocation
x 505 505
1. If Avail == NULL, then
x
print: Overflow
x 505
goto step 6

[end if]

2. new == Avail, Avail = Link[Avail]

3. Info[new] = item

4. Link[new] = start

5. start = new

6. Exit.

75
 4. Single_Linked_List_Insert_End[Avail,item,new]

START 210 450

85 310 55 350 11 x 77 x
210 310 350 450

FREE POOL
item = 77

x 505 x
450 505
x DYNAMIC MEMORY
505 ALLOCATION
x 505
x 505 505
x
x 505
1. If Availl == NULL, then

print: Overflow

goto step 8

[end if]

2. new == Avail, Avail = Link[Avail]

3. Info[new] = item

4. Link[new] = NULL

5. Ptr = start

6. Repeat step 7 while Ptr != NULL

7. If Link[Ptr] == NULL, then

Link[Ptr] = new

76
 goto step 8

else

Ptr = Link[Ptr]

[end if else]

[end step 6 loop]

8. Exit.

77
 5. Single_Linked_List_Insert_Loc[avail,item,new,loc]

START 100

27 310 52 410 32 x
100 310 410

item = 77
77 410
loc = 310
new 450

FREE POOL

x 505 X

450 505

x 505
DYNAMIC MEMORY ALLOCATION
x 505
1. If avail == NULL, then
x 505 505
print: Overflow x
goto step 6 x 505
[end if]

2. new = avail, avail = Link[avail]

3. Info[new] = item

4. Link[new] = Link[loc]

5. Link[loc] = new

6. Exit.

78
 6. Single_Linked_List_Del_Beg[start,item,NULL]

START 100

27 310 52 410 32 x
100 310 410

FREE POOL

START 100
x 505
27 x 450 610

50
100 DYNAMIC MEMORY ALLOCATION

1. If start == NULL, then

Print: Underflow

goto step- 5

[end if]

2. item = Info[start]

3. If (link[start] == NULL), then

Ptr = start, start = NULL

Else

Ptr = start, start = Link[start]

[end if else]

4. Link[Ptr] = Avail, Avail = Ptr (Memory Releasing)

5. Exit.

79
 7. Single_Linked_List_Del_End[item,NULL,ptr]

START 100

27 310 52 410 32 x
100 310 410

FREE POOL

START 100
x 505
27 x 450 610

100 DYNAMIC MEMORY ALLOCATION

1. If start == NULL, then

Print: Underflow

goto step 7

[end if]

2. If (Link(start) == NULL) , then

item = Info[start]

ptr = start

start = NULL

goto step 6

3. pptr = start, ptr = Link[start]

4. Repeat step 5 while ptr != NULL

5. If Link[ptr] == NULL, then

Item = Info[ptr], Link[pptr] = NULL

goto step 6

80
Else

pptr = ptr

ptr = Link[ptr]

[end if else]

[end step 4 loop]

6. Link[ptr] = Avail

Avail = ptr

7. Exit.

81
 8. Single_Linked_List_Del_Loc[item,NULL,loc]

Loc = 310
START 100
410

27 310 52 410 32 x
100 310 410

FREE POOL

START 100
x 505
27 x 450 610

100 DYNAMIC MEMORY ALLOCATION

1. If start == NULL, then

Print: Underflow

Goto step 9

[end if]

2. If Link[start] == NULL and loc == start ,then

Item = Info[loc]

Ptr = start

Start = NULL

Goto step 8

[end if]

3. item = Info[loc]

4. ptr = start

82
5. Repeat step 6 while ptr != loc

6. If Link[ptr] == loc, then

Link[ptr] = Link[loc]

Goto step 7

Else

Ptr = Link[ptr]

[end if else]

[end step 5 loop]

7. ptr = loc

8. Link[ptr] = Avail, Avail = ptr

9. Exit.

83
 9. Single_Linked_List_Del_Item[item,NULL,loc]

START 100

23 210 45 305 21 x
100 210 305

FREE POOL
item = 45

x 505 x
450 505
x DYNAMIC MEMORY
505 ALLOCATION
1. If start == NULL, then
x 505
x 505 505
Print: Underflow
x
Goto step 11
x 505
[end if]

2. ptr = start, loc = NULL

3. Repeat step 4 while ptr != NULL

4. If Info[ptr] == item, then

Loc = ptr

Goto step 5

Else

Ptr = Link[ptr]

[end if else]

[end while]

5. If loc == NULL, then

84
 Print: Item not found!!

Goto step 11

[end if]

6. ptr = start

7. Repeat step 8 while ptr != loc

8. If Link[ptr] == loc, then

Link[ptr] = Link[loc]

Goto step 9

Else

Ptr = Link[ptr]

[end if else]

[end step 7 loop]

9. ptr = loc

10. Link[ptr] = Avail, Avail = ptr

11. Exit.

85
 10. Circular_list_traversing[list,info,start]

START 100

25 210 56 300 11 100

100 210 300

1. If start != NULL, then

Process Info[start]

[end if]

2. Ptr = Link[start]

3. Repeat steps 4 to 5 while ptr != start

4. Process Info[ptr]

5. Ptr = Link[Ptr]

[end step 3 loop]

6. Exit.

86
 11. Circular_list_searching[item,info,loc]

Item = 11

START 100

25 210 56 300 11 100

100 210 300

1. If info[start] == item, then

Print: Item is present at the location.

Goto step 6

[end if]

2. Ptr = Link[start], loc = null

3. Repeat step 4 while ptr != start

4. If info[ptr] == item, then

Print: item is present at ptr location.

Loc = ptr

Goto step 5

Else

Ptr = link[ptr]

[end if else]

[end step 3 loop]

5. If loc == NULL, then

Print: Iten not present.

[end if]

6. Stop.

87
 12. Circular_list_insert_beg[item,start]
450

START 100

25 210 56 300 11 100

100 210 300

FREE POOL
13 100
450
item = 13 600
450 600

1. If Avail == NULL, then

x 505
x 505
Print: Overflow!
x 505 505
Goto step: 9
x
[end if] x 505
2. New = avail, avail = link[avail]

3. Info[new] = item

4. Link[new] = start

5. Ptr = Link[start]

6. Repeat step 7 while ptr != start

7. If link[ptr] == start, then

Goto step 8

Else

Ptr = Link[ptr]

[end if else]

[end step 6 loop]

8. Link[ptr] = new, start = new

88
9. Exit
 13. Circular_list_insert_end[Avail,item,end]

START 100

25 210 56 320 11 100

100 210 320

45 100
new 450
item = 45

610
450 610

1. If avail == NULL, then

Print: Overflow!

Goto step 8

[end if]

2. new = Avail, Avail = link[avail]

3. Info[new] = item

4. Link[new] = stsart

5. Ptr = Link[start]

6. Repeat step 7 while ptr != start

7. If link[ptr] == start, then

89
 Link[ptr] = new

Goto step 8

Else

Ptr = link[ptr]

[end if else]

[end while loop]

8. Exit

90
 14. Circular_list_deletion_beg[start,item]

START 100

27 310 52 410 32 100

100 310 410

FREE POOL

START 100
610
27 100 610

100

1. If start == NULL, then

Print: Underflow!

Goto step 7

[end if]

2. If start == Link[start], then

Item = info[start]

Ptr = start

Goto step 6

[end if]

3. ptr = link[start]

4. Repeat step 5 while ptr != start

5. If link[ptr] == start, then

Item = info[start]

Link[ptr] = link[start]

91
 Ptr = start

Start = link[start]

Goto step 6

Else

Ptr = link[ptr]

[end if else]

[end while loop]

6. link[ptr] = avail, avail = ptr

7. Exit

92
 15. Circular_list_deletion_end[start,ptr,pptr,item]

START 100

27 310 52 410 32 100

100 310 410

FREE POOL

START 100
610
27 100 610

100

1. If start == NULL, then

Print: underflow!

Goto step 7

[end if]

2. If start == link[start], then

Item = Info[start]

Ptr = start

Start = NULL

Goto step 6

[end if]

3. ptr = link[start], pptr = start

4. Repeat step 5 while ptr != start

5. If link[ptr] == start, then

Item = info[ptr]

93
 Link[pptr] = Link[ptr]

Goto step 6

Else

Pptr = ptr

Ptr = Link[ptr]

[end if else]

[end while loop]

6. Link[ptr] = Avail, Avail = ptr

7. Exit

94
 16. Double_list_delete_beg [FORW, item]

FORW 100 320 BACK

x 29 210 100 45 320 210 12 x

100 210 320

FORW 100 320 BACK

x 29 x

x 610 450
450 610

1. If FORW == NULL, then

Print: Underflow!

Goto step 7

[end if]

2. If FORW == BACK, then

Item = Info[flow]

Ptr = FORW

95
 FORW = NULL, BACK = NULL

Goto step 6

[end if]

3. Prev[Next[FORW]] = NULL

4. ptr = FORW

5. FORW = Next[FORW]

6. Next[ptr] = Avail, Prev[Avail] = Ptr, Avail = ptr

7. Exit

96
 17. Double_list_delete_end [BACK, item]

FORW 100 320 BACK

x 29 210 100 45 320 210 12 x

100 210 320

FORW 100 320 BACK

x 29 x

x 610 450
450 610

1. If FORW == NULL, then

Print: Underflow!

Goto step 7

[end if]

2. If FORW == BACK, then

Item = info[BACK]

Ptr = BACK

97
 FORW = NULL, BACK = NULL

Goto step 6

[end if]

3. Next[Prev[Back]] = NULL

4. ptr = BACK

5. BACK = Prev[Back]

6. Next[ptr] = Avail, Prev[Avail] = ptr, Avail = ptr

7. Exit

98
 18. Double_list_delete_loc [loc, item]

FORW 100 410 BACK

x 56 310 100 29 410 310 45 x

100 310 410
loc = 310

1. If FORW == NULL, then

Print: underflow!

Goto step 7

[end if]

2. If FORW == BACK == loc, then

Item = info[loc]

FORW = NULL, BACK = NULL

Goto step 6

[end if]

3. Next[Prev[loc]] = Next[loc]

4. Prev[Next[loc]] = Prev[loc]

5. ptr = loc

6. Next[ptr] = Avail, Prev[Avail] = ptr, Avail = ptr

7. Exit

99
 19. Double_list_traversing [FORW, BACK]

FORW 100 320 BACK

x 29 210 100 45 320 210 12 x

100 210 320

Case 1: Forward to Backward

1. Ptr = FORW

2. Repeat steps 3 to 4 while ptr != NULL

3. print: Info[ptr]

4. ptr = Next[ptr]

[end while]

5. Stop

Case 2: Backward to Forward

1. ptr = BACK

2. Repeat steps 3 to 4 while ptr != NULL

3. print: Info[ptr]

4. ptr = Prev[ptr]

[end while]

5. Stop

100
 20. Double_list_Search[FORW, BACK, item, loc]

FORW 100 320 BACK

x 29 210 100 45 320 210 12 x

100 210 320

1. ptr = FORW, Loc = NULL

2. Repeat step 3 while ptr != NULL

3. If Info[ptr] == item, then

Loc = ptr

Goto step 4

Else

Ptr = Next[ptr]

[end if else]

[end while]

4. If loc == NULL, then

Print: Item is not present

Else

Print: Item is present at loc Location

[end if else]

5. Stop

101
 21. Double_list_Insert_beg[FORW, Avail, item]

FORW 100 320 BACK

x 29 210 100 45 320 210 12 x

100 210 320

x 77 x 77
450 450

Item = 77

x 610 450
450 610

1. If Avail == NULL, then

Print: Overflow!

Goto step 8

[end if]

2. new = Avail, Avail = Next[Avail], Prev[Avail] = NULL

3. Info[new] = item

4. Prev[new] = NULL

5. Next[new] = FORW

6. Prev[FORW] = new

7. FORW = new

8. Stop

102
 22. Double_list_Insert_end[BACK, FORW, Item]

FORW 100 320 BACK

x 29 210 100 45 320 210 12 x

100 210 320

x 77 x 77
450 450

Item = 77

x 610 450
450 610

1. If Avail == NULL, then

Print: Overflow!

Goto step 8

[end if]

2. new = avail, avail = Next[avail], Prev[avail] = NULL

3. Info[new] = item

4. Next[new] = NULL

5. Prev[new] = BACK

6. Next[BACK] = new

7. BACK = new

8. Stop

103
 23. Double_list_insert_loc [FORW, Avail, item]

FORW 100 320 BACK

x 56 210 100 23 320 210 45 x

100 210 320

100 23 320
450

x 610 450
450 610

1. IF Avail == NULL, then

Print: Overflow!

Goto step 8

[end if]

2. new = Avail, Avail = Next[avail], Prev[Avail] = NULL

3. Info[new] = item

4. Prev[new] = Loc

5. Next[new] = Next[loc]

6. Prev[Next[loc]] = new

7. Next[loc] = new

8. Stop

104
ALGORITHM OF
STACK

105
 24. Finding the value of postfix expression (P) using STACK.
1. Add a right parenthesis “)” at the end of P [This acts as a sentinel].

2. Scan P from left to right and repeat step 3 & 4 for each element of P until the sentinel “)”
is encountered.

3. If an operand (*) is encountered, put it on STACK.

4. If an operator is encountered, then:

a. Remove the two top elements of STACK, where A is the top element and B is the
next-to-top element.

b. Evaluate B (*) A.

c. Place the result of (b) back on STACK.

[end of if structure]

[end of step 2 loop]

5. Set value equal to the top element on STACK.

6. Exit.

Example :- 7,5,3,*,+,2,-

Symbol STACK Evaluation Area

7 7
5 7,5
3 7,5,3
* 7,15 5 * 3 = 15
+ 22 7 + 15 = 22
2 22,2
- 20 22 – 2 = 20
) 20 STOP

106
 25. Converting infix to postfix using STACK.
POLISH (Q,P)

Suppose Q is an arithmetic expression written in infix notation. This algorithm finds the
equivalent postfix expression P.

1. Push “(“ onto STACK & add “)” to the end of Q.

2. Scan Q from left to right & repeat step 3 to 6 for each element of Q until the STACK is
empty.

3. If an operand is encountered, add it to P.

4. If a left parenthesis is encountered, push it onto STACK.

5. If an operator (*) is encountered, then:

a. Repeatedly POP from STACK & add to P each operator ( on the top of STACK)
which has the same precedence or higher precedence than (*).

b. Add (*) to STACK.

[end of if structure]

6. If a right parenthesis is encountered, then:

a. Repeatedly POP from STACK & add to P each operator until a left parenthesis is
encountered.

b. Remove the left parenthesis. [Do not add the left parenthesis to P.]

[end of if structure]

[end of step 2 loop]

7. Exit.

107
Example :- (6+4/8-9)

Symbol Scanned STACK Resultant

( (
6 ( 6
+ (+ 6
4 (+ 6,4
/ (+,/ 6,4
8 (+,/ 6,4,8
- (- 6,4,8,/,+
9 (- 6,4,8,/,+,9
) Empty 6,4,8,/,+,9,-

108
ALGORITHMS OF
RECURSION

109
 26. Factorial using Recursion[num, fact is factorial of
number].
1. Input positive integer i.e. num.

2. If num > 0, then

fact = factorial_num(num)

Print: Factorial of num is fact

Else

Print: number can’t be negative

[end if else]

3. Exit.

Factorial_num(num)

If num == 1, then

Return 1

Else

Return(num * factorial_num(num-1))

[end if else]

[end function]

110
 27. Fibonacci series using Recursion[Base values:0,1,N].
1. Input no. of terms to print i.e. N.

2. Set I =1.

3. Repeat step 4 to 6 while ( i <= n).

4. t = fib(i).

5. print t.

6. i = i + 1.

[ end while]

7. Exit.

fib(x)

if (x == 1), then

return 0

else if (x == 2), then

return 1

else

return(fib(x-1) + fib(x-2))

[end if else ladder]

[end function]

111
ALGORITHM OF
BST

112
 28. FUNCTION Insert(root,value)
IF root is NULL, then

RETURN new Node(value) //Create a new node

[end if]

IF value < root.data, then

Root.left = Insert(root.left,value) //Insert in left subtree

ELSE IF value > root.data, then

Root.right = Insert(root.right,value) // Insert in the right subtree

[end if]

RETURN root //Return the unchanged root

END FUNCTION

29. FUNCTION Search(root,value)

IF root is NULL, then

RETURN NULL //Value not found

[end if]

IF root.data = value, then

RETURN ROOT // Value found

ELSE IF value < root.data, then

RETURN Search(root.left,value) // Search in the left subtree

ELSE RETURN Search(root.right,value) // Search in the right subtree

[end if]

END FUNCTION

113
 30. DELETE_NODE_IN_BST(TREE,NODE,KEY)
IF TREE is empty

RRETURN

IF KEY < NODE.value

//Move to the left subtree

DELETE_NODE_IN_BST(TREE, NODE.left, KEY)

ELSE IF KEY > NODE.value

//Move to the right subtree

DELETE_NODE_IN_BST(TREE, NODE.right, KEY)

ELSE

//NODE to be deleted is found

//Case 1: Node is a leaf Node

IF NODE has no children

DELETE_NODE(TREE, NODE)

//Case 2: Node has one child

ELSE IF Node has exactly one child

DELETTE_NODE(TREE, NODE)

//Case 3: Node has two children

ELSE

DELETE_NODE(TREE, NODE)

[end if]

114
ALGORITHM OF
PRE-ORDER,
IN-ORDER,
POST-ORDER

115
 31. PREORDER [INFO, LIFT, RIGHT, ROOT]
1. [Push array index of root node]

(a) TOP = TOP+1 (b) STACK[TOP] = ROOT

2. Repeat steps 3 to 7 while TOP != 0

3. (a) PTR = STACK[TOP] (b) TOP = TOP-1

4. Repeat steps 5 to 7 while PTR != -1

5. Write INFO[PTR] //Processing Node

6. IF RIGHT[PTR] != -1, then //Right child exist

(a) TTOP = TOP+1 (b) STACK[TOP] = RIGHT[PTR]

[end if]

7. PTR = LEFT[PTR]

8. RETURN

32. INORDER [INFO, LEFT, RIGHT, ROOT]

1. PTR = ROOT

2. Repeat step 3 while TOP != 0 or PTR != -1

3. IF PTR != -1, then //Move towards left

TOP = TOP+1, STACK[TOP] = PTR //Push

PTR = LEFT[PTR]

ELSE

PTR = STACK[TOP], TOP = TOP-1 //Pop

Write (INFO[PTR]) //Process current node

PTR = RIGHT[PTR] //Move towards right

[end if]

[end step 2 loop]

4. RETURN

116
 33. POSTORDER [ INFO, LEFT,RIGHT, ROOT]
1. PTR = ROOT

TOP = 1, STACK[TOP] = 0

2. Repeat step 3 while TRUE

3. Repeat while PTR != -1

TOP = TOP + 1, STACK[TOP] = PTR

IF(RIGHT[PTR] != -1), then

TOP = TOP+1, STACK[TOP] = -RIGHT[PTR]

[end if]

PTR = LEFT[PTR]

[end step 3 loop]

4. PTR = STACK[TOP], TOP = TOP-1

5. Repeat steps while PTR > 0

Write (INFO[PTR])

PTR = STACK[TOP], TOP = TOP-1

IF TOP = 1, then

Return

[end if]

[end step 5 loop]

6. IF (PTR < 0), then

PTR = -PTR

[end if]

[end step 2 loop]

7. Return

117
ALGORITHM OF
BFS & DFS

118
 34. BFS (Breadth First Search) Algorithm
1. SET STATUS = 1 (ready state) for each node in G

2. Enqueue the starting node A and Set its STATUS = 2 (waiting state)

3. Repeat Steps 4 and 5 until QUEUE is empty

4. Dequeue a node N. Process it and set its STATUS = 3 (processed state)

5. Enqueue all the neighbours of N that are in the ready state (whose STATUS = 1) and set
their STATUS = 2 (waiting state)

[end of loop]

6. EXIT

35. DFS (Depth First Search) Algorithm

1. SET STATUS = 1 (ready state) for each node in G

2. Push the starting node A on the stack and set its STATUS = 2 (waiting state)

3. Repeat steps 4 and 5 until STACK is empty

4. Pop the top node N. Process it and set its STATUS = 3 (processed state)

5. Push on the stack all the neighbours of N that are in the ready state (whose STATUS =1 )
set their STATUS = 2 (waiting state)

[end of loop]

6. EXIT

119
ALGORITHM OF
SHORTEST PATH

120
 36. Dijkstra’s algorithm for shortest path
1. Create a set of all the unvisited nodes called unvisited set.

2. Assign to every node a distance from start value: for the starting node, it is zero, and for
all the other nodes, it is infinity, since initially no path is known to these nodes.

3. From the unvisited set, select the current node to be the one with the smallest finite
distance; initially this will be the starting node, which has distance zero. If the unvisited set
is empty, or contains only nodes with infinite distance (which are unreachable), then the
algorithm terminates to step 6.

4. For the current node, consider all of its unvisited neighbours and update their distance
through the current node; compare with newly calculated distance to the one currently
assigned to the neighbour and assign it the smaller one. For example, if the current node A
is marked with a distance of 6, and the edge connecting it with its neighbour B has length 2,
then the distance to B through A is 6 + 2 = 8. If B was previously marked with a distance
greater than 8, then update it to 8 (the path to B through A is shorter). Otherwise, keep its
current distance.

5. When we are done considering all of the unvisited neighbours of the current node, mar
the current node as visited and remove it from the unvisited set and Go back to step 3.

6. Once the loop exits (steps 3-5), every visited node will contain its shortest distance from
the starting node.

121
 37. Algorithm of Selection sort.
1. Set i = 1

2. Repeat steps 3 to 7 while (i <= n-1) //Number of passes

3. Set j = i + 1

4. Repeat steps 5 to 6 while ( j <= n) //Number of comparisons

5. If a[i] < a[j], then

Temp = a[i]

a[i] = a[j]

a[j] = temp

[end if]

6. j = j + 1

[end step 4 loop]

7. i = i + 1

[end step 2 loop]

8. Stop

122
 38. Algorithm of Bubble sort.
1. Set i = 1

2. Repeat steps 3 to 7 while (i <= n-1) //Number of passes

3. Set j = 1, flag = 0

4. Repeat steps 5 to 6 while ( j <= n-i) //Number of comparisons

5. If a[i] > a[j+1], then

Temp = a[j]

a[i] = a[j+1]

a[j+1] = temp

flag = flag + 1

[end if]

6. j = j + 1

[end step 4 loop]

7. If flag ==0, then

Goto step 8

i=i+1

[end step 2 loop]

8. Stop

123
 39. Algorithm of Insertion sort.
1. target = a[i]

j=i–1

Repeat steps 2 and 3 for i = 2,3,…….N

2. Repeat while target < a[j] and j > 1

a[j + 1] = a[j]

j=j–1

[end step 2 loop]

3. a[j + 1] = target

[end step 1 loop]

4. Return

124