Date: Exp.no: Page.

no:

Aim: To write a c program to implement a linked list to represent polynomials and perform
additon.
Program:
#include <stdio.h>
#include <conio.h>
#include <malloc.h>
struct node
{
int num;
int coeff;
struct node *next;
};
struct node *start1 = NULL;
struct node *start2 = NULL;
struct node *start3 = NULL;
struct node *last3 = NULL;
struct node *create_poly(struct node *);
struct node *display_poly(struct node *);
struct node *add_poly(struct node *, struct node *, struct node *);
struct node *add_node(struct node *, int, int);
int main()
{
int option;
clrscr();

Data Structures Laboratory

Date: Exp.no: Page.no:

do
{
printf("\n******* MAIN MENU *******");
printf("\n 1. Enter the first polynomial");
printf("\n 2. Display the first polynomial");
printf("\n 3. Enter the second polynomial");
printf("\n 4. Display the second polynomial");
printf("\n 5. Add the polynomials"); printf("\
n 6. Display the result");
printf("\n 7. EXIT");
printf("\n\n Enter your option : ");
scanf("%d", &option);
switch(option)
{
case 1: start1 = create_poly(start1);
break;
case 2: start1 = display_poly(start1);
break;
case 3: start2 = create_poly(start2);
break;
case 4: start2 = display_poly(start2);
break;
case 5: start3 = add_poly(start1, start2, start3);
break;

Data Structures Laboratory

Date: Exp.no: Page.no:

case 6: start3 = display_poly(start3);

break;
}
}while(option!=6);
getch();
return 0;
}
struct node *create_poly(struct node *start)
{
struct node *new_node, *ptr;
int n, c;
printf("\n Enter the number : ");
scanf("%d", &n);
printf("\t Enter its coefficient : ");
scanf("%d", &c);
while(n!=NULL)
{
if(start==NULL)
{
new_node = (struct node *)malloc(sizeof(struct node));
new_node -> num = n;
new_node -> coeff = c;
new_node -> next = NULL;
start = new_node;

Data Structures Laboratory

Date: Exp.no: Page.no:

}
else
{
ptr = start;
while(ptr -> next != NULL)
ptr = ptr -> next;
new_node = (struct node *)malloc(sizeof(struct node));
new_node -> num = n;
new_node -> coeff = c;
new_node -> next = NULL;
ptr -> next = new_node;
}
printf("\n Enter the number : ");
scanf("%d", &n);
if(n == NULL)
break;
printf("\t Enter its coefficient : ");
scanf("%d", &c);
}
return start;
}
struct node *display_poly(struct node *start)
{
struct node *ptr;

Data Structures Laboratory

Date: Exp.no: Page.no:

ptr = start;
while(ptr != NULL)
{
printf("\n%d x^ %d\t", ptr -> num, ptr -> coeff);
ptr = ptr -> next;
}
return start;
}
struct node *add_poly(struct node *start1, struct node *start2, struct node *start3)
{
struct node *ptr1, *ptr2;
int sum_num, c;

ptr1 = start1, ptr2 = start2;

while(ptr1 != NULL && ptr2 != NULL)
{
if(ptr1 -> coeff == ptr2 -> coeff)
{
sum_num = ptr1 -> num + ptr2 -> num;
start3 = add_node(start3, sum_num, ptr1 -> coeff);
ptr1 = ptr1 -> next;
ptr2 = ptr2 -> next;
}
else if(ptr1 -> coeff > ptr2 -> coeff)

Data Structures Laboratory

Date: Exp.no: Page.no:

{
start3 = add_node(start3, ptr1 -> num, ptr1 -> coeff);
ptr1 = ptr1 -> next;
}
else if(ptr1 -> coeff < ptr2 -> coeff)
{
start3 = add_node(start3, ptr2 -> num, ptr2 -> coeff);
ptr2 = ptr2 -> next;
}
}
if(ptr1 == NULL)
{
while(ptr2 != NULL)
{
start3 = add_node(start3, ptr2 -> num, ptr2 -> coeff);
ptr2 = ptr2 -> next;
}
}
if(ptr2 == NULL)
{
while(ptr1 != NULL)
{
start3 = add_node(start3, ptr1 -> num, ptr1 -> coeff);
ptr1 = ptr1 -> next;

Data Structures Laboratory

Date: Exp.no: Page.no:

}
}
return start3;
}

struct node *add_node(struct node *start, int n, int c)

{
struct node *ptr, *new_node;
if(start == NULL)
{
new_node = (struct node *)malloc(sizeof(struct node));
new_node -> num = n;
new_node -> coeff = c;
new_node -> next = NULL;
start = new_node;
}
else
{
ptr = start;
while(ptr -> next != NULL)
ptr = ptr -> next;
new_node = (struct node *)malloc(sizeof(struct node));
new_node -> num = n;
new_node -> coeff = c;

Data Structures Laboratory

Date: Exp.no: Page.no:

new_node -> next = NULL;

ptr -> next = new_node;
}
return start;
}
Output:
******* MAIN MENU *******
1. Enter the first polynomial
2. Display the first polynomial
3. Enter the second polynomial
4. Display the second polynomial
5. Add the polynomials
6. Display the result
7. EXIT

Enter your option : 1

Enter the number : 96

Enter its coefficient :
2

Enter the number : 54

Enter its coefficient :
1

Enter the number : 0

Data Structures Laboratory

Date: Exp.no: Page.no:

******* MAIN MENU *******

1. Enter the first polynomial
2. Display the first polynomial
3. Enter the second polynomial
4. Display the second polynomial
5. Add the polynomials
6. Display the result
7. EXIT

Enter your option :2

96 x^ 2
54 x ^1

******* MAIN MENU *******

1. Enter the first polynomial
2. Display the first polynomial
3. Enter the second polynomial
4. Display the second polynomial
5. Add the polynomials
6. Display the result
7. EXIT

Enter your option : 3

Data Structures Laboratory

Date: Exp.no: Page.no:

Enter the number : 3

Enter its coefficient : 2

Enter the number : 5

Enter its coefficient : 1

Enter the number : 0

******* MAIN MENU *******
1. Enter the first polynomial
2. Display the first polynomial
3. Enter the second polynomial
4. Display the second polynomial
5. Add the polynomials
6. Display the result
7. EXIT

Enter your option :

4 3 x^ 2
5 x^ 1
******* MAIN MENU *******
1. Enter the first polynomial
2. Display the first polynomial
3. Enter the second polynomial
4. Display the second polynomial

Data Structures Laboratory

Date: Exp.no: Page.no:

5. Add the polynomials

6. Display the result
7. EXIT

Enter your option : 5

******* MAIN MENU *******
1. Enter the first polynomial
2. Display the first polynomial
3. Enter the second polynomial
4. Display the second polynomial
5. Add the polynomials
6. Display the result
7. EXIT

Enter your option:6

99 x^2
57 x^1
******* MAIN MENU *******
1. Enter the first polynomial
2. Display the first polynomial
3. Enter the second polynomial
4. Display the second polynomial
5. Add the polynomials
6. Display the result

Data Structures Laboratory

Date: Exp.no: Page.no:

7. EXIT

Enter your option:7

Result:
Hence the c program to implement a linked list to represent polynomials and perform
addition is executed successfully.

Data Structures Laboratory

Date: Exp.no: Page.no:

Aim: To write a c program to implement a circular linked list and perform insertion ,
deletion and traversal .

Program:
#include <stdio.h>
#include <conio.h>
#include <malloc.h>
struct node
{
int data;
struct node *next;
};
struct node *start = NULL;
struct node *create_cll(struct node *);
struct node *display(struct node *);
struct node *insert_beg(struct node *);
struct node *insert_end(struct node *);
struct node *delete_beg(struct node *);
struct node *delete_end(struct node *);
struct node *delete_after(struct node *);
struct node *delete_list(struct node *);
int main()
{
int
option;
clrscr();
do
{

Data Structures Laboratory

Date: Exp.no: Page.no:

printf("\n\n *****MAIN MENU *****");

printf("\n 1: Create a list");
printf("\n 2: Display the list");
printf("\n 3: Add a node at the beginning");
printf("\n 4: Add a node at the end");
printf("\n 5: Delete a node from the beginning");
printf("\n 6: Delete a node from the end");
printf("\n 7: Delete a node after a given node");
printf("\n 8: Delete the entire list");
printf("\n 9: EXIT");
printf("\n\n Enter your option : ");
scanf("%d", &option);
switch(option)
{
case 1: start = create_cll(start);
printf("\n CIRCULAR LINKED LIST CREATED");
break;
case 2: start = display(start);
break;
case 3: start = insert_beg(start);
break;
case 4: start = insert_end(start);
break;
case 5: start = delete_beg(start);

Data Structures Laboratory

Date: Exp.no: Page.no:

break;
case 6: start = delete_end(start);
break;
case 7: start = delete_after(start);
break;
case 8: start = delete_list(start);
printf("\n CIRCULAR LINKED LIST DELETED");
break;
}
}while(option !=9);
getch();
return 0;
}
struct node *create_cll(struct node *start)
{
struct node *new_node, *ptr;
int num;
printf("\n Enter –1 to end");
printf("\n Enter the data :
"); scanf("%d", &num);
while(num!=-1)
{
new_node = (struct node*)malloc(sizeof(struct node));
new_node -> data = num;

Data Structures Laboratory

Date: Exp.no: Page.no:

if(start == NULL)
{
new_node -> next = new_node;
start = new_node;
}
else
{ ptr = start;
while(ptr -> next != start)
ptr = ptr -> next;
ptr -> next = new_node;
new_node -> next = start;
}
printf("\n Enter the data : ");
scanf("%d", &num);
}
return start;
}
struct node *display(struct node *start)
{
struct node
*ptr; ptr=start;
while(ptr -> next != start)
{
printf("\t %d", ptr -> data);

Data Structures Laboratory

Date: Exp.no: Page.no:

ptr = ptr -> next;

}
printf("\t %d", ptr -> data);
If(ptr==NULL)
Printf(“LINKED LIST IS EMPTY”);
return start;
}
struct node *insert_beg(struct node *start)
{
struct node *new_node, *ptr;
int num;
printf("\n Enter the data : ");
scanf("%d", &num);
new_node = (struct node *)malloc(sizeof(struct node));
new_node -> data = num;
ptr = start;
while(ptr -> next != start)
ptr = ptr -> next;
ptr -> next = new_node;
new_node -> next = start;
start = new_node;
return start;
}
struct node *insert_end(struct node *start)

Data Structures Laboratory

Date: Exp.no: Page.no:

{
struct node *ptr, *new_node;
int num;
printf("\n Enter the data : ");
scanf("%d", &num);
new_node = (struct node *)malloc(sizeof(struct node));
new_node -> data = num;
ptr = start;
while(ptr -> next != start)
ptr = ptr -> next;
ptr -> next = new_node;
new_node -> next = start;
return start;
}
struct node *delete_beg(struct node *start)
{
struct node
*ptr; ptr = start;
while(ptr -> next != start)
ptr = ptr -> next;
ptr -> next = start -> next;
free(start);

start = ptr -> next;

Data Structures Laboratory

Date: Exp.no: Page.no:

return start;
}
struct node *delete_end(struct node *start)
{
struct node *ptr, *preptr;
ptr = start;
while(ptr -> next != start)
{
preptr = ptr;
ptr = ptr -> next;
}
preptr -> next = ptr -> next;
free(ptr);
return start;
}
struct node *delete_after(struct node *start)
{
struct node *ptr, *preptr;
int val;
printf("\n Enter the value after which the node has to deleted : ");
scanf("%d", &val);
ptr = start;
preptr = ptr;
while(preptr -> data != val)

Data Structures Laboratory

Date: Exp.no: Page.no:

{
preptr = ptr;
ptr = ptr -> next;
}
preptr -> next = ptr -> next;
if(ptr == start)
start = preptr -> next;
free(ptr);
return start;
}
struct node *delete_list(struct node *start)
{
struct node
*ptr; ptr = start;
while(ptr -> next != start)
start = delete_end(start);
free(start);
return start;
}
Output:
*****MAIN MENU *****
1: Create a list
2: Display the list
3: Add a node at the beginning

Data Structures Laboratory

Date: Exp.no: Page.no:

4: Add a node at the end

5: Delete a node from the beginning
6: Delete a node from the end
7: Delete a node after a given node
8: Delete the entire list
9: EXIT

Enter your option : 1

Enter –1 to end
Enter the data : 4

Enter the data : 2

Enter the data : 3

Enter the data : -1

CIRCULAR LINKED LIST CREATED

*****MAIN MENU *****

1: Create a list
2: Display the list
3: Add a node at the
beginning 4: Add a node at
the end

Data Structures Laboratory

Date: Exp.no: Page.no:

5: Delete a node from the beginning

6: Delete a node from the end
7: Delete a node after a given node
8: Delete the entire list
9: EXIT

Enter your option : 2

4 2 3
*****MAIN MENU *****
1: Create a list
2: Display the list
3: Add a node at the
beginning 4: Add a node at
the end
5: Delete a node from the beginning
6: Delete a node from the end
7: Delete a node after a given node
8: Delete the entire list
9: EXIT

Enter your option : 3

Enter the data : 6

*****MAIN MENU *****
1: Create a list

Data Structures Laboratory

Date: Exp.no: Page.no:

2: Display the list

3: Add a node at the
beginning 4: Add a node at
the end
5: Delete a node from the beginning
6: Delete a node from the end
7: Delete a node after a given node
8: Delete the entire list
9: EXIT

Enter your option : 2

6 4 2 3
*****MAIN MENU *****
1: Create a list
2: Display the list
3: Add a node at the
beginning 4: Add a node at
the end
5: Delete a node from the beginning
6: Delete a node from the end
7: Delete a node after a given node
8: Delete the entire list
9: EXIT

Enter your option : 4

Data Structures Laboratory

Date: Exp.no: Page.no:

Enter the data : 7

*****MAIN MENU *****
1: Create a list
2: Display the list
3: Add a node at the
beginning 4: Add a node at
the end
5: Delete a node from the beginning
6: Delete a node from the end
7: Delete a node after a given node
8: Delete the entire list
9: EXIT

Enter your option : 2

6 4 2 3 7
*****MAIN MENU *****
1: Create a list
2: Display the list
3: Add a node at the
beginning 4: Add a node at
the end
5: Delete a node from the beginning
6: Delete a node from the end
7: Delete a node after a given node
8: Delete the entire list
9: EXIT

Data Structures Laboratory

Date: Exp.no: Page.no:

Enter your option : 5

4 2 37

*****MAIN MENU *****

1: Create a list
2: Display the list
3: Add a node at the
beginning 4: Add a node at
the end
5: Delete a node from the beginning
6: Delete a node from the end
7: Delete a node after a given node
8: Delete the entire list
9: EXIT

Enter your option : 2

4 2 3 7
*****MAIN MENU *****
1: Create a list
2: Display the list
3: Add a node at the
beginning 4: Add a node at
the end
5: Delete a node from the beginning
6: Delete a node from the end

Data Structures Laboratory

Date: Exp.no: Page.no:

7: Delete a node after a given

node 8: Delete the entire list
9: EXIT

Enter your option :6

*****MAIN MENU *****
1: Create a list
2: Display the list
3: Add a node at the
beginning 4: Add a node at
the end
5: Delete a node from the beginning
6: Delete a node from the end
7: Delete a node after a given node
8: Delete the entire list
9: EXIT

Enter your option :2

4 2 3
*****MAIN MENU *****
1: Create a list
2: Display the list
3: Add a node at the beginning
4: Add a node at the end
5: Delete a node from the beginning

Data Structures Laboratory

Date: Exp.no: Page.no:

6: Delete a node from the end

7: Delete a node after a given node
8: Delete the entire list
9: EXIT

Enter your option :7

Enter the node after which the data has to be deleted:2
*****MAIN MENU *****
1: Create a list
2: Display the list
3: Add a node at the
beginning 4: Add a node at
the end
5: Delete a node from the beginning
6: Delete a node from the end
7: Delete a node after a given node
8: Delete the entire list
9: EXIT

Enter your option :2

4 3
*****MAIN MENU *****
1: Create a list
2: Display the list
3: Add a node at the beginning

Data Structures Laboratory

Date: Exp.no: Page.no:

4: Add a node at the end

5: Delete a node from the beginning
6: Delete a node from the end
7: Delete a node after a given node
8: Delete the entire list
9: EXIT

Enter your option :8

*****MAIN MENU *****
1: Create a list
2: Display the list
3: Add a node at the
beginning 4: Add a node at
the end
5: Delete a node from the beginning
6: Delete a node from the end
7: Delete a node after a given node
8: Delete the entire list
9: EXIT

Enter your option :2

LINKED LIST IS EMPTY
*****MAIN MENU *****
1: Create a list
2: Display the list

Data Structures Laboratory

Date: Exp.no: Page.no:

3: Add a node at the beginning

4: Add a node at the end
5: Delete a node from the beginning
6: Delete a node from the end
7: Delete a node after a given node
8: Delete the entire list
9: EXIT

Enter your option :9

Result:
Hence the c program to implement a circular linked list and perform insertions,deletions
and traversal executed successfully.

Data Structures Laboratory

Date: Exp.no: Page.no:

Data Structures Laboratory

Date: Exp.no: Page.no:

Aim: To write a c program to implement doubly linked list and perform insertions,
deletion andtraversal.

Program:
#include <stdio.h>
#include <conio.h>
#include <malloc.h>
struct node
{
struct node *next;
int data;
struct node *prev;
};
struct node *start = NULL;
struct node *create_ll(struct node *);
struct node *display(struct node *);
struct node *insert_beg(struct node *);

Data Structures Laboratory

Date: Exp.no: Page.no:

struct node *insert_end(struct node *);

struct node *insert_before(struct node *);
struct node *insert_after(struct node *);
struct node *delete_beg(struct node *);
struct node *delete_end(struct node *);
struct node *delete_before(struct node *);
struct node *delete_after(struct node *);
struct node *delete_list(struct node *);
int main()
{
int
option;
clrscr();
do
{
printf("\n\n *****MAIN MENU *****");
printf("\n 1: Create a list");
printf("\n 2: Display the list");
printf("\n 3: Add a node at the beginning");
printf("\n 4: Add a node at the end"); printf("\
n 5: Add a node before a given node");
printf("\n 6: Add a node after a given node");
printf("\n 7: Delete a node from the beginning");
printf("\n 8: Delete a node from the end");
printf("\n 9: Delete a node before a given node");

Data Structures Laboratory

Date: Exp.no: Page.no:

printf("\n 10: Delete a node after a given node");

printf("\n 11: Delete the entire list");
printf("\n 12: EXIT");
printf("\n\n Enter your option : ");
scanf("%d", &option);
switch(option)
{
case 1: start = create_ll(start);
printf("\n DOUBLY LINKED LIST CREATED");
break;
case 2: start = display(start);
break;
case 3: start = insert_beg(start);
break;
case 4: start = insert_end(start);
break;
case 5: start = insert_before(start);
break;
case 6: start = insert_after(start);
break;
case 7: start = delete_beg(start);
break;
case 8: start = delete_end(start);
break;

Data Structures Laboratory

Date: Exp.no: Page.no:

case 9: start = delete_before(start);

break;
case 10: start = delete_after(start);
break;
case 11: start = delete_list(start); printf("\
n DOUBLY LINKED LIST DELETED");
break;
}
}while(option != 12);
getch();
return 0;
}
struct node *create_ll(struct node *start)
{
struct node *new_node, *ptr;
int num;
printf("\n Enter –1 to end");
printf("\n Enter the data :
"); scanf("%d", &num);
while(num != –1)
{
if(start == NULL)
{
new_node = (struct node*)malloc(sizeof(struct node));

Data Structures Laboratory

Date: Exp.no: Page.no:

new_node -> prev = NULL;

new_node -> data = num;
new_node -> next = NULL;
start = new_node;
}
else
{
ptr=start;
new_node = (struct node*)malloc(sizeof(struct node));new_node–
>data=num; while(ptr–
>next!=NULL) ptr = ptr–
>next; ptr–
>next = new_node; new_node–
>prev=ptr; new_node–
>next=NULL;
}
printf("\n Enter the data : ");
scanf("%d", &num);
}
return start;
}
struct node *display(struct node *start)
{
struct node *ptr;

Data Structures Laboratory

Date: Exp.no: Page.no:

ptr=start;
while(ptr!=NULL)
{
printf("\t %d", ptr -> data);
ptr = ptr -> next;
}
If(ptr==NULL)
Printf(“THE DOUBLY LINKED LIST EMPTY”);
return start;
}
struct node *insert_beg(struct node *start)
{
struct node *new_node;
int num;
printf("\n Enter the data : ");
scanf("%d", &num);
new_node = (struct node *)malloc(sizeof(struct node));
new_node -> data = num;
start -> prev = new_node;
new_node -> next = start;
new_node -> prev = NULL;
start = new_node;
return start;
}

Data Structures Laboratory

Date: Exp.no: Page.no:

struct node *insert_end(struct node *start)

{
struct node *ptr, *new_node;
int num;
printf("\n Enter the data : ");
scanf("%d", &num);
new_node = (struct node *)malloc(sizeof(struct node));
new_node -> data = num;
ptr=start;
while(ptr -> next != NULL)
ptr = ptr -> next;
ptr -> next = new_node;
new_node -> prev = ptr;
new_node -> next = NULL;
return start;
}
struct node *insert_before(struct node *start)
{
struct node *new_node, *ptr;
int num, val;
printf("\n Enter the data : ");
scanf("%d", &num);
printf("\n Enter the value before which the data has to be inserted:");
scanf("%d", &val);

Data Structures Laboratory

Date: Exp.no: Page.no:

new_node = (struct node *)malloc(sizeof(struct node));

new_node -> data = num;
ptr = start;
while(ptr -> data != val)
ptr = ptr -> next;
new_node -> next = ptr;
new_node -> prev = ptr-> prev;
ptr -> prev -> next = new_node;
ptr -> prev = new_node;
return start;
}
struct node *insert_after(struct node *start)
{
struct node *new_node, *ptr;
int num, val;
printf("\n Enter the data : ");
scanf("%d", &num);
printf("\n Enter the value after which the data has to be inserted:");
scanf("%d", &val);
new_node = (struct node *)malloc(sizeof(struct node));
new_node -> data = num;
ptr = start;
while(ptr -> data != val)
ptr = ptr -> next;

Data Structures Laboratory

Date: Exp.no: Page.no:

new_node -> prev = ptr;

new_node -> next = ptr -> next;
ptr -> next -> prev = new_node;
ptr -> next = new_node;
return start;
}
struct node *delete_beg(struct node *start)
{
struct node
*ptr; ptr = start;
start = start -> next;
start -> prev =
NULL; free(ptr);
return start;
}
struct node *delete_end(struct node *start)
{
struct node
*ptr; ptr = start;
while(ptr -> next != NULL)
ptr = ptr -> next;
ptr -> prev -> next = NULL;
free(ptr);
return start;

Data Structures Laboratory

Date: Exp.no: Page.no:

}
struct node *delete_after(struct node *start)
{
struct node *ptr, *temp;
int val;
printf("\n Enter the value after which the node has to deleted : ");
scanf("%d", &val);
ptr = start;
while(ptr -> data != val)
ptr = ptr -> next;
temp = ptr -> next;
ptr -> next = temp -> next;
temp -> next -> prev = ptr;
free(temp);
return start;
}
struct node *delete_before(struct node *start)
{
struct node *ptr, *temp;
int val;
printf("\n Enter the value before which the node has to deleted:");
scanf("%d", &val);
ptr = start;
while(ptr -> data != val)

Data Structures Laboratory

Date: Exp.no: Page.no:

ptr = ptr -> next;

temp = ptr -> prev;
if(temp == start)
start =
delete_beg(start); else
{
ptr -> prev = temp -> prev;
temp -> prev -> next = ptr;
}
free(temp);
return
start;
}
struct node *delete_list(struct node *start)
{
while(start != NULL)
start =
delete_beg(start);
return start;
}
Output:
*****MAIN MENU *****
1: Create a list
2: Display the list
3: Add a node at the
beginning 4: Add a node at
the end

Data Structures Laboratory

Date: Exp.no: Page.no:

5: Add a node before a given

node 6: Add a node after a given
node
7: Delete a node from the
beginning 8: Delete a node from
the end
9: Delete a node before a given node
10: Delete a node after a given node
11: Delete the entire list
12: EXIT
Enter your option:1
Enter –1 to end
Enter the data: 5
Enter the data:3
Enter the data:4
Enter the data:7
Enter the data:-1
DOUBLY LINKED LIST IS CREATED SUCCESSFULLY
*****MAIN MENU *****
1: Create a list
2: Display the list
3: Add a node at the
beginning 4: Add a node at
the end
5: Add a node before a given node
6: Add a node after a given node
7: Delete a node from the beginning

Data Structures Laboratory

Date: Exp.no: Page.no:

8: Delete a node from the end

9: Delete a node before a given node
10: Delete a node after a given node
11: Delete the entire list
12: EXIT
Enter your option:2
5 3 4 7
*****MAIN MENU *****
1: Create a list
2: Display the list
3: Add a node at the
beginning 4: Add a node at
the end
5: Add a node before a given node
6: Add a node after a given node
7: Delete a node from the beginning
8: Delete a node from the end
9: Delete a node before a given node
10: Delete a node after a given node
11: Delete the entire list
12: EXIT
Enter your option: 3
Enter the data: 10
*****MAIN MENU *****
1: Create a list

Data Structures Laboratory

Date: Exp.no: Page.no:

2: Display the list

3: Add a node at the
beginning 4: Add a node at
the end
5: Add a node before a given node
6: Add a node after a given node
7: Delete a node from the beginning
8: Delete a node from the end
9: Delete a node before a given
node 10: Delete a node after a given
node 11: Delete the entire list
12: EXIT
Enter your option:2
10 5 3 4 7
*****MAIN MENU *****
1: Create a list
2: Display the list
3: Add a node at the
beginning 4: Add a node at
the end
5: Add a node before a given node
6: Add a node after a given node
7: Delete a node from the beginning
8: Delete a node from the end
9: Delete a node before a given node
10: Delete a node after a given node

Data Structures Laboratory

Date: Exp.no: Page.no:

11: Delete the entire list

12: EXIT
Enter your option:4
Enter the data:20
*****MAIN MENU *****
1: Create a list
2: Display the list
3: Add a node at the
beginning 4: Add a node at
the end
5: Add a node before a given node
6: Add a node after a given node
7: Delete a node from the beginning
8: Delete a node from the end
9: Delete a node before a given node
10: Delete a node after a given node
11: Delete the entire list
12: EXIT
Enter your option:2
10 5 3 4 7 20
*****MAIN MENU *****
1: Create a list
2: Display the list
3: Add a node at the
beginning 4: Add a node at
the end

Data Structures Laboratory

Date: Exp.no: Page.no:

5: Add a node before a given node

6: Add a node after a given node
7: Delete a node from the beginning
8: Delete a node from the end
9: Delete a node before a given node
10: Delete a node after a given node
11: Delete the entire list
12: EXIT
Enter your option:5
Enter the data:4
Enter the value before which the data has to be inserted: 3
*****MAIN MENU *****
1: Create a list
2: Display the list
3: Add a node at the
beginning 4: Add a node at
the end
5: Add a node before a given node
6: Add a node after a given node
7: Delete a node from the beginning
8: Delete a node from the end
9: Delete a node before a given node
10: Delete a node after a given node
11: Delete the entire list
12: EXIT

Data Structures Laboratory

Date: Exp.no: Page.no:

Enter your option:2

10 5 4 3 4 7 20
*****MAIN MENU *****
1: Create a list
2: Display the list
3: Add a node at the
beginning 4: Add a node at
the end
5: Add a node before a given node
6: Add a node after a given node
7: Delete a node from the beginning
8: Delete a node from the end
9: Delete a node before a given
node 10: Delete a node after a given
node 11: Delete the entire list
12: EXIT
Enter your option:6
Enter the data: 1
Enter the value after which the data has to be inserted:5
*****MAIN MENU *****
1: Create a list
2: Display the list
3: Add a node at the
beginning 4: Add a node at
the end
5: Add a node before a given node

Data Structures Laboratory

Date: Exp.no: Page.no:

6: Add a node after a given node

7: Delete a node from the
beginning 8: Delete a node from
the end
9: Delete a node before a given
node 10: Delete a node after a given
node 11: Delete the entire list
12: EXIT
Enter your option:2
10 5 1 4 3 4 7 20
*****MAIN MENU *****
1: Create a list
2: Display the list
3: Add a node at the
beginning 4: Add a node at
the end
5: Add a node before a given node
6: Add a node after a given node
7: Delete a node from the beginning
8: Delete a node from the end
9: Delete a node before a given
node 10: Delete a node after a given
node 11: Delete the entire list
12: EXIT
Enter your option:7
*****MAIN MENU *****

Data Structures Laboratory

Date: Exp.no: Page.no:

1: Create a list
2: Display the list
3: Add a node at the
beginning 4: Add a node at
the end
5: Add a node before a given node
6: Add a node after a given node
7: Delete a node from the beginning
8: Delete a node from the end
9: Delete a node before a given node
10: Delete a node after a given node
11: Delete the entire list
12: EXIT
Enter your option:2
5 4 1 3 4 7 20
*****MAIN MENU *****
1: Create a list
2: Display the list
3: Add a node at the
beginning 4: Add a node at
the end
5: Add a node before a given node
6: Add a node after a given node
7: Delete a node from the beginning
8: Delete a node from the end
9: Delete a node before a given node

Data Structures Laboratory

Date: Exp.no: Page.no:

10: Delete a node after a given node

11: Delete the entire list
12: EXIT
Enter your option:8
*****MAIN MENU *****
1: Create a list
2: Display the list
3: Add a node at the
beginning 4: Add a node at
the end
5: Add a node before a given node
6: Add a node after a given node
7: Delete a node from the beginning
8: Delete a node from the end
9: Delete a node before a given node
10: Delete a node after a given node
11: Delete the entire list
12: EXIT
Enter your option:2

5 4 1 3 4 7
*****MAIN MENU *****
1: Create a list
2: Display the list
3: Add a node at the
beginning 4: Add a node at
the end

Data Structures Laboratory

Date: Exp.no: Page.no:

5: Add a node before a given node

6: Add a node after a given node
7: Delete a node from the beginning
8: Delete a node from the end
9: Delete a node before a given node
10: Delete a node after a given node
11: Delete the entire list
12: EXIT
Enter your option:9
Enter the value before which the node has to be deleted:6
*****MAIN MENU *****
1: Create a list
2: Display the list
3: Add a node at the
beginning 4: Add a node at
the end
5: Add a node before a given node
6: Add a node after a given node
7: Delete a node from the beginning
8: Delete a node from the end
9: Delete a node before a given
node 10: Delete a node after a given
node 11: Delete the entire list
12: EXIT
Enter your option:2

Data Structures Laboratory

Date: Exp.no: Page.no:

5 4 1 3 7
*****MAIN MENU *****
1: Create a list
2: Display the list
3: Add a node at the
beginning 4: Add a node at
the end
5: Add a node before a given node
6: Add a node after a given node
7: Delete a node from the beginning
8: Delete a node from the end
9: Delete a node before a given
node 10: Delete a node after a given
node 11: Delete the entire list
12: EXIT
Enter your option:10
Enter the value after which the node has to be deleted:1
*****MAIN MENU *****
1: Create a list
2: Display the list
3: Add a node at the
beginning 4: Add a node at
the end
5: Add a node before a given node
6: Add a node after a given node
7: Delete a node from the beginning

Data Structures Laboratory

Date: Exp.no: Page.no:

8: Delete a node from the end

9: Delete a node before a given node
10: Delete a node after a given node
11: Delete the entire list
12: EXIT
Enter your option:2

5 4 1 7
*****MAIN MENU *****
1: Create a list
2: Display the list
3: Add a node at the
beginning 4: Add a node at
the end
5: Add a node before a given node
6: Add a node after a given node
7: Delete a node from the beginning
8: Delete a node from the end
9: Delete a node before a given node
10: Delete a node after a given node
11: Delete the entire list
12: EXIT
Enter your option:11
*****MAIN MENU *****
1: Create a list
2: Display the list

Data Structures Laboratory

Date: Exp.no: Page.no:

3: Add a node at the

beginning 4: Add a node at
the end
5: Add a node before a given node
6: Add a node after a given node
7: Delete a node from the beginning
8: Delete a node from the end
9: Delete a node before a given node
10: Delete a node after a given node
11: Delete the entire list
12: EXIT
Enter your option:2
THE DOUBLY LINKED LIST EMPTY
*****MAIN MENU *****
1: Create a list
2: Display the list
3: Add a node at the
beginning 4: Add a node at
the end
5: Add a node before a given node
6: Add a node after a given node
7: Delete a node from the beginning
8: Delete a node from the end
9: Delete a node before a given node
10: Delete a node after a given node
11: Delete the entire list

Data Structures Laboratory

Date: Exp.no: Page.no:

12: EXIT
Enter your option:12
Result:
Hence the c program to implement doubly linked list and perform insertion, deletion
and traverse is executed successfully.

Data Structures Laboratory

Date: Exp.no: Page.no:

Aim: To write a c propgram to implement stacks using arrays.

Data Structures Laboratory

 Date: Exp.no: Page.no:

Program:
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#define MAX 3 // Altering this value changes size of stack created
int st[MAX], top=-1;
void push(int st[], int val);
int pop(int st[]);
int peek(int st[]);
void display(int
st[]);
int main(int argc, char *argv[])
{ int val, option;
do
{
printf("\n ****MAIN
MENU"); printf("\n 1. PUSH");
printf("\n 2. POP");
printf("\n 3. PEEK");
printf("\n 4. DISPLAY");
printf("\n 5. EXIT");
printf("\n Enter your option: ");
scanf("%d", &option);
switch(option)
{
Data Strcutures Laboratory
 Date: Exp.no: Page.no:

case 1:
printf("\n Enter the number to be pushed on stack: ");
scanf("%d", &val);
push(st, val);
break;
case 2:
val = pop(st);
if(val != -1)
printf("\n The value deleted from stack is: %d", val);
break;
case 3:
val =
peek(st);
if(val != -1)
printf("\n The value stored at top of stack is: %d", val);
break;
case 4:
display(st);
break;
}
}while(option != 5);
return 0;
}
void push(int st[], int val)
{
Data Strcutures Laboratory
 Date: Exp.no: Page.no:

if(top == MAX-1)
{
printf("\n STACK OVERFLOW");
}
else
{
top++;
st[top] =
val;
}
}
int pop(int st[])
{
int val;
if(top == -1)
{
printf("\n STACK UNDERFLOW");
return -1;
}
else
{
val =
st[top];
top--;
return val;
}
Data Strcutures Laboratory
 Date: Exp.no: Page.no:

}
void display(int st[])
{
int i;
if(top == -1)
printf("\n STACK IS EMPTY");
else
{
for(i=top;i>=0;i--)
printf("\n %d",st[i]);
printf("\n"); // Added for formatting purposes
}
}
int peek(int st[])
{
if(top == -1)
{
printf("\n STACK IS EMPTY");
return -1;
}
else
return (st[top]);
}
Output:
Data Strcutures Laboratory
 Date: Exp.no: Page.no:

****MAIN MENU****
1. PUSH
2. POP
3. PEEK
4. DISPLAY
5. EXIT
Enter your option: 1
Enter the number to be pushed on stack: 12
****MAIN MENU****
1. PUSH
2. POP
3. PEEK
4. DISPLAY
5. EXIT
Enter your option: 1
Enter the number to be pushed on stack: 24
****MAIN MENU****
1. PUSH
2. POP
3. PEEK
4. DISPLAY
5. EXIT
Enter your option: 1
Enter the number to be pushed on stack: 20
Data Strcutures Laboratory
 Date: Exp.no: Page.no:

****MAIN MENU****
1. PUSH
2. POP
3. PEEK
4. DISPLAY
5. EXIT
Enter your option: 4
20
24
12
****MAIN MENU****
1. PUSH
2. POP
3. PEEK
4. DISPLAY
5. EXIT
Enter your option: 3
The value stored at top of stack is: 20
****MAIN MENU****
1. PUSH
2. POP
3. PEEK
4. DISPLAY
5. EXIT
Data Strcutures Laboratory
 Date: Exp.no: Page.no:

Enter your option: 2

The value deleted from stack is: 20
****MAIN MENU****
1. PUSH
2. POP
3. PEEK
4. DISPLAY
5. EXIT
Enter your option: 4
24
12
****MAIN MENU****
1. PUSH
2. POP
3. PEEK
4. DISPLAY
5. EXIT
Enter your option:5
Result:
Hence the c program to implement stacks using arrays implemented succesfully.

Aim:To write a cprogram to implement stacks using linlked list

Data Strcutures Laboratory

 Date: Exp.no: Page.no:

Program:
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <malloc.h>
struct stack
{
int data;
struct stack *next;
};
struct stack *top = NULL;
struct stack *push(struct stack *, int);
struct stack *display(struct stack *);
struct stack *pop(struct stack *);
int peek(struct stack *);
int main(int argc, char *argv[])
{ int val, option;
do
{
printf("\n ****MAIN MENU");
printf("\n 1. PUSH");
printf("\n 2. POP");
printf("\n 3. PEEK");
printf("\n 4. DISPLAY");

Data Strcutures Laboratory

 Date: Exp.no: Page.no:

printf("\n 5. EXIT");
printf("\n Enter your option: ");
scanf("%d", &option);
switch(option)
{
case 1:
printf("\n Enter the number to be pushed on stack: ");
scanf("%d", &val);
top = push(top, val);
break;
case 2:
top = pop(top);
break;
case 3:
val = peek(top);
if (val != -1)
printf("\n The value at the top of stack is: %d", val);
else
printf("\n STACK IS EMPTY");
break;
case 4:
top = display(top);
break;
}
Data Strcutures Laboratory
 Date: Exp.no: Page.no:

}while(option != 5);
return 0;
}
struct stack *push(struct stack *top, int val)
{
struct stack *ptr;
ptr = (struct stack*)malloc(sizeof(struct stack));
ptr -> data = val;
if(top == NULL)
{
ptr -> next = NULL;
top = ptr;
}
else
{
ptr -> next = top;
top = ptr;
}
return top;
}
struct stack *display(struct stack *top)
{
struct stack
*ptr; ptr = top;
Data Strcutures Laboratory
 Date: Exp.no: Page.no:

if(top == NULL)
printf("\n STACK IS EMPTY");
else
{
while(ptr != NULL)
{
printf("\n %d", ptr -> data);
ptr = ptr -> next;
}
}
return top;
}
struct stack *pop(struct stack *top)
{
struct stack
*ptr; ptr = top;
if(top == NULL)
printf("\n STACK UNDERFLOW");
else
{
top = top -> next;
printf("\n The value being deleted is: %d", ptr -> data);
free(ptr);
}
Data Strcutures Laboratory
 Date: Exp.no: Page.no:

return top;
}
int peek(struct stack *top)
{
if(top==NULL)
return -1;
else
return top ->data;
}
Out put:
****MAIN MENU****
1. PUSH
2. POP
3. PEEK
4. DISPLAY
5. EXIT
Enter your option: 1
Enter the number to be pushed on stack: 4
****MAIN MENU****
1. PUSH
2. POP
3. PEEK
4. DISPLAY
5. EXIT
Data Strcutures Laboratory
 Date: Exp.no: Page.no:

Enter your option: 1

Enter the number to be pushed on stack: 16
****MAIN MENU****
1. PUSH
2. POP
3. PEEK
4. DISPLAY
5. EXIT
Enter your option: 1
Enter the number to be pushed on stack: 20
****MAIN MENU****
1. PUSH
2. POP
3. PEEK
4. DISPLAY
5. EXIT
Enter your option: 1
Enter the number to be pushed on stack: 25

****MAIN MENU****
1. PUSH
2. POP
3. PEEK
4. DISPLAY
Data Strcutures Laboratory
 Date: Exp.no: Page.no:

5. EXIT
Enter your option: 1
Enter the number to be pushed on stack: 36
****MAIN MENU****
1. PUSH
2. POP
3. PEEK
4. DISPLAY
5. EXIT
Enter your option: 4
36
25
20
16
4
****MAIN MENU****
1. PUSH
2. POP
3. PEEK
4. DISPLAY
5. EXIT
Enter your option: 2
The value being deleted is: 36
****MAIN MENU****
Data Strcutures Laboratory
 Date: Exp.no: Page.no:

1. PUSH
2. POP
3. PEEK
4. DISPLAY
5. EXIT
Enter your option: 2
The value being deleted is: 25
****MAIN MENU****
1. PUSH
2. POP
3. PEEK
4. DISPLAY
5. EXIT
Enter your option: 3
The value at the top of stack is: 20
****MAIN MENU****
1. PUSH
2. POP
3. PEEK
4. DISPLAY
5. EXIT
Enter your option: 4
20
16
Data Strcutures Laboratory
 Date: Exp.no: Page.no:

4
****MAIN MENU****
1. PUSH
2. POP
3. PEEK
4. DISPLAY
5. EXIT
Enter your option: 5
Result:
Hence the c program to implement stacks using linked list executed successfully.

Data Strcutures Laboratory

 Date: Exp.no: Page.no:

Aim:To write a c program to evaluate postfix expression using stack.

Program:
#include <stdio.h>
#include <conio.h>
#include <ctype.h>
#define MAX 100
float st[MAX];
int top=-1;
void push(float st[], float val);
float pop(float st[]);
float evaluatePostfixExp(char exp[]);
int main()
{
float val;
char exp[100];
clrscr();
printf("\n Enter any postfix expression : ");
Data Strcutures Laboratory
 Date: Exp.no: Page.no:

gets(exp);
val = evaluatePostfixExp(exp);
printf("\n Value of the postfix expression = %.2f", val);
getch();
return 0;
}
float evaluatePostfixExp(char exp[])
{
int i=0;
float op1, op2, value;
while(exp[i] != '\0')
{
if(isdigit(exp[i]))
push(st, (float)(exp[i]-'0'));
else
{
op2 = pop(st);
op1 = pop(st);
switch(exp[i])
{
case '+':
value = op1 + op2;
break;
case '-':
Data Strcutures Laboratory
 Date: Exp.no: Page.no:

value = op1 - op2;

break;
case '/':
value = op1 / op2;
break;
case '*':
value = op1 * op2;
break;
case '%':
value = (int)op1 % (int)op2;
break;
}
push(st, value);
} i+
+;
}
return(pop(st));
}
void push(float st[], float val)
{
if(top==MAX-1)
printf("\n STACK
OVERFLOW"); else
{
Data Strcutures Laboratory
 Date: Exp.no: Page.no:

top++;
st[top]=val;
}
}
float pop(float st[])
{
float val=-
1; if(top==-
1)
printf("\n STACK UNDERFLOW");
else
{
val=st[top];
top--;
}
return val;
}
Output:
Enter any postfix expression: 6 7 8 +2*/
Value of postfix expression is: 5.00
Result:
Hence the c program to evaluate postfix expression is executed successfully.

Data Strcutures Laboratory

 Date: Exp.no: Page.no:

Aim:To write a c program to check paranthesis.

Data Strcutures Laboratory
 Date: Exp.no: Page.no:

Program:
#include <stdio.h>
#include <conio.h>
#include <string.h>
#define MAX 10
int top =-1;
int stk[MAX];
void push(char);
char pop();
void main()
{
char exp[MAX],temp;
int i, flag=1;
clrscr();
printf("Enter an expression : ");
gets(exp); for(i=0;i<strlen(exp);i+
+)
{
if(exp[i]=='(' || exp[i]=='{' || exp[i]=='[')
push(exp[i]);
if(exp[i]==')' || exp[i]=='}' || exp[i]==']')
if(top == -1)
flag=0;
else

Data Strcutures Laboratory

 Date: Exp.no: Page.no:

{
temp=pop();
if(exp[i]==')' && (temp=='{' || temp=='['))
flag=0;
if(exp[i]=='}' && (temp=='(' || temp=='['))
flag=0;
if(exp[i]==']' && (temp=='(' || temp=='{'))
flag=0;
}
}
if(top>=0)
flag=0;
if(flag==1)
printf("\n Valid expression");
else
printf("\n Invalid expression");
}
void push(char c)
{
if(top == (MAX-1))
printf("Stack Overflow\n");
else
{
top=top+1;

Data Strcutures Laboratory

 Date: Exp.no: Page.no:

stk[top] = c;
}
}
char pop()
{
if(top ==-1)
printf("\n Stack
Underflow"); else
return(stk[top--]);
}
Output:
Enter an expression : (2+3{4-2}+)
Valid expression
Result:
Hence c program to check paranthesis executed successfully.

Data Strcutures Laboratory

Date: Exp.no: Page.no:

Data Strcutures Laboratory