Data Structures Syllabus

COURSE OBJECTIVES:
 To introduce various searching and sorting techniques
 To demonstrate operations of linear and non-linear data structure
 To develop an application using suitable data structure.
COURSE OUTCOMES: After completion of the course, the student should be able to

CO-1: Understand basic concepts of data structures and analyse computation complexity.
CO-2: Apply linear data structures to implement various sorting, searching techniques.
CO-3: Solve the given problem using linear data structures.
CO-4: Execute the given problem using non-linear data structures.
CO-5: Analyze appropriate and efficient data structure to implement a given problem.

UNIT-I:
Introduction to Data Structures: Abstract Data Types (ADT), Asymptotic Notations. Time-
Space trade off. Searching: Linear Search and Binary Search Techniques and their time complexities.
Linear Data Structures: Stacks - ADT Stack and its operations: Applications of Stacks:
Recursion, Expression Conversion, and evaluation.
UNIT-II:
Linear Data Structures: Queues - ADT queue, Types of Queue: Linear Queue,
CircularQueue, Double ended queue, operations on each types of Queues
Linked Lists: Singly linked lists: Representation in memory, Operations: Traversing, Searching,
insertion, Deletion from linked list; Linked representation of Stack and Queue. Doubly linked List,
Circular Linked Lists: All operations

UNIT-III:
Trees: Basic Tree Terminologies, Different types of Trees: Binary Tree, Binary Search Tree, AVL Tree;
Tree Operations on each of the trees and their algorithms with time complexities.
B-Trees: Definition, Operations.
UNIT-IV:
Priority Queue: Definition, Operations and their time complexities.
Sorting: Objective and properties of different sorting algorithms: Quick Sort, Heap
Sort, Merge Sort; Radix sort
UNIT-V:
Dictionaries: Definition, ADT, Linear List representation, operations- insertion, deletion and
searching, Hash Table representation, Hash function-Division Method, Collision Resolution
Techniques-Separate Chaining, open addressing-linear probing, quadratic probing, double
hashing, Rehashing.

Graphs: Graph terminology –Representation of graphs –Graph Traversal: BFS (breadth first search)
–DFS (depth first search) –Minimum Spanning Tree.

TEXT BOOKS:
1. Fundamental of Data Structure, Horowitz and Sahani, Galgotia Publication
2. Data Structure, Lipschutz, Schaum Series

REFERENCES:
1. Algorithms, Data Structures, and Problem Solving with C++, Illustrated Edition
byMark Allen Weiss, Addison-Wesley Publishing Company
2. How to Solve it by Computer, 2nd Impression by R.G. Dromey, Pearson Education
 UNIT-I
1.1. Abstract data type (ADT):
• Abstract Data type is the way we look at a data structure, focusing on
what it does and ignoring how it does its job.
• Abstract Data type (ADT) is a type (or class) for objects whose behavior
is defined by a set of values and a set of operations.
• The definition of ADT only mentions what operations are to be performed
but not how these operations will be implemented. It does not specify
how data will be organized in memory and what algorithms will be used
for implementing the operations.
• The following figure gives the visual representation of abstract data
type.

Fig 1: Abstract data type

List ADT:
• get() – Return an element from the list at any given position
• insert() – Insert an element at any position of the list.
• remove() – Remove the first occurrence of any element from a non-
empty list.
• removeAt() – Remove the element at a specified location from a non-
empty list.
• replace() – Replace an element at any position by another element.
• size() – Return the number of elements in the list.
• isEmpty() – Return true if the list is empty, otherwise return false.
• isFull() – Return true if the list is full, otherwise return false.
STACK ADT:
• push() – Insert an element at one end of the stack called top.
• pop() – Remove and return the element at the top of the stack, if it is
not empty.
• peek() – Return the element at the top of the stack without removing
it, if the stack is not empty.
• size() – Return the number of elements in the stack.
• isEmpty() – Return true if the stack is empty, otherwise return false
• isFull() – Return true if the stack is full, otherwise return false.
QUEUE ADT:
• enqueue() – Insert an element at the end of the queue.
• dequeue() – Remove and return the first element of the queue, if the
queue is not empty.
• peek() – Return the element of the queue without removing it, if the
queue is not empty.
• size() – Return the number of elements in the queue.
• isEmpty() – Return true if the queue is empty, otherwise return false.
• isFull() – Return true if the queue is full, otherwise return false.

1.2. Asymptotic notations:

Asymptotic Notations are the expressions that are used to represent the
complexity of an algorithm.

There are three types of analysis that we perform on a particular algorithm.

They are
1. Best Case
2. Worst Case
3. Average Case
Best Case: Minimum time or space required for program execution.
Worst Case: Maximum time or space required for program execution.
Average Case: Average time or space required for program execution.

Asymptotic notations are three types. Which are

1. Big- O Notation (O)

2. Omega Notation ( Ω )
3. Theta Notation ( ϴ )
Big-O Notation (O) : Big-O notation specifically describes worst-case scenario.
It represents the upper bound running time complexity of an algorithm.
Definition: f(n) and g(n) are two functions and f(n) = O(g(n)) iff there exist
two positive constants c and n0 such that f(n) ≤ c.g(n) for all n ≥ n0.
The following example explains how we represent the time and space complexity
using Big O notation.
O(1) – Constant time
It represents the complexity of an algorithm that always executes at the same
time or space regardless of the input data.
Example: The following step will always execute at the same time (or space)
regardless of the size of the input data.
num = a[5];
O(n) – Linear time
It represents the complexity of an algorithm, whose performance will grow
linearly (in direct proportion) to the size of the input data.
Example: The execution time will depend on the size of the array. When the size
of the array increases, the execution time will also increase in the same
proportion (linearly).
Traversing an array
for(i=0 ;i<=n; i++){ }
O(n2)
It represents the complexity of an algorithm, whose performance is directly
proportional to the square of the size of the input data.
Example: Traversing 2D array
for(i=1 ;i<=n; i++)
{
for(j=1; j<=n;j++)
{
...........
}
}
Other examples: Bubble sort, insertion sort, and selection sort algorithms
Similarly, there are other Big O notations such as:
Logarithmic growth O(log n), log-linear growth O(n log n), exponential growth
O(2^n), and factorial growth O(n!).
Relationship between the complexities:
O(1) < O(log n) < O (n) < O(n log n) < O(n^2) < O (n^3)< O(2^n) < O(n!)
Omega Notation (Ω)

Omega notation specifically describes the best-case scenario. It represents the

lower bound running time complexity of an algorithm. So if we represent a
complexity of an algorithm in Omega notation, it means that the
algorithm cannot be completed in less time than this, it would at least
take the time represented by Omega notation or it can take more (when not in
the best case scenario).

Definition: f(n) and g(n) are two functions and f(n) = Ω (g(n)) iff there
exist two positive constants c and n0 such that f(n) ≥ c.g(n) for all n ≥ n0

Theta Notation (θ)

This notation describes both the upper bound and lower bound of an
algorithm so we can say that it defines exact asymptotic behavior. In the real-
case scenario the algorithm does not always run on best and worst cases, the
average running time lies between best and worst and can be represented by the
theta notation.
Definition: f(n) and g(n) are two functions and f(n) = Ω (g(n)) iff there
exist three positive constants c1, c2 and n0 such that c1.g(n) ≤ f(n) ≤ c2.g(n)
for all n ≥ n0

1.3. Time and Space Tradeoff

A trade-off is a situation where one thing increases, and another thing
decreases.
Definition: A time-space or space-time trade-off is a way of solving a
problem in:
 less time by using more memory, or
 less space by spending more time.

The best Algorithm is that which helps to solve a problem that requires less
space in memory and also takes less time to generate the output. But in
general, it is not always possible to achieve both of these conditions at the
same time.

There are 4 types of time-Space trade-off

 Compressed or Uncompressed data
 Re Rendering or Stored images
 Smaller code or loop unrolling
 Lookup tables or Recalculation

Compressed vs Uncompressed:

Time-space trade-off plays a role in data storage also. If stored data is

uncompressed, it required more space but less access time. If stored data
is compressed, it requires less space but more time.
Re Rendering or Stored images

Storing only the source and rendering it as an image every time the page is
requested would be trading time for space: more time used, but less space.
Storing the image would be trading space for time: more space, but less
time.

Smaller code or loop unrolling

Smaller code with loops occupies less space but requires more
computation time (for jumping back to the beginning of the loop after each
iteration).
Larger codes require more space but less computation time.

Lookup table vs Recalculation

Lookup table: An implementation can include the entire table, which

reduces computing time, but increases the amount of memory needed.
Re-calculation: An implementation can compute table entries as needed
increasing computing time, but reducing memory requirements.

1.4. Searching
Searching is the processing of finding a particular element is present in the
list or not. There are two types of searching techniques.
1. Linear search
2. Binary search.
1.4.1. Linear Search
Linear search technique is also known as sequential search technique. The
linear search is a method of searching an element in a list in sequence. In this
method, the array is searched for the required element from the beginning of
the list/array or from the last element to first element of array and contin ues
until the item is found or the entire list/array has been searched.
Algorithm
Step 1: set-up a flag to indicate “element not found”.
Step 2: Take the first element in the list.
Step 3: If the element in the list is equal to the desired element.
 Set flag to “element found.”
 Display the message “element found in the list.”
 Go to step 6
Step 4: If it is not the end of list,
  Take the next element in the list
 Go to step 3
Step 5: If the flag is “element not found”
Display the message “element not found”
Step 6: End of the Algorithm

Program
/*
Linear search
*/

#include<stdio.h>
#include<conio.h>
void main()
{
int a[10],i,key,flag=0,n;
clrscr();
printf("\n Array length(No of elements)\n");
scanf("%d",&n);
printf("\n ENter array elements\n");
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
printf("\n Enter key\n");
scanf("%d",&key);
for(i=0;i<n;i++)
{
if(key == a[i])
{
flag=1;
break;
}
}
if(flag == 1)
{
printf("\n Search is successful\n");
}
else
{
printf("\n Search is unsuccessful\n");
}

getch();
}
Advantages
1. It is a simple and conventional method of searching for data. The linear
or sequential name implies that the items are stored in a systematic
manner.
2. The elements in the list can be in any order. i.e. The linear search can
be applied on sorted or unsorted linear data structure.
Disadvantages
1. This method is insufficient when a large number of elements is
present in list.
2. It consumes more time and reduces the retrieval rate of the system.
Time complexities:
1. Best case – O(1) – if the key element is at the first position
2. Average case – O(n) – if the key element is in the middle of the array
3. Worst case - O(n) – if the key element is the at the end of the array.

1.4.2. Binary Search

Binary search is quicker than the linear search. However, it cannot be applied
on unsorted data structure. The binary search is based on the approach
divide-and-conquer. The binary search starts by testing the data in the
middle element of the array. This determines target is whether in the first half
or second half. If target is in first half, we do not need to check the second half
and if it is in second half no need to check in first half. Similarly, we repeat
this process until we find target in the list or not found from the list. Here we
need 3 variables to identify first, last and middle elements.
To implement binary search method, the elements must be in sorted order.
Search is performed as follows:
1. The key is compared with an item in the middle position of an array.
2. If the key matches with the item, return it and stop.
3. If the key is less than mid positioned item, then the item to be found
must be in the first half of array, otherwise it must be in second half
of array.
4. Repeat the procedure for lower (or upper half) of array until the
element is found.
Algorithm:

Program:
/*
Binary search
*/

#include<stdio.h>
#include<conio.h>
void main()
{
int a[10],low,i,high,key,flag=0,n,mid;
clrscr();
printf("\n Array length(No of elements)\n");
scanf("%d",&n);
printf("\n Enter array elements\n");
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
printf("\n Enter key\n");
scanf("%d",&key);
low=0;
high=n-1;

while(low<=high)
{
mid = (low+high)/2;
if(key == a[mid])
{
flag=1;
break;
}
else if(key < a[mid])
{
high = mid-1;
}
else
{
low = mid+1;
}
}

if(flag==1)
{
printf("\n Search is successful\n");
}
else
{
printf("\n Search is unsuccessful\n");
}

getch();
}
Advantages
1. It takes less time complexity (O(logn))
2. it is efficient when the data set is large.
Disadvantages
1. The elements must be in either ascending or descending order.
Time complexities
1. Best case – O(1) – if the key element is in the middle position of an array.
2. Average case – O(logn)
3. Worst case – O(logn)

1.5. Data Structures

• A data structure is basically a group of data elements that are put
together under one name, and which defines a particular way of
storing and organizing data in a computer so that it can be used
efficiently.
• Definition: it is a particular way of organizing and storing data in a
computer so that it can be used efficiently.
• Examples: Arrays, linked lists, queues, stacks, binary trees, and hash
tables.
• Data structures are applied in the following areas:

• Compiler Design • Operating System

• Data base Management Systems • Statistical Analysis

• Simulation • Artificial Intelligence

• Graphics

1.5.1. Classification of Data Structures

• Basically, data strictures are divided into two categories, which are
Primitive data structures and non-primitive data structures.
• Primitive data structures are also called as simple data types. The
primitive data structures are integer, real, character and bool.
• Based on the structure and arrangement of data, non-primitive data
structures are further divided into linear and non-linear data structure.
• Linear data structure: A data structure is said to be linear if its
elements form a linear or sequential list.
• In linear data structures, the data is arranged in a linear fashion
although the way they are stored in the memory need not be sequential.
 Example: Arrays, stacks, queues and linked lists

Fig. Classification of data structures.

• Non-linear data structures: A data structure is to be non-linear if the
data is not arranged in sequential.
• In non-linear data structures, insertion and deletion of data is
therefore not possible in a linear fashion.
• Examples: Trees and Graphs.
Array: An array is a group of similar data elements.
Stack: A stack is a linear data structures, in which insertions and deletions
are performed only from one end is called top of the stack.
In stack the elements which is inserted last is to be removed first. Hence it
is called Last-in-first-out (LIFO) data structure.
Queue: A queue is a linear data structure in which insertions are performed
at rear end and deletions are performed at front end.
In queue, the first inserted element is to be removed first. Hence it is
called First-In-First-Out (FIFO) data structure.

Linked List: A linked list is a linear data structure; it consists of nodes where
each node contains a data field and a reference(link) to the next node in the
list.

Note: Non-linear data structures follows hierarchy, i.e. the elements are
arranged in multiple levels.
Tree: A tree can be theoretically defined as a finite set of one or more data
items (or nodes) such that :
1. There is a special node called the root of the tree.
2. Removing nodes (or data item) are partitioned into number of mutually
exclusive (i.e., disjoined) subsets each of which is itself a tree, are called
sub tree.
Graph: A graph is a structure made of two components: a set of vertices V,
and a set of edges E. Therefore, a graph is G = (V, E), where G is a graph.

1.5.2. Data Structure Operations

1. Traversing: It means to access each data item exactly once so that it
can be processed
2. Searching: It is used to find the location of one or more data items
that satisfy the given constraint.
3. Inserting: It is used to add new data items to the given list of data
items.
4. Deleting: It means to remove (delete) a particular data item from the
given collection of data items.
5. Sorting: Data items can be arranged in some order like ascending
order or descending order depending on the type of application.
6. Merging: Lists of two sorted data items can be combined to form a
single list of sorted data items.

1.6. Stack:
Definition: A stack is a linear data structure in which insertions and
deletions are performed at only one end called the top of the stack.
The last added element will be first removed from the stack. Hence it is also
called Last-in-First-out (LIFO) data structure.
Note:
1. The most frequently accessible element in the stack is the top most
elements, whereas the least accessible element is the bottom of the stack.
The basic operations on stack are 1. Push 2. Pop
1. Push: Inserting an element into the stack is called push.
2. Pop: Removing an element from the stack is called pop.
PRIMITIVE STACK OPERATIONS: PUSH AND POP
The primitive operations performed on the stack are as follows:
PUSH: The process of adding (or inserting) a new element to the top of the
stack is called PUSH operation. Pushing an element to a stack will add the
new element at the top. After every push operation the top is incremented by
one. If the array is full and no new element can be accommodated, then the
stack overflow condition occurs.
Algorithm:
Step 1: IF TOP = MAX-1 PRINT OVERFLOW [END OF IF]
Step 2: SET TOP = TOP+1
Step 3: SET STACK[TOP] = VALUE
Step 4: END
POP: The process of deleting (or removing) an element from the top of stack
is called POP operation. After every pop operation the stack is decremented
by one. If there is no element in the stack and the pop operation is performed,
then the stack underflow condition occurs.
Algorithm:
Step 1: IF TOP = NULL PRINT UNDERFLOW [END OF IF]
Step 2: SET VAL = STACK[TOP]
Step 3: SET TOP = TOP-1
Step 4: END
1.6.1. Stack ADT
• push() – Insert an element at one end of the stack called top.
• pop() – Remove and return the element at the top of the stack, if it is
not empty.
• peek() – Return the element at the top of the stack without removing
it, if the stack is not empty.
• size() – Return the number of elements in the stack.
• isEmpty() – Return true if the stack is empty, otherwise return false
• isFull() - Return true if the stack is full, otherwise return false.
1.6.2. Implementation of Stack
There are two ways to implement a stack.
1. Array representation
2. Linked list representation. (will be discussed in UNIT-2)
C program to implement stack using arrays
#include<stdio.h>
#include<ctype.h>
#define SIZE 5
int s[100];
int top=-1;

void push(int x)
{
if(top==SIZE-1)
{
printf("\n Overflow");
}
else
{
top++;
s[top]=x;
}
}

void pop()
{
if(top==-1)
{
printf("\n Underflow");
}
else
{
printf("\n Deleted item is %d",s[top]);
top--;
}
}

void peek()
{
if(top==-1)
{
printf("\n Underflow");
}
else
{
printf("\n top of the stack is %d",s[top]);
}
}

void display()
{
int i;
 if(top==-1)
{
printf("\n Stack is empty");
}
else
{
for(i=top;i>=0;i--)
{
printf("\n %d",s[i]);
}
}
}

void main()
{
int ch,x;
while(1)
{
printf("\n 1. Push \n 2. Pop \n 3. Peek \n 4. Display \n 5.
Exit\n");
printf("\n Enter your choice:");
scanf("%d",&ch);
switch(ch)
{
case 1: printf("\n Enter the item to be inserted into the
stack:");
scanf("%d",&x);
push(x);
break;
case 2: pop();
break;
case 3: peek();
break;
case 4: display();
break;
case 5: exit(0);
default : printf("\n Enter correct choice");
}
}

1.6.3. Applications of Stack:

Stack has mainly three applications:
1. Converting infix expression into postfix expression.
2. Evaluating postfix expression
3. Recursion.
Expression: An expression is defined as the number of operands or data
items combined with several operators.
There are basically three types of notation for an expression (mathematical
expression.
1. Infix expression
2. Postfix expression
3. Prefix expression
Infix expression: The operator is placed between the operands is called infix
expression.
Example: 2+3, a+b*c, 2+5/2*3-4^5, etc…
Postfix expression: The operator is placed after the operands is called postfix
expression. it is also known as suffix notation or reverse polish notation.
Example: 23+, abc*+, 23+5*, etc…
Prefix expression: The operator is placed before the operands is called
prefix expression. it is also called polish notation in the honour of the polish
mathematician Jan Lukasiewicz who developed this notation.
Example: +23, +a*bc, *+235, etc…
Note: postfix notation is most suitable for a computer to calculate any expression
(due to its reverse characteristic) and is the universally accepted notation for
designing Arithmetic and Logical Unit (ALU) of the CPU (processor).
Advantages of Postfix notation: Using infix notation, we cannot tell the order
in which operators should be applied. But using postfix expression operands
appear before the operator, so there is no need for operator precedence and other
rules. As soon as an operator appears in the postfix expression during scanning
of postfix expression the topmost operands are popped off and are calculated
by applying the encountered operator. Place the result back onto the stack.
Operator precedence
1. Exponential operator ^ Highest precedence
2. Multiplication/Division *, / Next precedence
3. Addition/Subtraction +, - Least precedence

Converting infix expression to postfix expression.

The rules to be remembered during infix to postfix conversion are:
1. Parenthesize the expression starting from left to light.
 2. During parenthesizing the expression, the operands associated with
operator having higher precedence are first parenthesized.
3. The sub-expression (part of expression), which has been converted
into postfix, is to be treated as single operand.
4. Once the expression is converted to postfix form, remove the
parenthesis.

Give postfix form for A + [ (B + C) + (D + E) * F ] / G

Solution. Evaluation order is
A + { [ (BC +) + (DE +) * F ] / G}
A + { [ (BC +) + (DE + F *] / G}
A + { [ (BC + (DE + F * +] / G}
A + [ BC + DE + F *+ G / ]
ABC + DE + F * + G / + Postfix Form
Algorithm
Step 1: Add “)”to the end of the infix expression
Step 2: Push “(“ on to the stack
Step 3: Repeat until each character in the infix notation is scanned
a. IF a “(“ is encountered, push it on the stack
b. IF an operand is encountered, add it postfix expression.
c. IF a “)” is encountered, then
i. Repeatedly pop from stack and add it to the postfix
expression until a “(“ is encountered.
ii. Discard the “(“. That is, remove the “(“ from stack and do
not add it to the postfix expression
d. IF an operator is encountered, then
i. Repeatedly pop from stack and add each operator (popped
from the stack) to the postfix expression which has the
same precedence or a higher precedence than
ii. Push the operator to the stack
[END OF IF]
Step 4: Repeatedly pop from the stack and add it to the postfix expression
until the stack is empty.
Step 5: EXIT
Example: A – (B / C + (D % E * F) / G)* H
Infix Character Scanned Stack Postfix Expression
(
A ( A
– (– A
( (–( A
B (–( AB
/ (–(/ AB
C (–(/ ABC
+ (–(+ ABC/
( (–(+( ABC/
D (–(+( ABC/D
% (–(+(% ABC/D
E (–(+(% ABC/DE
* (–(+(* A B C / D E%
F (–(+(* A B C / D E %F
) (–(+ A B C / D E %F *
/ (–(+/ A B C / D E %F *
G (–(+/ A B C / D E %F * G
) (– A B C / D E %F * G / +
* (–* A B C / D E %F * G / +
H (–* A B C / D E% F * G / + H
) A B C / D E %F * G / + H * –

C Program to convert infix expression to postfix expression

#include<stdio.h>
#include<ctype.h>
#define SIZE 50
char stack[100];
int top=-1;
char infix[100];
char postfix[100];

void push(char elem)

{
stack[++top]=elem;
}
char pop()
{
return stack[top--];
}
int pr(char symbol)
{
if(symbol=='(')
return 1;
else if(symbol=='+'||symbol=='-')
return 2;
else if(symbol=='*'||symbol=='/'||symbol=='%')
return 3;
else if(symbol=='^')
return 4;
}
void main()
{
char ch,elem;
int i=0,k=0;
printf("Type infix expression: \n");
scanf("%s",infix);
push('(');
while(infix[i]!='\0')
{
ch=infix[i];
if(ch=='(')
push(ch);
else if(isalnum(ch))
{
postfix[k++]=ch;
 }
else if(ch==')')
{
while(stack[top]!='(')
{
postfix[k++]=pop();
}
elem=pop();
}
else
{
while(pr(stack[top])>=pr(ch))
{
postfix[k++]=pop();
}
push(ch);
}
i++;
}
while(stack[top]!='(')
{
postfix[k++]=pop();
}
postfix[k]='\0';
printf("Postfix expression: %s",postfix);
}
Evaluating postfix expression
Using stacks, any postfix expression can be evaluated very easily. Every
character of the postfix expression is scanned from left to right. If the
character encountered is an operand, it is pushed on to the stack. However, if
an operator is encountered, then the top two values are popped from the
stack and the operator is applied on these values. The result is then pushed
on to the stack.
Algorithm
Step 1. Add a right parenthesis “)” at the end of P. [This acts as a sentinel.]
Step 2. Scan P from left to right and repeat Steps 3 and 4 for each element
of P until the sentinel “)” is encountered.
Step 3. If an operand is encountered, put it on STACK.
Step 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 on to the STACK.
Step 5. Result equal to the top element on STACK.
Step 6. Exit
Example: 9 3 4 * 8 + 4 / –
Character Scanned Stack
9 9
3 9, 3
4 9, 3, 4
* 9, 12
8 9, 12, 8
+ 9, 20
4 9, 20, 4
/ 9, 5
– 4

Program to evaluate postfix expression.

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
int s[100];
int top=-1;
void push(int x)
{
s[++top]=x;
}
int pop()
{
return s[top--];
}
int main(int argc, char *argv[]) {
char p[20];
char ch;
int i,num,a,b,res;
printf("\n Enter postfix expression");
scanf("%s",p);
i=0;
while(p[i]!='\0')
{
ch=p[i];
if(isdigit(p[i]))
{
num = p[i]-48;
push(num);
}
else
{
a=pop();
b=pop();
switch(ch)
{
case '+': res = b+a;
 push(res);
break;

case '-': res = b-a;

push(res);
break;

case '*': res = b*a;

push(res);
break;

case '/': res = b/a;

push(res);
break;
case '^': res = pow(b,a);
push(res);
break;
}

}
i++;
}
printf("\n Result is %d",s[top]);
return 0;
}
Recursion
Definition: A recursion is defined as a function that calls itself.
Every recursive solution has two major cases. They are
1. Base case, in which the problem is simple enough to be solved directly
without making any further calls to the same function.
2. Recursive case, in which first the problem at hand is divided into
simpler sub-parts. Second the function calls itself but with sub-parts of
the problem obtained in the first step. Third, the result is obtained by
combining the solutions of simpler sub-parts.
Types of Recursions
1. Direct recursion
2. Indirect recursion
3. Tail recursion

1. Direct recursion: A function is said to be directly recursive if it

explicitly calls itself.
Example:
int Func (int n)
{ if (n == 0)
return n;
else
return (Func (n–1));
}

2. Indirect Recursion: A function is said to be indirectly recursive if it

contains a call to another function which ultimately calls it.
Example:
int Funcl (int n)
{
if (n == 0)
return n;
else
return Func2(n);
}
int Func2(int x)
{
return Func1(x–1);
}

3. Tail Recursion: A recursive function is said to be tail recursive if no

operations are pending to be performed when the recursive function
returns to its caller.
Example:
int Fact(n)
{
return Fact1(n, 1);
}
int Fact1(int n, int res)
{
if (n == 1)
return res;
else
 return Fact1(n–1, n*res);
}
Disadvantages of Recursion
1. It consumes more storage space because the recursive calls along with
automatic variables are stored on the stack.
2. The computer may run out of memory if the recursive calls are not
checked.
3. It is not more efficient in terms of speed and execution time.
4. If proper precautions are not taken, recursion may result in non-
terminating iterations.
5. Recursion is not advocated when the problem can be through iteration.
Recursion may be treated as a software tool to be applied carefully and
selectively.

One of the recursive problems is towers of Hanoi

Towers of Hanoi
Now let us look at the Tower of Hanoi problem and see how we can use recursive
technique to produce a logical and elegant solution.
The initial setup of the problem is shown below. Here three pegs (or towers)
X, Y and Z exists. There will be four different sized disks, say A, B, C and D.
Each disk has a hole in the center so that it can be stacked on any of the pegs.
At the beginning, the disks are stacked on the X peg, that is the largest
sized disk on the bottom and the smallest sized disk on top as shown in Fig.
below.

Initial configuration of Towers of Hanoi

Here we have to transfer all the disks from source peg X to the destination
peg Z by using an intermediate peg Y. Following are the rules to be followed
during transfer:
1. Transferring the disks from the source peg to the destination peg such that
at any point of transformation no large size disk is placed on the smaller
one.
2. Only one disk may be moved at a time.
3. Each disk must be stacked on any one of the pegs.

Example: Towers of Hanoi Solution

Algorithm
• Base case: if n=1
• Move the ring from A to C using B as spare
• Recursive case:
• Move n – 1 rings from A to B using C as spare
• Move the one ring left on A to C using B as spare
• Move n – 1 rings from B to C using A as spare
Towers of Hanoi Program
#include <stdio.h>
void towerOfHanoi(int n, char from_rod, char to_rod, char aux_rod)
{
if (n == 1)
{
printf("\n Move disk 1 from rod %c to rod %c", from_rod, to_rod);
}
else
{
towerOfHanoi(n-1, from_rod, aux_rod, to_rod);
printf("\n Move disk %d from rod %c to rod %c", n, from_rod,
to_rod);
towerOfHanoi(n-1, aux_rod, to_rod, from_rod);
}
}
int main()
{
int n = 4; // Number of disks
towerOfHanoi(n, 'A', 'C', 'B'); // A, B and C are names of rods
return 0;
}
Important Question:
Short Answer questions
1. Define time and space complexity.
2. What are the asymptotic notations.
3. Define BigO, Omega and Theta notations.
4. What is time-space trade-off?
5. Explain types of time-space trade-off.
6. What are the advantages and disadvantages of linear and Binary
search.
7. What are the time complexities of linear and binary search.
8. Define stack.
9. Define ADT
10. Give stack ADT.
11. What are the applications of stack.
12. What is recursion? Explain its disadvantages.
13. explain recursion types.
14. What is infix, prefix and postfix expression.

Long answer questions

1. Define data structure. Explain different types of data structure.
1. Explain Asymptotic notations.
2. Explain types of time space trade-off.
3. Explain linear search with an example.
4. Explain binary search with an example.
5. Write a c program to implement stack using arrays.
6. Convert the given infix expression A+B^C+(D*E/F)*G into its postfix
expression, and evaluate the same using stack. Here A=3, B=5, C=2, D=7,
E=4, F=1, G=8.
7. Explain the procedure to evaluate postfix expression. Evaluate the
following postfix expression 7 3 4 + - 2 4 5 / + * 6 / 7 + ?.
8. Write a c program to implement towers of Hanoi.
9. Write an algorithm / program to convert infix expression to postfix
expression.
10. Write an algorithm/program to evaluate postfix expression.
11. Convert following expression X+( Y * Z) – (( N * M +O) /P) in to post
form.
12. Explain the evaluation of prefix expression. Find the equivalent prefix
of 8 6 3 + * 1 2 3 -/-
13. Convert following infix expression into postfix expression: A+B^(C+D)-
E*F+G.
14. Transform the expression into its equivalent post fix expression:
A*(B+D)/E-F*(G+H/K).
 UNIT - II
QUEUE
Definition: A Queue is a linear data structure in which insertion operations
are performed at rear end and deletion operations are performed front end.
In queue data structure, the insertion and deletion operations are performed
based on FIFO (First In First Out) principle. Which means that the element
inserted first is to be removed first. Hence it is called First in First Out(FIFO) data
structure.

Uses of Queue:
1. Railway reservation
2. Cinema ticket booking
3. Operating systems
QUEUE ADT
• enqueue() – Insert an element at the end of the queue.
• dequeue() – Remove and return the first element of the queue, if the
queue is not empty.
• peek() – Return the element of the queue without removing it, if the
queue is not empty.
• size() – Return the number of elements in the queue.
• isEmpty() – Return true if the queue is empty, otherwise return false.
• isFull() – Return true if the queue is full, otherwise return false.
Types of Queues
1. Simple queue
2. Circular queue
3. Double ended queue
Simple Queue
Basically, queue has two operations. 1. Enqueue 2. Dequeue
1. Enqueue: Inserting an element into the queue is called enqueue.
2. Dequeue: Deleting / removing an element from the queue is called
dequeue.
Enqueue
 Step 1 - Check whether queue is FULL. (rear == SIZE-1)
 Step 2 - If it is FULL, then display "Queue is FULL!!! Insertion is not
possible!!!" and terminate the function.
 Step 3 - If it is NOT FULL, then increment rear value by one (rear++)
and set queue[rear] = value.
Dequeue
 Step 1 - Check whether queue is EMPTY. (front = rear=-1)
 Step 2 - If it is EMPTY, then display "Queue is EMPTY!!! Deletion is not
possible!!!" and terminate the function.
 Step 3 - If it is NOT EMPTY, then increment the front value by one (front
++). Then display queue[front] as deleted element. Then check whether
both front and rear are equal (front == rear), if it TRUE, then set both
front and rear to '-1' (front = rear = -1).
Implementing queue using arrays
#include <stdio.h>
#include <stdlib.h>
#define size 5
int Q[size];
int f=-1,r=-1;

void enqueue(int x)
{
if(r==size-1)
{
printf("\n overflow");
}
else if(r==-1&&f==-1)
{
r = r+1;
f=f+1;
Q[r]=x;
}
else
{
 r=r+1;
Q[r]=x;
}

void dequeue()
{

if(f==-1)
{
printf("underflow\n");
}
else if(f==r)
{
printf("\n The deleted element is %d",Q[f]);
r=-1;
f=-1;
}
else
{
printf("\n The deleted element is %d",Q[f]);
f=f+1;
}

void peek()
{

if(f==-1)
{
printf("underflow\n");
return 0;
}
else
{
printf("\n Peek element is %d",Q[f]);

void display()
{
int i;
if(r==-1)
{
printf("\n Queue is empty\n");
 }
else
{
for(i=f;i<=r;i++)
{
printf("%d\n",Q[i]);
}
}
}

int main(int argc, char *argv[]) {

int ch,x;

while(1)
{
printf("\n 1. Insert");
printf("\n 2. Delete");
printf("\n 3. Display ");
printf("\n 4. Peek ");
printf("\n 5. exit");
printf("\n Enter your choice\n");
scanf("%d",&ch);
switch(ch)
{
case 1: printf("\n insert a value\n");
scanf("%d",&x);
enqueue(x);
break;
case 2: dequeue();
break;
case 3: display();
break;
case 4: peek();
break;
case 5: exit(0);
default: printf("\n Enter correct choice\n");
}
}

return 0;
}
Drawback of Simple queue

Let us consider the following scenario.

The above situation says that queue is full, and we cannot insert an element
into the queue because rear is pointing to last position. In the above situation
even though we have empty position in the queue, but we cannot use of them
to insert the new element.
To overcome the above the problem we use circular queue.

Circular Queue

Circular queue is a linear data structure in which operations are performed based
on FIFO ( FIRST IN FIRST OUT) principle and the last position is connected back
to the first position to make a circle.

Graphical representation of a circular queue is as follows.

Circular Queue Insertion

Step 1: IF (REAR+1)%MAX = FRONT Write " OVERFLOW “ Goto step 4

Step 2: IF FRONT = -1 and REAR = -1 then SET FRONT = REAR = 0
ELSE IF REAR = MAX - 1 and FRONT ! = 0 then SET REAR = 0
 ELSE SET REAR = (REAR + 1) % MAX
Step 3: SET QUEUE[REAR] = VAL
Step 4: EXIT
Circular Queue Deletion

 Step 1: IF FRONT = -1 Write " UNDERFLOW “ Goto Step 4

 Step 2: SET VAL = QUEUE[FRONT]
 Step 3: IF FRONT = REAR then SET FRONT = REAR = -1
ELSE IF FRONT = MAX -1 then SET FRONT = 0
ELSE SET FRONT = FRONT + 1
 Step 4: EXIT

Circular queue Operations

Implementing Circular queue using arrays
#include <stdio.h>
#include <stdlib.h>
#define size 5
int CQ[size];
int front=-1;
int rear=-1;

void enqueue(int x)
{
if((rear+1)%size== front)
{
printf("\n Overflow");
}
else if(front==-1&& rear==-1)
{
front =front+1;
rear = rear +1;
CQ[rear]= x;
}
else
{
rear = (rear + 1)%size;
CQ[rear] = x;
}

int dequeue( )
{
int x;
if(front==-1 && rear == -1)
{
printf("\n Underflow \n");
return 0;
}
else if(front == rear)
{
x = CQ[front];
front =-1;
rear = -1;
}
else
{
x = CQ[front];
front = (front+1)%size;

}
 return x;
}
void display()
{
int i;

if(front ==-1 && rear == -1)

{
printf("\n Queue is empty\n");
}
else
{

for(i=front; i!=rear;i=(i+1)%size)
{
printf("%d\n",CQ[i]);
}
printf("%d\n",CQ[i]);
}

int main(int argc, char *argv[]) {

int ch,x;
while(1)
{

printf("\n 1. Insert\n2. Delete\n3. Display\n4. Exit\nEnter

your choice\n");
scanf("%d",&ch);
switch(ch)
{
case 1: printf("\n Enter the number\n");
scanf("%d",&x);
enqueue(x);
break;
case 2: x = dequeue();
printf("\n Deleted element is %d\n",x);
break;
case 3: display();
break;
case 4: exit(0);
default: printf("\n Enter correct choice\n");
}
}
return 0;
}
The drawback of circular queue is we cannot insert and delete the elements
from both the ends. It is overcome with the deque (double ended queue).

Double ended queue (Deque)

Definition: Double ended queue is also a queue data structure, in which

deletion and insertions are performed at the both the ends (front and rear).

Graphical representation of Deque is shown below.

Double ended queue is represented in two ways. They are.

1. input restricted deque.
2. output restricted deque

Input restricted deque: In input restricted dequeue insertion is performed

at rear end but deletion is performed at both the ends (front and rear).

Output restricted deque: In output restricted deque, deletion is performed

at front end, but insertion is performed at both the ends (front and rear).

Operations on deque:

1. insertFront(): Insert an element at the front of Deque.

2. insertRear(): Insert an element at the rear of Deque.
3. deleteFront(): Deletes an element from the front of Deque.
4. deleteRear(): Deletes an element from the rear of Deque.

Implementing deque (double ended queue) using arrays

#include <stdio.h>
#include <stdlib.h>
#define size 10
int Q[size];
int f=-1,r=-1;

void insert_rear(int x)
{
if((r+1)%size==f)
 {
printf("\n Overflow");
}
else if(f==-1)
{
f=0;
r=0;
Q[r]=x;
}
else
{
r=(r+1)%size;
Q[r]=x;
}
}

void insert_front(int x)
{
if((r+1)%size==f)
{
printf("\n Overflow");
}
else if(f==0)
{
f=size-1;
Q[f] = x;
}
else
{
f=f-1;
Q[f]=x;
}
}

int delete_front()
{
int x;

if(f==-1)
{
printf("\n Underflow\n");
return 0;
}
else if(f==r)
{
printf(“\n Deleted element is %d”,Q[f]);
f=-1;
r=-1;
}
 else
{
printf(“\n Deleted element is %d”,Q[f]);
f = (f+1)%size;

}
}

int delete_rear()
{
int x;
if(f==-1)
{
printf("\n Underflow\n");
return 0;
}
else if(f==r)
{
Printf(“\n Deleted element is %d”,Q[r]);
f=-1;
r=-1;
}
else
{
Printf(“\n Deleted element is %d”,Q[r]);
if(r==0)
r=size-1;
else
r = r-1;
}
}

void display()
{
int i;
if(f==-1)
{
printf("\n Queue is empty\n");
}
else
{
for(i=f;i!=r;i=(i+1)%size)
{
printf("%d\n",Q[i]);
}
printf("%d\n",Q[i]);
}
}
int main(int argc, char *argv[]) {
int ch,x;
while(1)
{
printf("\n 1. Insert rear\n2. Insert front \n 3. delete front \n4.
delete rear\n5. display\n6. exit\n Enter your choice\n");
scanf("%d",&ch);
switch(ch)
{
case 1: printf("\n Enter your choice\n");
scanf("%d",&x);
insert_rear(x);
break;
case 2: printf("\n Enter your choice\n");
scanf("%d",&x);
insert_front(x);
break;\
case 3: delete_front();
break;
case 4: delete_rear();
break;
case 5: display();
break;
case 6: exit(0);
default: printf("\n Enter correct choice\n");
}
}
return 0;
}

Applications of Queue

1. Task Scheduling: Queues can be used to schedule tasks based on priority

or the order in which they were received.
2. Resource Allocation: Queues can be used to manage and allocate
resources, such as printers or CPU processing time.
3. Batch Processing: Queues can be used to handle batch processing jobs,
such as data analysis or image rendering.
4. Message Buffering: Queues can be used to buffer messages in
communication systems, such as message queues in messaging systems
or buffers in computer networks.
5. Event Handling: Queues can be used to handle events in event-driven
systems, such as GUI applications or simulation systems.
6. Traffic Management: Queues can be used to manage traffic flow in
transportation systems, such as airport control systems or road networks.
7. Operating systems: Operating systems often use queues to manage
processes and resources. For example, a process scheduler might use a
queue to manage the order in which processes are executed .
Important Questions:

Short Answer questions

1. Define queue, circular queue, deque, input restricted deque, and
output restricted deque.
2. What is the drawback of a simple queue?
3. All Queues – Full and empty conditions.

Long Answer questions

1. Write an algorithm for enqueue and dequeue.

2. Implement queue using arrays.
3. Implement circular queue using arrays.
4. Implement deque using arrays.
Practice questions

1. Draw the queue structure in each case when the following operations are
performed on an empty queue.

(a) Add A, B, C, D, E, F (b) Delete two letters

(c) Add G (d) Add H
(e) Delete four letters (f) Add I

2. Consider the queue given below which has FRONT = 1 and REAR = 5.

Now perform the following operations on the queue:

(a) Add F (b) Delete two letters
(c) Add G (d) Add H
(e) Delete four letters (f) Add I

Multiple choice questions

1. A line in a grocery store represents a

(a) Stack (b) Queue (c) Linked List (d) Array

2. In a queue, insertion is done at

(a) Rear (b) Front (c) Back (d) Top

3. The function that deletes values from a queue is called

(a) enqueue (b) dequeue (c) pop (d) peek

4. Typical time requirement for operations on queues is

(a) O(1) (b) O(n) (c) O(log n) (d) O(n2 )
5. The circular queue will be full only when
(a) FRONT = MAX –1 and REAR = Max –1
(b) FRONT = 0 and REAR = Max –1
(c) FRONT = MAX –1 and REAR = 0
(d) FRONT = 0 and REAR = 0
Linked Lists
An array is a linear collection of data elements in which the elements are
stored in consecutive memory locations. While declaring arrays, we have to
specify the size of the array, which will restrict the number of elements that
the array can store. But what if we are not sure of the number of elements
in advance? Moreover, to make efficient use of memory, the elements must
be stored randomly at any location rather than in consecutive locations. So, there
must be a data structure that removes the restrictions on the maximum
number of elements and the storage condition to write efficient programs. So,
there must be a data structure that removes the restrictions on the maximum
number of elements and the storage condition to write efficient programs.

Linked list is a data structure that is free from the aforementioned restrictions.
A linked list does not store its elements in consecutive memory locations and the
user can add any number of elements to it.

Drawback of Linked list

Unlike an array, a linked list does not allow random access of data.
Elements in a linked list can be accessed only in a sequential manner.

Definition: A linked list is an ordered collection of finite, homogeneous data

elements called nodes where the linear order is maintained by means of links
or pointers.

In a linked list, every node contains a pointer to another node which is of the
same type, hence it is also called a self-referential data type.

Node structure

struct node

Int data;

struct node *next;

}
Visual representation of a Node

Representation of a Linked list in memory

There are two ways to represent a linked list in memory:

1. Static representation using array
2. Dynamic representation using free pool of storage

Static representation
In static representation of a single linked list, two arrays are maintained: one
array for data and the other for links. The linked list and its static representation
using arrays are shown in figures.

Linked list with six nodes.

Two parallel arrays of equal size are allocated which should be sufficient to store
the entire linked list. Nevertheless, this contradicts the idea of the linked list
(that is non-contagious location of elements). Hence it is not an efficient method.
 Linked list representation using arrays

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 (which is nothing but a collection of free
memory spaces) and a memory manager (a program, in fact). During the
creation of a linked list, whenever a node is required, the request is placed to the
memory manager; the memory manager will then search the memory bank for
the block requested and, if found, grants the desired block to the caller. Again,
there is also another program called the garbage collector; it plays whenever
a node is no more in use; it returns the unused node to the memory bank.
Operations on a single linked list
1. Inserting a node at the beginning of a single linked list
2. Inserting a node at the end of the single linked list
3. Inserting a node at any position
4. Deleting a node from the beginning of the single linked list
5. Deleting a node from the end of the single linked list
6. Deleting a node from any position in the linked list.
7. Traversing linked list (display linked list elements).
8. Searching a node in the linked list
9. Sorting the list elements
 10. Reverse linked list elements.

Global declarations
typedef struct linkedlist
{
int data;
struct linkedlist *next;
}node;
node *head=NULL;
1. Inserting a mode at the beginning of the single linked list
Code:
void insert_begin()
{
int x;
node *temp;
temp=(node*)malloc(sizeof(node));
if(temp==NULL)
{
printf("\n Insufficient Memory\n");
}
else
{
printf("\n Enter a value\n");
scanf("%d",&x);
temp->data = x;
temp->next = NULL;
if(head==NULL)
{
head=temp;
}
else
 {
temp->next = head;
head=temp;
}
}
}
2. Inserting a node at the end of the single linked list
void insert_end()
{
int x;
node *temp,*temp1;
temp = (node*)malloc(sizeof(node));
if(temp==NULL)
{
printf("\n Insufficient Memory\n");
}
else
{
printf("\n Enter a value\n");
scanf("%d",&x);
temp->data=x;
temp->next=NULL;
if(head==NULL)
{
head=temp;
}
else
{
for(temp1=head;temp1->next!=NULL;temp1=temp1-
>next);
temp1->next=temp;
}
 }
}
3. Inserting a node at any position in the single linked list
void insert_pos()
{
int x,p,n; //p represents the position and n represents no of nodes
in the linked list
node *temp,*temp1;
printf("\n Enter position:");
scanf("%d",&p);
for(temp1=head,n=1;temp1->next!=NULL;temp1=temp1->next,n++);
if(p==1)
{
insert_begin();
}
else if(p==n+1)
{
insert_end();
}
else if(p > n+1||p<1)
{
printf("\n Insertion is not possible\n");
}
else
{
temp=(node*)malloc(sizeof(node));

if(temp==NULL)
{
printf("\n Insufficient Memory\n");

}
 else
{
for(temp1=head,n=1;n<p-1;n++,temp1=temp1->next);
printf("\n Enter a value\n");
scanf("%d",&x);
temp->data = x;
//temp->next = NULL;
temp->next = temp1->next;
temp1->next = temp;
}
}
}

4. Deleting a node from the beginning of the single linked list

void delete_begin()
{
node *temp;
if(head==NULL)
{
printf("\n Linked List is empty\n");
}
else
{
temp=head;
printf("\n Deleted node is %d \n",temp->data);
head=head->next;
free(temp);
}
}
5. Deleting a node from the end of the single linked list
void delete_end()
{
node *temp,*temp1;

if(head==NULL)
{
printf("\n List is empty\n");
}
else
{
if(head->next==NULL)
{
temp=head;
printf("\n Deleted node is %d\n",temp->data);
head=NULL;
free(temp);
}
else
{
for(temp1=head;temp1->next->next!=NULL;temp1=temp1-
>next);
temp=temp1->next;
temp1->next=NULL;
printf("\n Deleted node is %d\n",temp->data);
free(temp);
}
}

}
6. Deleting a node from any position of the linked list
void delete_pos()
{
node *temp,*temp1;
int i, pos, count=0;
printf("\n Enter position:");
scanf("%d",&pos);
for(temp1=head;temp1!=NULL;temp1=temp1->next, count++);
if(pos==1)
{
delete_begin();
}
else if(pos==count)
{
delete_end();
}
else if(pos<1||pos>count)
{
printf("\n Deletion is not possible");
}
else
{
for(i=2,temp1=head; i<pos && i<count;i++,temp1=temp1->next);
temp=temp1->next;
temp1->next = temp->next;
printf("\n Deleted node is %d \n", temp->data);
free(temp);
}
}
7. Traversing linked list (display linked list elements)
void display()
{
node *temp;
if(head==NULL)
{
printf("\n List is empty\n");
}
else
{
temp = head;
for(temp=head;temp!=NULL;temp=temp->next)
{
printf("%d\n",temp->data);
}
}
}
8. Searching a node in the linked list
void search()
{
int key,found=0;
node *temp;
printf("\n Enter the key elements:");
scanf("%d",&key);
temp=head;
if(temp==NULL)
{
printf("\n List is empty");
}
else
 {
for(;temp!=NULL; temp=temp->next)
{
if(key==temp->data)
{
found=1;
break;
}
}
if(found==1)
{
printf("\n %d is found in the list",key);
}
else
{
printf("\n %d is not found in the list",key);
}
}
}

9. Sorting the list elements

void sort()
{
int x;
node *i,*j;
i=head;
while(i!=NULL)
{
j=i->next;
while(j!=NULL)
{
 if(i->data>j->data)
{
x=i->data;
i->data=j->data;
j->data=x;
}
j=j->next;
}
i=i->next;
}
}
10. Reverse linked list elements
void reverse()
{
node *curr,*prev,*next1;
curr=head;
prev=next1=NULL;
while(curr!=NULL)
{
next1=curr->next;
curr->next=prev;
prev=curr;
curr=next1;
}
head=prev;
}
The corresponding main program for the above functions is as follows.
Main program
typedef struct list
{
int data;
struct list *next;
}node;
node *head=NULL;
void main()
{
int x;
while(1)
{
printf("[Link] begin\[Link] End \n 3. Insert position\n 4. Delete
begin \n 5. Insert end\n 6. Insert position \n 7. Search\n 8.
Sort\[Link]\[Link]\[Link]\n");
printf("Enter your choice\n");
scanf("%d",&x);
switch(x)
{
case 1:insert_begin(); break;
case 2: insert_begin();break;
case 3: insert_pos(); break;
case 4: delete_begin(); break;
case 5: delete_end(); break;
case 6: delete_pos(); break;
case 7: search(); break;
case 8: sort();break;
case 9: reverse();break;
case 10: display();break;
case 11: exit(0);
 default: printf("Enter correct choice\n");
}
}
}
C program to create a linked list.
#include<stdio.h>
#include<stdlib.h>
typedef struct linkedlist
{
int data;
struct linkedlist *next;
}node;
node *head=NULL;
void create()
{
node *temp;
char ch='y';
int x;
while(ch=='y')
{
temp=(node *)malloc(sizeof(node));
if(temp!=NULL)
{
printf("Enter a value\n");
scanf("%d",&x);
temp->data=x;
temp->next=NULL;
if(head==NULL)
{
head=temp;
 }
else
{
temp->next=head;
head=temp;
}
}
printf("Do you want to continue (y/n)\n");
fflush(stdin);
scanf("%c",&ch);
}
}
void display()
{
node *temp;
if(head==NULL)
{
printf("List is empty\n");
}
else
{
for(temp=head;temp!=NULL;temp=temp->next)
{
printf("%d\n",temp->data);
}
}
}
void main()
{
int x;
 while(1)
{
printf("[Link] linked list \[Link]\[Link]\n");

printf("Enter your choice\n");

scanf("%d",&x);
switch(x)
{
case 1: create();break;
case 2: display();break;
case 3: exit(0);
default:printf("Enter correct choice\n");
}
}
}
C Program for merging two linked lists.

C Program to implement stack using linked list

Push operation: The push operation is used to insert an element into the stack.
The new element is added at the topmost position of the stack. Consider the
linked stack shown in Figure.

To insert an element with value 9, we first check if TOP=NULL. If this is the

case, then we allocate memory for a new node, store the value in its DATA part
and NULL in its NEXT part. The new node will then be called TOP. However, if
TOP!=NULL, then we insert the new node at the beginning of the linked stack
and name this new node as TOP. Thus, the updated stack becomes as shown
in figure.
Algorithm
Step 1: Allocate memory for the new node and name it as NEW_NODE
Step 2: SET NEW_NODE DATA = VAL
Step 3: IF TOP = NULL SET TOP = ELSE SET TOP = [END OF IF]
Step 4: END
C Code: (which is similar to inserting a node at the beginning of the single
linked list).
void insert_begin()
{
int x;
node *temp;
temp=(node*)malloc(sizeof(node));
if(temp==NULL)
{
printf("\n Insufficient Memory\n");
}
else
{
printf("\n Enter a value\n");
scanf("%d",&x);
temp->data = x;
temp->next = NULL;
if(top==NULL)
{
top=temp;
}
else
{
temp->next = top;
top=temp;
}
 }
}
POP Operation: The pop operation is used to delete the topmost element
from a stack. However, before deleting the value, we must first check if
TOP=NULL, because if this is the case, then it means that the stack is empty
and no more deletions can be done. If an attempt is made to delete a value
from a stack that is already empty, an UNDERFLOW message is printed.
Consider the stack shown in Figure.

In case TOP!=NULL, then we will delete the node pointed by TOP, and make
TOP point to the second element of the linked stack. Thus, the updated
stack becomes as shown in Figure.

Algorithm:
Step 1: IF TOP = NULL PRINT UNDERFLOW [END OF IF]
Step 2: SET PTR = TOP
Step 3: SET TOP = TOP NEXT
Step 4: FREE PTR
Step 5: END
C Code: (which is similar to deleting a node from the beginning of the single linked
list).
void delete_begin()
{
node *temp;
if(top ==NULL)
{
printf("\n Linked List is empty\n");
}
else
{
temp= top;
 printf("\n Deleted node is %d \n",temp->data);
top=head->next;
free(temp);
}
}
C Program to implement stack using linked list
#include<stdio.h>
#include<stdlib.h>
typedef struct linkedlist
{
int data;
struct linkedlist *next;
}node;
node *top=NULL;
void push()
{
int x;
node *temp;
temp=(node*)malloc(sizeof(node));
if(temp==NULL)
{
printf("\n Insufficient Memory\n");
}
else
{
printf("\n Enter a value\n");
scanf("%d",&x);
temp->data = x;
temp->next = NULL;
if(top==NULL)
{
 top=temp;

}
else
{
temp->next = top;
top=temp;

}
}
}

void pop()
{
node *temp;
if(top ==NULL)
{
printf("\n Linked List is empty\n");
}
else
{
temp= top;
printf("\n Deleted node is %d \n",temp->data);
top=top->next;
free(temp);
}
}

void display()
{
node *temp;
if(top ==NULL)
{
printf("List is empty\n");
 }
else
{
for(temp= top;temp!=NULL;temp=temp->next)
{
printf("%d\n",temp->data);
}
}
}
void main()
{
int x;
while(1)
{
printf("[Link]\[Link]\[Link]\[Link]\n");
printf("Enter your choice\n");
scanf("%d",&x);
switch(x)
{
case 1:push();break;
case 2:pop();break;
case 3:display();break;
case 4:exit(0);
default:printf("Enter correct choice\n");
}
}
}
Queue implementation using linked list
A queue has basically two operations 1. Enqueue 2. Dequeue
Enqueue: inserting an element into the queue
Dequeue: Deleting an element from the queue.
Enqueue:
The enqueue operation is used to insert an element into a queue. The new
element is added as the last element of the queue. Consider the linked
queue shown in Figure.

To insert an element with value 9, we first check if FRONT=NULL. If the

condition holds, then the queue is empty. So, we allocate memory for a new
node, store the value in its data part and NULL in its next part. The new node
will then be called both FRONT and rear. However, if FRONT != NULL, then we
will insert the new node at the rear end of the linked queue and name this
new node as rear. Thus, the updated queue becomes as shown in Figure.

Algorithm
Step 1: Allocate memory for the new node and name it as PTR
Step 2: SET PTR DATA = VAL
Step 3: IF FRONT = NULL
SET FRONT = REAR = PTR
SET FRONT->NEXT = REAR->NEXT = NULL
ELSE
SET REAR->NEXT = PTR
SET REAR = PTR
SET REAR->NEXT = NULL
[END OF IF]
Step 4: END
Dequeue: The delete operation is used to delete the element that is first
inserted in a queue, i.e., the element whose address is stored in FRONT.
However, before deleting the value, we must first check if FRONT=NULL
because if this is the case, then the queue is empty and no more deletions can
be done. If an attempt is made to delete a value from a queue that is already
empty, an underflow message is printed. Consider the queue shown in Figure.

To delete an element, we first check if FRONT=NULL. If the condition is false,

then we delete the first node pointed by FRONT. The FRONT will now point
to the second element of the linked queue. Thus, the updated queue becomes
as shown in Figure.

Algorithm
Step 1: IF FRONT = NULL
Write “Underflow”
Go to Step 5
[END OF IF]
Step 2: SET PTR = FRONT
Step 3: SET FRONT = FRONT NEXT
Step 4: FREE PTR
Step 5: END
C Program to implement queue using linked list
//Queue using linked list
#include<stdio.h>
#include<stdlib.h>

typedef struct linkedlist

{
int data;
struct linkedlist *next;
} node;

node *front = NULL, *rear = NULL;

void enqueue()
{
node *temp;
int x;
temp = (node *)malloc(sizeof(node));
if(temp==NULL)
{
printf("Insufficient Memory\n");
}
else
{
printf("Enter a number : ");
scanf("%d", &x);
temp->data = x;
temp->next = NULL;
if(rear==NULL)
{
front = temp;
rear = temp;
}
else
{
rear->next = temp;
rear = temp;
}
}
}
void dequeue()
{
node *temp;
if(front==NULL)
{
printf("Queue Underflow\n");
}
else
{
temp = front;
if(front->next==NULL) //Checking for one node
{
rear = NULL;
}
front = temp->next;
printf("Deleted %d\n", temp->data);
free(temp);
}
}

void display()
{
node *temp;
if(rear==NULL)
{
printf("Queue is empty\n");
}
else
{
 printf("Queue elements are");
for(temp = front; temp!=rear; temp = temp->next)
{
printf("\n%d", temp->data);
}
printf("\n%d\n", rear->data);
}
}

void main()
{
int ch;
while(1)
{
printf("\nOperations\n1. Enqueue\n2. Dequeue\n3. Display\n4.
Exit\n");
printf("\nEnter your choice : ");
scanf("%d", &ch);
switch(ch)
{
case 1: enqueue();
break;
case 2: dequeue();
break;
case 3: display();
break;
case 4: printf("\n");
exit(0);
default: printf("\nInvalid Choice\n");
}
 }
}

Drawback of single linked list

Using single linked list, we cannot traverse and access the previous nodes.
This can be overcome through circular linked list.

Circular linked list:

Definition: In circular linked list, every node points to the next node and the
last node of the linked list points to the first node.

Note: This feature makes it circular in nature. It is essential to know that the
circular linked lists have no end, and we need to be careful while traversing
the linked list.
Operations performed on a circular linked list are
1. Inserting a node at the beginning of a circular linked list
2. Inserting a node at the end of the circular linked list
3. Inserting a node at any position in the circular linked list
4. Deleting a node from the beginning of the circular linked list
5. Deleting a node from the end of the circular linked list
6. Deleting a node from any position in the circular linked list.
7. Traversing linked list (display linked list elements).

C Program to implement circular linked list

//Circular Linked List
#include<stdio.h>
#include<stdlib.h>

typedef struct linkedlist

{
int data;
struct linkedlist *next;
} node;

node *head = NULL;

void insert_begin()
{
node *temp, *temp1;
int x;
temp = (node *)malloc(sizeof(node));
if(temp==NULL)
{
printf("Insufficient Memory\n");
}
else
{
printf("Enter a number : ");
scanf("%d", &x);
temp->data = x;
temp->next = NULL;
if(head==NULL)
{
head = temp;
head->next = head;
}
else
{
temp->next = head;
for(temp1=head;temp1->next!=head;temp1=temp1->next);
temp1->next = temp;
head = temp;
 }
}
}

void insert_end()
{
node *temp, *temp1;
int x;
temp = (node *)malloc(sizeof(node));
if(temp==NULL)
{
printf("Insufficient Memory\n");
}
else
{
printf("Enter a number : ");
scanf("%d", &x);
temp->data = x;
temp->next = NULL;
if(head==NULL)
{
head = temp;
head->next = head;
}
else
{
temp->next = head;
for(temp1=head;temp1->next!=head;temp1=temp1->next);
temp1->next = temp;
}
 }
}

void insert_pos()
{
node *temp, *temp1;
int x, pos, count, i;
printf("Enter a position : ");
scanf("%d", &pos);
for(count=1, temp1 = head; temp1->next!=head; temp1=temp1->next,count++);
if(head==NULL)
{
count--;
}
if(pos<1||pos>count+1)
{
printf("Insertion not possible\n");
}
else if(pos==1)
{
insert_begin();
}
else if(pos==count+1)
{
insert_end();
}
else
{
temp = (node *)malloc(sizeof(node));
 if(temp==NULL)
{
printf("Insufficient Memory\n");
}
else
{
printf("Enter a number : ");
scanf("%d", &x);
temp->data = x;
temp->next = NULL;
temp1 = head;
i = 2;
while(i<pos)
{
temp1 = temp1->next;
i++;
}
temp->next = temp1->next;
temp1->next = temp;
}
}
}

void delete_begin()
{
node *temp, *temp1;
if(head==NULL)
{
printf("Underflow\n");
}
 else if(head->next==head)
{
temp = head;
printf("Deleted %d\n", temp->data);
head = NULL;
free(temp);
}
else
{
for(temp1=head;temp1->next!=head;temp1=temp1->next);
temp = head;
head = head->next;
temp1->next = head;
printf("Deleted %d\n", temp->data);
free(temp);
}
}

void delete_end()
{
node *temp, *temp1;
if(head==NULL)
{
printf("Underflow\n");
}
else if(head->next==head)
{
temp = head;
printf("Deleted %d\n", temp->data);
head = NULL;
 free(temp);
}
else
{
for(temp1=head;(temp1->next)->next!=head;temp1=temp1->next);
temp = temp1->next;
temp1->next = head;
printf("Deleted %d\n", temp->data);
free(temp);
}
}

void delete_pos()
{
node *temp, *temp1;
int count, pos, i;
if(head==NULL)
{
printf("Underflow\n");
}
else
{
for(temp=head,count=1;temp->next!=head;temp=temp->next,count++);
printf("Enter a position : ");
scanf("%d", &pos);
if(pos<1||pos>count)
{
printf("Deletion is not possible\n");
}
else if(pos==1)
 {
delete_begin();
}
else if(pos==count)
{
delete_end();
}
else
{
temp = head;
i = 2;
while(i<pos)
{
temp = temp->next;
i++;
}
temp1 = temp->next;
temp->next = temp1->next;
printf("Deleted %d\n", temp1->data);
free(temp1);
}
}
}

void display()
{
node *temp;
if(head==NULL)
{
printf("The List is empty\n");
 }
else
{
printf("The list elements are\n");
for(temp=head;temp->next!=head;temp=temp->next)
{
printf("%d\n", temp->data);
}
printf("%d\n", temp->data);
}
}

void search()
{
node *temp;
int key, f=0;
if(head==NULL)
{
printf("List is empty\n");
}
else
{
printf("Enter key : ");
scanf("%d", &key);
temp = head;
while(temp->next!=head)
{
if(temp->data==key)
{
f=1;
 break;
}
temp = temp->next;
}
if(temp->data==key)
{
f=1;
}
if(f==1)
{
printf("Search is successful\n");
}
else
{
printf("Search is unsuccessful\n");
}
}
}

void main()
{
int ch;
while(1)
{
printf("\nOperations\n");
printf("1. Insert Begin\n2. Insert End\n3. Insert Position\n");
printf("4. Delete Begin\n5. Delete End\n6. Delete Position\n");
printf("7. Display\n8. Search\n9. Exit\n");
printf("\nEnter your choice : ");
scanf("%d", &ch);
 switch(ch)
{
case 1: insert_begin();
break;
case 2: insert_end();
break;
case 3: insert_pos();
break;
case 4: delete_begin();
break;
case 5: delete_end();
break;
case 6: delete_pos();
break;
case 7: display();
break;
case 8: search();
break;
case 9: printf("\n");
exit(0);
default: printf("Invalid Choice\n");
}
}
}

Drawback of circular linked list: The main drawback of circular linked list
is it cannot traverse in a reverse direction. To overcome this drawback
through the double linked list.
Double linked list
A doubly linked list or a two-way linked list is a more complex type of linked list
which contains a pointer to the next as well as the previous node in the sequence.
Therefore, it consists of three parts—data, a pointer to the next node, and a
pointer to the previous node as shown in Figure.

In C, the structure of a doubly linked list can be given as,

struct node
{
struct node *prev;
int data;
struct node *next;
};
The PREV field of the first node and the NEXT field of the last node will contain
NULL. The PREV field is used to store the address of the preceding node,
which enables us to traverse the list in the backward direction.
Double linked list operations
1. Inserting a node at the beginning of a double linked list
2. Inserting a node at the end of the double linked list
3. Inserting a node at any position in the double linked list
4. Deleting a node from the beginning of the double r linked list
5. Deleting a node from the end of the double linked list
6. Deleting a node from any position in the double linked list.
7. Traversing linked list (display linked list elements).
C Program to implement double linked list
#include <stdio.h>
#include <stdlib.h>
typedef struct node
{
int data;
struct node *next;
struct node *prev;
}dnode;
dnode *head=NULL;

void insert_begin()
{
int x;
dnode *temp;
temp=(dnode*)malloc(sizeof(dnode));
if(temp==NULL)
{
printf("\n Insufficient memory");
}
else
{
printf("\n Enter a value:");
scanf("%d",&x);
temp->data=x;
temp->next=NULL;
temp->prev=NULL;
if(head==NULL)
{
head=temp;
}
else
{
temp->next=head;
head->prev=temp;
head = temp;
}
}
}
void insert_end()
{
int x;
dnode *temp,*last;
temp=(dnode*)malloc(sizeof(dnode));

if(temp==NULL)
{
printf("\n Insufficient memory");
}
else
{
printf("\n Enter a value:");
scanf("%d",&x);
temp->data=x;
temp->next=NULL;
temp->prev=NULL;

if(head==NULL)
{
head=temp;
}
else
{
for(last=head;last->next!=NULL;last=last->next);
last->next=temp;
temp->prev=last;
}
}
}

void insert_pos()
{
dnode *temp,*temp1;
int count,pos,x,i;
for(count=0,temp=head;temp!=NULL;temp=temp->next,count++);
printf("\n Enter position:");
scanf("%d",&pos);
if(pos==1)
{
insert_begin();
}
else if(pos==count+1)
{
insert_end();
}
else
{
temp=(dnode*)malloc(sizeof(dnode));
if(temp!=NULL)
{
printf("\n Enter a value:");
scanf("%d",&x);
temp->data=x;
temp->next=NULL;
temp->prev=NULL;
i=2;
temp1=head;
while(i<pos)
 {
temp1=temp1->next;
i++;
}
temp->next=temp1->next;
temp1->next->prev = temp;
temp1->next = temp;
temp->prev = temp1;
}
}
}

void delete_begin()
{
dnode *temp;
if(head==NULL)
{
printf("\n List is empty");
}
else
{
if(head->next==NULL)
{
temp=head;
printf("\n deleted node is %d",temp->data);
head=NULL;
free(temp);
}
else
{
 temp=head;
printf("\n deleted node is %d",temp->data);
head=head->next;
head->prev=NULL;
free(temp);
}
}
}

void delete_end()
{
dnode *temp,*temp1;
if(head==NULL)
{
printf("\n List is empty");
}
else
{
if(head->next==NULL)
{
temp=head;
printf("\n deleted node is %d",temp->data);
head=NULL;
free(temp);
}
else
{
for(temp1=head;temp1->next->next!=NULL;temp1=temp1-
>next);
temp=temp1->next;
 printf("\n deleted node is %d",temp->data);
temp1->next=NULL;
free(temp);
}
}
}

void delete_pos()
{
dnode *temp,*temp1;
int pos,count,i;
for(count=0,temp=head;temp!=NULL;temp=temp->next,count++);
printf("\n Enter position:");
scanf("%d",&pos);
if(pos==1)
{
delete_begin();
}
else if(pos==count)
{
delete_end();
}
else
{
i=2;
temp1=head;
while(i<pos)
{
temp1=temp1->next;
i++;
 }
temp=temp1->next;
printf("\n Deleted element is %d",temp->data);
temp1->next=temp->next;
temp1->next->prev = temp->prev;
free(temp);
}
}
void display_front()
{
dnode *temp;
if(head==NULL)
{
printf("\n List is Empty");
}
else
{
printf("\n");
for(temp=head;temp!=NULL;temp=temp->next)
{
printf(" %d-->",temp->data);
}
printf("\n");
}
}

void display_last()
{
dnode *last;
if(head==NULL)
 {
printf("\n List is empty");

}
else
{
for(last=head;last->next!=NULL;last=last->next);
printf("\n");
do
{
printf(" %d-->",last->data);
last=last->prev;
}while(last!=NULL);
printf("\n");
}
}

void main()
{
int ch;
while(1)
{
printf("\n 1. Insert begin \n 2. Insert End \n 3. Insert any position
\n 4. Delete Begin \n 5. Delete End\n 6. Delete Position \n 7. Display from
front \n 8. Display from last \n 9. exit\n");
printf("\n Enter your choice\n");
scanf("%d",&ch);
switch(ch)
{
case 1: insert_begin();
break;
case 2: insert_end();
 break;
case 3: insert_pos();
break;
case 4: delete_begin();
break;
case 5: delete_end();
break;
case 6: delete_pos();
break;
case 7: display_front();
break;
case 8: display_last();
break;
case 9: exit(0);
default: printf("\n Enter correct choice\n");
}
}
}

C Program for merging two linked list elements

#include <stdio.h>
#include <stdlib.h>

typedef struct list

{
int data;
struct list *next;
}node;

node *create(node *first)

{
node *temp;
char ch='y';
int x;
while(ch=='y')
{
temp=(node*)malloc(sizeof(node));
if(temp==NULL)
{
printf("\n Insufficient memory");
return NULL;
}
else
{
printf("\n Enter a value:");
scanf("%d",&x);
temp->data=x;
temp->next=NULL;
if(first==NULL)
{
first = temp;
printf("\n %d",first->data);
}
else
{
temp->next=first;
first = temp;
printf("\n %d",first->data);
}
}
 printf("\n Do you want to continue: (y/n):");
fflush(stdin);
scanf("%c",&ch);
}
return first;
}

node *sort(node *head)

{
node *i,*j;
int x;
i=head;
while(i!=NULL)
{
j=i->next;
while(j!=NULL)
{
if(i->data > j->data)
{
x=i->data;
i->data=j->data;
j->data=x;
}
j=j->next;
}
i=i->next;
}
return head;
}
void display(node *first)
{
node *temp;
if(first==NULL)
{
printf("\n List is empty");
}
else
{
printf("\n");
for(temp=first;temp!=NULL;temp=temp->next)
{
printf("%d-->",temp->data);
}
printf("\n");
}
}
node *merge(node *first,node *second)
{
node *temp1,*temp2,*temp3,*head;
temp1=first;
temp2=second;
head=temp3=NULL;
if(temp1->data > temp2->data)
{
head = temp3 = temp2;
temp2 = temp2->next;
temp3->next=NULL;
}
else
{
head = temp3 = temp1;
temp1 = temp1->next;
temp3->next=NULL;
}
while(temp1!=NULL&&temp2!=NULL)
{
if(temp1->data > temp2->data)
{
temp3->next = temp2;
temp2 = temp2->next;
temp3=temp3->next;
}
else
{
temp3->next = temp1;
temp1 = temp1->next;
temp3=temp3->next;
}
}

while(temp1!=NULL)
{
temp3->next = temp1;
temp1=temp1->next;
temp3=temp3->next;
}
while(temp2!=NULL)
{
temp3->next = temp2;
temp2=temp2->next;
 temp3=temp3->next;
}
temp3->next=NULL;
return head;
}

int main(int argc, char *argv[]) {

node *first=NULL,*second=NULL,*third=NULL;
printf("\n Enter first list values:");
first = create(first);
printf("\n Enter Second list values:");
second = create(second);
printf("\n First list values are:");
display(first);
printf("\n Second list values are:");
display(second);
first = sort(first);
printf("\n After sorting first list values are:");
display(first);
second = sort(second);
printf("\n After sorting second list values are:");
display(second);
third = merge(first,second);
printf("\n After merging list values are:");
display(third);
return 0;
}
C program to implement polynomial addition
#include <stdio.h>
#include <stdlib.h>
typedef struct polynomial
{
int coef;
int expo;
struct polynomial *next;
}poly;

poly *create(poly *first)

{
poly *temp,*temp1;
char ch='y';
int x,y;
while(ch=='y')
{
temp=(poly*)malloc(sizeof(poly));
if(temp==NULL)
{
printf("\n Insufficient memory");
return NULL;
}
else
{
printf("\n Enter coefficient value:");
scanf("%d",&x);
printf("\n Enter exponent value:");
scanf("%d",&y);
temp->coef=x;
temp->expo=y;
temp->next=NULL;
 if(first==NULL)
{
first = temp;
}
else
{
for(temp1=first;temp1->next!=NULL;temp1=temp1-
>next);
temp1->next =temp;
}
}

printf("\n Do you want to continue: (y/n):");

fflush(stdin);
scanf("%c",&ch);
}
return first;
}

void display(poly *first)

{
poly *temp;
if(first==NULL)
{
printf("\n List is empty");
}
else
{
printf("\n");
for(temp=first;temp!=NULL;temp=temp->next)
 {
printf(" %dX%d +",temp->coef,temp->expo);
}
printf("\n");
}
}

poly *addition(poly *first,poly *second)

{
poly *f,*s,*head=NULL,*temp=NULL;
f=first;
s=second;
head=temp;

while(s!=NULL&&f!=NULL)
{
if(head==NULL)
{
head=(poly*)malloc(sizeof(poly));
temp=head;

}
else
{
temp->next = (poly*)malloc(sizeof(poly));
temp=temp->next;
}

if(s->expo > f->expo)

{
temp->coef=s->coef;
 temp->expo = s->expo;
s = s->next;
}
else if(s->expo < f->expo)
{
temp->coef=f->coef;
temp->expo = f->expo;
f=f->next;
}
else
{
temp->coef=f->coef+s->coef;
temp->expo = f->expo;
s=s->next;
f=f->next;
}
}

while(f!=NULL)
{
temp->next = (poly*)malloc(sizeof(poly));
temp=temp->next;
temp->coef= f->coef;
temp->expo =f->expo;
f=f->next;
}
while(s!=NULL)
{
temp->next = (poly*)malloc(sizeof(poly));
temp=temp->next;
temp->coef= s->coef;
 temp->expo =s->expo;
s=s->next;
}
temp->next=NULL;
return head;
}

int main(int argc, char *argv[]) {

poly *first=NULL,*second=NULL,*third=NULL;
printf("\n Enter first polynomial values(Give correct order):");
first = create(first);
printf("\n Enter second polynomial values(Give correct order):");
second = create(second);
printf("\n first polynomial values are:");
display(first);
printf("\n Second polynomial values are:");
display(second);
third=addition(first,second);
printf("\n Addition of two polynomials are:");
display(third);
return 0;
}
 UNIT-3
Trees
Trees are very flexible, versatile and powerful non-liner data structure that
can be used to represent data items possessing hierarchical relationship between
the grand father and his children and grand children as so on.

A tree is an ideal data structure for representing hierarchical data

Definition: A tree can be theoretically defined as a finite set of one or more data
items (or nodes) such that:
1. There is a special node called the root of the tree.
2. Removing nodes (or data item) are partitioned into number of mutually
exclusive (i.e., disjoined) subsets each of which is itself a tree, are called sub tree.
Tree Terminology
Root node: The root node R is the topmost node in the tree. If R = NULL,
then it means the tree is empty.
Sub-trees: If the root node R is not NULL, then the trees T1 , T2 , and T3 are
called the sub-trees of R.
Leaf node: A node that has no children is called the leaf node or the terminal
node.
Path: A sequence of consecutive edges is called a path.
For example, in Figure, the path from the root node A to node M is given as: A,
B,E,I and M.
Ancestor node An ancestor of a node is any predecessor node on the path
from root to that node.
Note: The root node does not have any ancestors.
In the tree given in Figure, nodes A, C, and F are the ancestors of node J.
Descendant node A descendant node is any successor node on any path
from the node to a leaf node.
Note: Leaf nodes do not have any descendants.
In the tree given in Figure, nodes C, F, J, and O are the descendants of node
A.
Level number Every node in the tree is assigned a level number in such a
way that the root node is at level 0, children of the root node are at level number
1 and so on.
Thus, every node is at one level higher than its parent.
So, all child nodes have a level number given by parent’s level number + 1.
Degree Degree of a node is equal to the number of children that a node has.
Note: The degree of a leaf node is zero.
In-degree In-degree of a node is the number of edges arriving at that node.
Out-degree Out-degree of a node is the number of edges leaving that node
Types of Trees
1. General trees
2. Forests
3. Binary trees
4. Binary search trees
5. Expression trees
6. Tournament tree
We are focusing only on Binary tress and Binary search trees.
Binary Tree:
A binary tree is a tree in which no node can have more than two children.
Typically, these children are described as “left child” and “right child” of the
parent node.
Definition: A binary tree T is defined as a finite set of elements called nodes,
such that
1. T is empty (i.e. if T has no nodes called the NULL tree or empty tree).
2. T contains a special node R, called the root node of T, and the remaining
nodes of T form an ordered pair of disjoint binary trees T1 and T2 each
of which represents a binary tree.