1. Check if the next_node is NULL or not.

If it’s NULL, return from the function

because any new node can not be added before a NULL
2. Allocate memory for the new node, let it be called new_node
3. Set new_node->data = new_data
4. Set the previous pointer of this new_node as the previous node of the next_node,
new_node->prev = next_node->prev
5. Set the previous pointer of the next_node as the new_node, next_node->prev =
new_node
6. Set the next pointer of this new_node as the next_node, new_node->next =
next_node;
7. If the previous node of the new_node is not NULL, then set the next pointer of
this previous node as new_node, new_node->prev->next = new_node
 Lecture-10
Circular Linked List
Circular linked list is a linked list where all nodes are connected to form a circle. There is
no NULL at the end. A circular linked list can be a singly circular linked list or doubly
circular linked list.

Advantages of Circular Linked Lists:

1) Any node can be a starting point. We can traverse the whole list by starting from any
point. We just need to stop when the first visited node is visited again.
2) Useful for implementation of queue. Unlike this implementation, we don’t need to
maintain two pointers for front and rear if we use circular linked list. We can maintain a
pointer to the last inserted node and front can always be obtained as next of last.
3) Circular lists are useful in applications to repeatedly go around the list. For example,
when multiple applications are running on a PC, it is common for the operating system
to put the running applications on a list and then to cycle through them, giving each of
them a slice of time to execute, and then making them wait while the CPU is given to
another application. It is convenient for the operating system to use a circular list so that
when it reaches the end of the list it can cycle around to the front of the list.
4) Circular Doubly Linked Lists are used for implementation of advanced data structures
like Fibonacci Heap.
Insertion in an empty List

Initially when the list is empty, last pointer will be NULL.

After inserting a node T,

After insertion, T is the last node so pointer last points to node T. And Node T is first
and last node, so T is pointing to itself.
Function to insert node in an empty List,
struct Node *addToEmpty(struct Node *last, int data)
{
// This function is only for empty list
if (last != NULL)
return last;
 // Creating a node dynamically.
struct Node *last =
(struct Node*)malloc(sizeof(struct Node));

// Assigning the data.

last -> data = data;

// Note : list was empty. We link single node

// to itself.
last -> next = last;

return last;
}
Run on IDE

Insertion at the beginning of the list

To Insert a node at the beginning of the list, follow these step:

1. Create a node, say T.
2. Make T -> next = last -> next.
3. last -> next = T.

After insertion,

Function to insert node in the beginning of the List,

struct Node *addBegin(struct Node *last, int data)
{
if (last == NULL)
return addToEmpty(last, data);

// Creating a node dynamically.

struct Node *temp
= (struct Node *)malloc(sizeof(struct Node));

// Assigning the data.

temp -> data = data;

// Adjusting the links.

temp -> next = last -> next;
last -> next = temp;

return last;
}

Insertion at the end of the list

To Insert a node at the end of the list, follow these step:

1. Create a node, say T.
2. Make T -> next = last -> next;
3. last -> next = T.
4. last = T.

After insertion,

Function to insert node in the end of the List,

struct Node *addEnd(struct Node *last, int data)
{
if (last == NULL)
return addToEmpty(last, data);

// Creating a node dynamically.

 struct Node *temp =
(struct Node *)malloc(sizeof(struct Node));

// Assigning the data.

temp -> data = data;

// Adjusting the links.

temp -> next = last -> next;
last -> next = temp;
last = temp;

return last;
}

Insertion in between the nodes

To Insert a node at the end of the list, follow these step:

1. Create a node, say T.
2. Search the node after which T need to be insert, say that node be P.
3. Make T -> next = P -> next;
4. P -> next = T.
Suppose 12 need to be insert after node having value 10,

After searching and insertion,

Function to insert node in the end of the List,
struct Node *addAfter(struct Node *last, int data, int item)
{
if (last == NULL)
return NULL;
struct Node *temp, *p;
p = last -> next;
// Searching the item.
do
{
if (p ->data == item)
{
temp = (struct Node *)malloc(sizeof(struct Node));
// Assigning the data.
temp -> data = data;
// Adjusting the links.
temp -> next = p -> next;
// Adding newly allocated node after p.
p -> next = temp;
// Checking for the last node.
if (p == last)
last = temp;
return last;
}
p = p -> next;
} while (p != last -> next);

cout << item << " not present in the list." << endl;
return last;
}
 Module-2:
Lecture-11
Memory Allocation-
Whenever a new node is created, memory is allocated by the system. This memory is
taken from list of those memory locations which are free i.e. not allocated. This list is
called AVAIL List. Similarly, whenever a node is deleted, the deleted space becomes
reusable and is added to the list of unused space i.e. to AVAIL List. This unused space
can be used in future for memory allocation.
Memory allocation is of two types-
1. Static Memory Allocation
2. Dynamic Memory Allocation

1. Static Memory Allocation:

When memory is allocated during compilation time, it is called ‘Static Memory
Allocation’. This memory is fixed and cannot be increased or decreased after
allocation. If more memory is allocated than requirement, then memory is wasted. If
less memory is allocated than requirement, then program will not run successfully.
So exact memory requirements must be known in advance.
2. Dynamic Memory Allocation:
When memory is allocated during run/execution time, it is called ‘Dynamic Memory
Allocation’. This memory is not fixed and is allocated according to our requirements.
Thus in it there is no wastage of memory. So there is no need to know exact memory
requirements in advance.
Garbage Collection-
Whenever a node is deleted, some memory space becomes reusable. This memory
space should be available for future use. One way to do this is to immediately insert the
free space into availability list. But this method may be time consuming for the operating
system. So another method is used which is called ‘Garbage Collection’. This method is
described below: In this method the OS collects the deleted space time to time onto the
availability list. This process happens in two steps. In first step, the OS goes through all
the lists and tags all those cells which are currently being used. In the second step, the
OS goes through all the lists again and collects untagged space and adds this collected
space to availability list. The garbage collection may occur when small amount of free
space is left in the system or no free space is left in the system or when CPU is idle and
has time to do the garbage collection.
Compaction
One preferable solution to garbage collection is compaction.
The process of moving all marked nodes to one end of memory and all available
memory to other end is called compaction. Algorithm which performs compaction is
called compacting algorithm.
 Lecture-12

Infix to Postfix Conversion

1 #include<stdio.h>
2 char stack[20];
3 int top = -1;
4 void push(char x)
5 {
6 stack[++top] = x;
7 }
8
9 char pop()
10 {
11 if(top == -1)
12 return -1;
13 else
14 return stack[top--];
15 }
16
17 int priority(char x)
18 {
19 if(x == '(')
20 return 0;
21 if(x == '+' || x == '-')
22 return 1;
23 if(x == '*' || x == '/')
24 return 2;
25 }
26
27 main()
28 {
29 char exp[20];
30 char *e, x;
31 printf("Enter the expression :: ");
32 scanf("%s",exp);
33 e = exp;
34 while(*e != '\0')
35 {
36 if(isalnum(*e))
37 printf("%c",*e);
38 else if(*e == '(')
39 push(*e);
40 else if(*e == ')')
41 {
42 while((x = pop()) != '(')
43 printf("%c", x);
44 }
45 else
46 {
47 while(priority(stack[top]) >= priority(*e))
48 printf("%c",pop());
49 push(*e);
50 }
51 e++;
52 }
53 while(top != -1)
54 {
55 printf("%c",pop());
56 }
57 }

OUTPUT:

Enter the expression :: a+b*c

abc*+

Enter the expression :: (a+b)*c+(d-a)

ab+c*da-+
Evaluate POSTFIX Expression Using Stack

1 #include<stdio.h>

2 int stack[20];

3 int top = -1;

4 void push(int x)

5 {

6 stack[++top] = x;

7 }

9 int pop()

10 {

11 return stack[top--];

12 }

13

14 int main()

15 {

16 char exp[20];

17 char *e;

18 int n1,n2,n3,num;

19 printf("Enter the expression :: ");

20 scanf("%s",exp);

21 e = exp;

22 while(*e != '\0')

23 {

24 if(isdigit(*e))
25 {

26 num = *e - 48;

27 push(num);

28 }

29 else

30 {

31 n1 = pop();

32 n2 = pop();

33 switch(*e)

34 {

35 case '+':

36 {

37 n3 = n1 + n2;

38 break;

39 }

40 case '-':

41 {

42 n3 = n2 - n1;

43 break;

44 }

45 case '*':

46 {

47 n3 = n1 * n2;

48 break;

49 }
50 case '/':

51 {

52 n3 = n2 / n1;

53 break;

54 }

55 }

56 push(n3);

57 }

58 e++;

59 }

60 printf("\nThe result of expression %s = %d\n\n",exp,pop());

61 return 0;

62

63 }

64

Output:

Enter the expression :: 245+*

The result of expression 245+* = 18

 Lecture-13

Binary Tree

A binary tree consists of a finite set of nodes that is either empty, or consists of one
specially designated node called the root of the binary tree, and the elements of two
disjoint binary trees called the left subtree and right subtree of the root.
Note that the definition above is recursive: we have defined a binary tree in terms of
binary trees. This is appropriate since recursion is an innate characteristic of tree
structures.
Diagram 1: A binary tree

Binary Tree Terminology

Tree terminology is generally derived from the terminology of family trees (specifically,
the type of family tree called a lineal chart).
 Each root is said to be the parent of the roots of its subtrees.
 Two nodes with the same parent are said to be siblings; they are the children of
their parent.
 The root node has no parent.
 A great deal of tree processing takes advantage of the relationship between a
parent and its children, and we commonly say a directed edge (or simply
an edge) extends from a parent to its children. Thus edges connect a root with
the roots of each subtree. An undirected edge extends in both directions between
a parent and a child.
  Grandparent and grandchild relations can be defined in a similar manner; we
could also extend this terminology further if we wished (designating nodes as
cousins, as an uncle or aunt, etc.).

Other Tree Terms

 The number of subtrees of a node is called the degree of the node. In a binary
tree, all nodes have degree 0, 1, or 2.
 A node of degree zero is called a terminal node or leaf node.
 A non-leaf node is often called a branch node.
 The degree of a tree is the maximum degree of a node in the tree. A binary tree
is degree 2.
 A directed path from node n1 to nk is defined as a sequence of nodes n1, n2,
..., nk such that ni is the parent of ni+1 for 1 <= i < k. An undirected path is a
similar sequence of undirected edges. The length of this path is the number of
edges on the path, namely k – 1 (i.e., the number of nodes – 1). There is a path
of length zero from every node to itself. Notice that in a binary tree there is
exactly one path from the root to each node.
 The level or depth of a node with respect to a tree is defined recursively: the level
of the root is zero; and the level of any other node is one higher than that of its
parent. Or to put it another way, the level or depth of a node ni is the length of the
unique path from the root to ni.
 The height of ni is the length of the longest path from ni to a leaf. Thus all leaves
in the tree are at height 0.
 The height of a tree is equal to the height of the root. The depth of a tree is equal
to the level or depth of the deepest leaf; this is always equal to the height of the
tree.
 If there is a directed path from n1 to n2, then n1 is an ancestor of n2 and n2 is a
descendant of n1.
 Lecture-14

Special Forms of Binary Trees

There are a few special forms of binary tree worth mentioning.

If every non-leaf node in a binary tree has nonempty left and right subtrees, the tree is
termed a strictly binary tree. Or, to put it another way, all of the nodes in a strictly binary
tree are of degree zero or two, never degree one. A strictly binary tree with N leaves
always contains 2N – 1 nodes.
Some texts call this a "full" binary tree.
A complete binary tree of depth d is the strictly binary tree all of whose leaves are at
level d.
The total number of nodes in a complete binary tree of depth d equals 2d+1 – 1. Since all
leaves in such a tree are at level d, the tree contains 2d leaves and, therefore, 2d - 1
internal nodes.
Diagram 2: A complete binary tree

A binary tree of depth d is an almost complete binary tree if:

 Each leaf in the tree is either at level d or at level d – 1.
 For any node nd in the tree with a right descendant at level d, all the left
descendants of nd that are leaves are also at level d.
Diagram 3: An almost complete binary tree
An almost complete strictly binary tree with N leaves has 2N – 1 nodes (as does any
other strictly binary tree). An almost complete binary tree with N leaves that is not
strictly binary has 2N nodes. There are two distinct almost complete binary trees
with N leaves, one of which is strictly binary and one of which is not.
There is only a single almost complete binary tree with N nodes. This tree is strictly
binary if and only if N is odd.

Representing Binary Trees in Memory

Array Representation
For a complete or almost complete binary tree, storing the binary tree as an array may
be a good choice.
One way to do this is to store the root of the tree in the first element of the array. Then,
for each node in the tree that is stored at subscript k, the node's left child can be stored
at subscript 2k+1 and the right child can be stored at subscript 2k+2. For example, the
almost complete binary tree shown in Diagram 2 can be stored in an array like so:

However, if this scheme is used to store a binary tree that is not complete or almost
complete, we can end up with a great deal of wasted space in the array.
For example, the following binary tree

would be stored using this techinque like so:

Linked Representation
If a binary tree is not complete or almost complete, a better choice for storing it is to use
a linked representation similar to the linked list structures covered earlier in the
semester:
Each tree node has two pointers (usually named left and right). The tree class has a
pointer to the root node of the tree (labeled root in the diagram above).
Any pointer in the tree structure that does not point to a node will normally contain the
value NULL. A linked tree with N nodes will always contain N + 1 null links.
 Lecture-15
Tree Traversal:
Traversal is a process to visit all the nodes of a tree and may print their values too.
Because, all nodes are connected via edges (links) we always start from the root
(head) node. That is, we cannot randomly access a node in a tree. There are three
ways which we use to traverse a tree −
 In-order Traversal
 Pre-order Traversal
 Post-order Traversal
Generally, we traverse a tree to search or locate a given item or key in the tree or to
print all the values it contains.
In-order Traversal
In this traversal method, the left subtree is visited first, then the root and later the right
sub-tree. We should always remember that every node may represent a subtree itself.
If a binary tree is traversed in-order, the output will produce sorted key values in an
ascending order.

We start from A, and following in-order traversal, we move to its left subtree B. B is
also traversed in-order. The process goes on until all the nodes are visited. The output
of inorder traversal of this tree will be −
D→B→E→A→F→C→G
Algorithm

Until all nodes are traversed −

Step 1 − Recursively traverse left subtree.
Step 2 − Visit root node.
Step 3 − Recursively traverse right subtree.

Pre-order Traversal
In this traversal method, the root node is visited first, then the left subtree and finally
the right subtree.

We start from A, and following pre-order traversal, we first visit A itself and then move
to its left subtree B. B is also traversed pre-order. The process goes on until all the
nodes are visited. The output of pre-order traversal of this tree will be −
A→B→D→E→C→F→G

Algorithm

Until all nodes are traversed −

Step 1 − Visit root node.
Step 2 − Recursively traverse left subtree.
Step 3 − Recursively traverse right subtree.
Post-order Traversal
In this traversal method, the root node is visited last, hence the name. First we traverse
the left subtree, then the right subtree and finally the root node.

We start from A, and following Post-order traversal, we first visit the left subtree B. B is
also traversed post-order. The process goes on until all the nodes are visited. The
output of post-order traversal of this tree will be −
D→E→B→F→G→C→A

Algorithm

Until all nodes are traversed −

Step 1 − Recursively traverse left subtree.
Step 2 − Recursively traverse right subtree.
Step 3 − Visit root node.
 Lecture-16
AVL Trees
An AVL tree is another balanced binary search tree. Named after their
inventors, Adelson-Velskii and Landis, they were the first dynamically balanced trees to
be proposed. Like red-black trees, they are not perfectly balanced, but pairs of sub-
trees differ in height by at most 1, maintaining an O(logn) search time. Addition and
deletion operations also take O(logn) time.
Definition of an AVL tree
An AVL tree is a binary search tree which has the following
properties:
1. The sub-trees of every node differ in height by at most one.
2. Every sub-tree is an AVL tree.
Balance requirement
for an AVL tree: the left
and right sub-trees
differ by at most 1 in
height.
You need to be careful with this definition: it permits some apparently unbalanced trees!
For example, here are some trees:

Tree AVL tree?

Yes
Examination shows
that each left sub-tree
has a height 1 greater
than each right sub-
tree.
 No
Sub-tree with root 8 has
height 4 and sub-tree
with root 18 has height
2

Insertion
As with the red-black tree, insertion is somewhat complex and involves a number of
cases. Implementations of AVL tree insertion may be found in many textbooks: they rely
on adding an extra attribute, the balance factor to each node. This factor indicates
whether the tree is left-heavy (the height of the left sub-tree is 1 greater than the right
sub-tree), balanced (both sub-trees are the same height) or right-heavy(the height of the
right sub-tree is 1 greater than the left sub-tree). If the balance would be destroyed by
an insertion, a rotation is performed to correct the balance.
A new item has been
added to the left subtree
of node 1, causing its
height to become 2
greater than 2's right sub-
tree (shown in green). A
right-rotation is performed
to correct the imbalance.