DATA STRUCTURE -ASSIGNMENT NO.5-LINKED LIST
PRACTICE PROGRAM:
1) Write a C Program to find largest element of doubly linked list.
ANS:
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
typedef struct node
{
struct node *pre;
int data;
struct node *next;
} NODE;
NODE *create_list(NODE *list)
{
NODE *temp = list, *new_node;
int n, i;
printf("\n Enter how many nodes:");
scanf("%d", &n);
for (i = 1; i <= n; i++)
{
new_node = (NODE *)malloc(sizeof(struct node));
new_node->next = NULL;
new_node->pre = NULL;
printf("\n Enter [%d] node data:", i);
scanf("%d", &new_node->data);
if (list == NULL)
{
list = temp = new_node;
}
else
{
temp->next = new_node;
temp->next->pre = temp;
temp = new_node;
}
}
return list;
}
void display(NODE *list)
{
NODE *temp=list;
int max=temp->data;
while(temp!=NULL)
{
printf("\t%d",temp->data);
temp=temp->next;
}
}
int count(NODE*list)
{
int n=0;
while (list!=NULL)
{
n++;
list=list->next;
}
return n;
}
int largest(NODE*list)
{
int max;
NODE*temp=list;
while(temp->next!=NULL)
{
temp=temp->next;
}
max=temp->data;
return max;
}
void bubble_sort(NODE*list, int n)
{
int pass,i;
NODE*temp;
int temp1;
for(pass=1;pass<=n;pass++)
{
for(i=1,temp=list;i<=n-pass&&temp!=NULL;i++,temp=temp->next)
{
if(temp->data>temp->next->data)
{
temp1=temp->data;
temp->data=temp->next->data;
temp->next->data=temp1;
}
}
}
}
int main()
{
NODE *list=NULL;
int max;
int c;
list=create_list(list);
printf("\n Doubly linked list is:\n");
display(list);
c=count(list);
bubble_sort(list,c);
printf("\n The sorted list is:\n");
display(list);
max=largest(list);
printf("\n The largest number in list is = %d",max);
}
------------------------------------------------------------------------------------
2) Write a C Program to interchange the two adjacent nodes in given circular linked list.
ANS:
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
typedef struct node
{
int data;
struct node *next;
} NODE;
NODE *create_list(NODE *list)
{
NODE *temp = list, *new_node, *temp1;
int i, n;
printf("\n Enter size of list:");
scanf("%d", &n);
for (i = 1; i <= n; i++)
{
new_node = (NODE *)malloc(sizeof(NODE));
new_node->next = NULL;
printf("\n Enter [%d] node data:", i);
scanf("%d", &new_node->data);
if (list == NULL)
{
list = temp = new_node;
temp1=list;
}
else
{
temp->next = new_node;
temp = new_node;
}
if (temp->next==NULL)
{
temp->next=temp1;
}
}
return list;
}
void display(NODE *list)
{
NODE *temp = list;
do
{
printf("\t%d", temp->data);
temp = temp->next;
} while (temp != list);
}
NODE *interchange(NODE *list)
{
NODE *t1,*t2,*t3;
t1=list;
t2=t1->next;
t3=t2->next;
while (t2!=list)
{
t2->next=NULL;
t2->next=t1;
t1->next=t3;
}
return list;
}
int main()
{
NODE *list = NULL;
list = create_list(list);
printf("\n The circular list is:\n");
display(list);
list=interchange(list);
printf("\n After interchange two adjacent of list is:\n ");
display(list);
getch();
return 0;
}
------------------------------------------------------------------------------
3) Write C Program to find length of linked list without using recursion.
ANS:
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
typedef struct node
{
int data;
struct node *next;
}NODE;
NODE*create_list(NODE*list)
{
NODE*temp=list,*new_node;
int i,n;
printf("\n Enter size of list:");
scanf("%d",&n);
for ( i = 1; i <= n; i++)
{
new_node=(NODE*)malloc(sizeof(NODE));
new_node->next=NULL;
printf("\n Enter [%d] node data:",i);
scanf("%d",&new_node->data);
if (list==NULL)
{
list=temp=new_node;
}else{
temp->next=new_node;
temp=new_node;
}
}
return list;
}
void display(NODE*list){
while (list!=NULL)
{
printf("\t%d",list->data);
list=list->next;
}
}
int count(NODE*list)
{
int count=0;
while (list!=NULL)
{
count++;
list=list->next;
}
return count;
}
int main()
{
NODE *list=NULL;
int length;
list=create_list(list);
printf("\n The linked list is:\n");
display(list);
length=count(list);
printf("\n The size of list is:%d",length);
}
------------------------------------------------------------
4) Write C Program to print alternative nodes in linked list using recursion.
ANS:
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
typedef struct node
{
int data;
struct node *next;
}NODE;
NODE*create_list(NODE*list)
{
NODE*temp=list,*new_node;
int i,n;
printf("\n Enter size of list:");
scanf("%d",&n);
for ( i = 1; i <= n; i++)
{
new_node=(NODE*)malloc(sizeof(NODE));
new_node->next=NULL;
printf("\n Enter [%d] node data:",i);
scanf("%d",&new_node->data);
if (list==NULL)
{
list=temp=new_node;
}else{
temp->next=new_node;
temp=new_node;
}
}
return list;
}
void display(NODE*list){
while (list!=NULL)
{
printf("\t%d",list->data);
list=list->next;
}
}
void display_alter(NODE*list){
NODE *temp1,*temp2,*temp3;
temp1=list;
temp2=temp1->next;
temp3=temp2->next;
do
{
printf("\t%d",temp1->data);
printf("\t%d",temp3->data);
printf("\t%d",temp2->data);
temp1=temp3->next;
temp2=temp1->next;
temp3=temp2->next;
}while((temp1!=NULL));
}
int main()
{
NODE*list=NULL;
list=create_list(list);
printf("\n The list is:\n");
display(list);
printf("\n The alternative nodes of list is:\n");
display_alter(list);
}
-----------------------------------------------------------
SET A:
1) Write a C program to implement a singly linked list with Create and Display operation.
ANS:
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
typedef struct node
{
int data;
struct node *next;
}NODE;
NODE *create_list(NODE *list)
{
NODE *temp, *new_node;
int n, i;
printf("\n Enter how many nodes you want:");
scanf("%d", &n);
for (i = 1; i <= n; i++)
{
new_node = (NODE *)malloc(sizeof(struct node));
new_node->next = NULL;
printf("\n Enter [%d] list element:", i);
scanf("%d", &new_node->data);
if (list == NULL)
{
list = temp = new_node;
}
else
{
temp->next = new_node;
temp = new_node;
}
}
return list;
}
void display(NODE *list)
{
while (list != NULL)
{
printf("\t%d", list->data);
list = list->next;
}
}
int main()
{
NODE *list=NULL;
list=create_list(list);
printf("\n The list is:\n");
display(list);
getch();
return 0;
}
---------------------------------------------------------
2) Write a C program to implement a Circular Singly linked list with Create and Display
operation.
ANS:
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
typedef struct node
{
int data;
struct node *next;
} NODE;
NODE *create_list(NODE *list)
{
NODE *temp, *new_node, *temp1;
int n, i;
printf("\n Enter how many nodes you want:");
scanf("%d", &n);
for (i = 1; i <= n; i++)
{
new_node = (NODE *)malloc(sizeof(struct node));
new_node->next = NULL;
printf("\n Enter [%d] list element:", i);
scanf("%d", &new_node->data);
if (list == NULL)
{
list = temp = new_node;
temp1 = list;
}
else
{
temp->next = new_node;
temp = new_node;
}
if (temp->next == NULL)
{
temp->next = temp1;
}
}
return list;
}
void display(NODE *list)
{
NODE *temp = list;
do
{
printf("\t%d", temp->data);
temp = temp->next;
} while (temp != list);
}
int main()
{
NODE *list = NULL;
list = create_list(list);
printf("\n list is:\n");
display(list);
getch();
return 0;
}
-----------------------------------------------
3) Write a C program to implement a doubly linked list with Create and Display operation.
ANS:
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
typedef struct node
{
struct node *pre;
int data;
struct node *next;
} NODE;
NODE *create_list(NODE *list)
{
NODE *temp = list, *new_node;
int n, i;
printf("\n Enter how many elements you want:");
scanf("%d", &n);
for (i = 1; i <= n; i++)
{
new_node = (NODE *)malloc(sizeof(struct node));
new_node->pre = NULL;
new_node->next = NULL;
printf("\n Enter [%d] node element:", i);
scanf("%d", &new_node->data);
if (list == NULL)
{
list = temp = new_node;
}
else
{
temp->next = new_node;
new_node->pre = temp;
temp = new_node;
}
}
return list;
}
void display(NODE *list)
{
NODE *temp = list;
while (temp!=NULL)
{
printf("\t%d",temp->data);
temp=temp->next;
}
}
int main()
{
NODE *list = NULL;
list = create_list(list);
printf("\n The doubly list is:\n");
display(list);
getch();
return 0;
}
------------------------------------------------------
4) Write a C program to implement a Circular doubly linked list with Create and Display
operation.
ANS:
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
typedef struct node
{
struct node *pre;
int data;
struct node *next;
} NODE;
NODE *create_list(NODE *list)
{
NODE *temp = list, *new_node, *temp1;
int i, n;
printf("\n Enter how many nodes:");
scanf("%d", &n);
for (i = 1; i <= n; i++)
{
new_node = (NODE *)malloc(sizeof(NODE));
new_node->next = NULL;
new_node->pre = NULL;
printf("\n Enter [%d] node data:",i);
scanf("%d", &new_node->data);
if (list == NULL)
{
list = temp = new_node;
temp1 = list;
}
else
{
temp->next = new_node;
temp->next->pre = temp;
temp = new_node;
}
if (temp->next == NULL)
{
temp->next = list;
}
}
return list;
}
void display(NODE *list)
{
NODE *temp = list;
do
{
printf("\t%d", temp->data);
temp = temp->next;
} while (temp != list);
}
void display_pre(NODE *list)
{
NODE *temp = list,*temp1;
do
{
temp = temp->next;
} while (temp->next != list);
list=temp;
do
{
printf("\t%d",temp->data);
temp=temp->pre;
} while (temp!=list);
}
int main()
{
NODE *list = NULL;
list = create_list(list);
printf("\n The circular doubly list is:\n");
display(list);
printf("\n The list using previous link:\n");
display_pre(list);
}
--------------------------------------------------------------
SET B:
1) Implement the following programs by adding the functions one by one in SET A(Question1)
i) To count total number of nodes and display the count.
ii) To insert node at the start.
iii) To reverse the Linked List and display both the list.
ANS:
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
typedef struct node
{
int data;
struct node *next;
} NODE;
NODE *create_list(NODE *list)
{
NODE *temp, *new_node;
int i, n;
printf("\n Enter how many nodes you want:");
scanf("%d", &n);
for (i = 1; i <= n; i++)
{
new_node = (NODE *)malloc(sizeof(NODE));
new_node->next = NULL;
printf("\n Enter [%d] element of list:");
scanf("%d", &new_node->data);
if (list == NULL)
{
list = temp = new_node;
}
else
{
new_node->next = list;
list = new_node;
}
}
return list;
}
void display(NODE *list)
{
while (list != NULL)
{
printf("\t%d", list->data);
list = list->next;
}
}
void count(NODE *list)
{
int count = 0;
while (list != NULL)
{
count++;
list = list->next;
}
printf("\n The no.of nodes are in list is %d", count);
}
NODE *insert(NODE *list, int n)
{
NODE *temp = list, *new_node;
new_node = (NODE *)malloc(sizeof(NODE));
new_node->next = NULL;
new_node->data = n;
if (list == NULL)
{
list = temp = new_node;
}
else
{
new_node->next = list;
list = new_node;
}
return list;
}
NODE *reverse(NODE*list,NODE*rev_list){
NODE *temp=list;
while (temp!=NULL)
{
rev_list=insert(rev_list,temp->data);
temp=temp->next;
}
return rev_list;
}
int main()
{
NODE *list = NULL, *rev_list = NULL;
int n, i, choice;
do
{
printf("\n----------------------------");
printf("\n 1.create \n 2.display\n 3.count no.of nodes \n 4.insert \n5.reverse the list \n6.Exit");
printf("\n ---------------------------");
printf("\n Enter your choice:");
scanf("%d", &choice);
switch (choice)
{
case 1:
list = create_list(list);
break;
case 2:
printf("\n The list is:\n");
display(list);
break;
case 3:
count(list);
break;
case 4:
printf("\n Enter value to insert:");
scanf("%d", &n);
list = insert(list, n);
break;
case 5:
rev_list = reverse(list, rev_list);
printf("\n Original list is:\n");
display(list);
printf("\n The reverse list is:\n");
display(rev_list);
break;
}
} while (choice != 6);
}
-----------------------------------------------------------------
2) Write a Menu driven program in C to implement the following functions:
i) To search the number in the list. If the number is present display the Position of
node .If number not present print the message “Number not Found”
ii) To swap mth and nth element of linked list.
iii) To delete node from specific position of linked list.
ANS:
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
typedef struct node
{
int data;
struct node *next;
} NODE;
NODE *create_list(NODE *list)
{
NODE *temp, *new_node;
int i, n;
printf("\n Enter how many nodes you want:");
scanf("%d", &n);
for (i = 1; i <= n; i++)
{
new_node = (NODE *)malloc(sizeof(NODE));
new_node->next = NULL;
printf("\n Enter [%d] element of list:", i);
scanf("%d", &new_node->data);
if (list == NULL)
{
list = temp = new_node;
}
else
{
new_node->next = list;
list = new_node;
}
}
return list;
}
void display(NODE *list)
{
while (list != NULL)
{
printf("\t%d", list->data);
list = list->next;
}
}
NODE *search(NODE *list, int n)
{
while (list != NULL)
{
if (list->data == n)
{
return list;
}
list = list->next;
}
return NULL;
}
NODE *swap(NODE *list, int p1, int p2)
{
NODE *temp1, *temp2;
int temp3;
int i;
for (i = 1, temp1 = list; i < p1 && temp1->next != NULL; i++, temp1 = temp1->next)
;
for (i = 1, temp2 = list; i < p2 && temp2->next != NULL; i++, temp2 = temp2->next)
;
temp3 = temp1->data;
temp1->data = temp2->data;
temp2->data = temp3;
return list;
}
NODE *delete(NODE *list, int p)
{
NODE *temp = list, *temp1;
int i;
if (p == 1)
{
list = temp->next;
free(temp);
}
else
{
for (i = 1, temp = list; i < p - 1 && temp->next != NULL; i++, temp = temp->next)
;
if (temp == NULL)
{
printf("\n position out of range!");
return list;
}
else
{
temp1 = temp->next;
temp->next = temp1->next;
free(temp1);
}
}
return list;
}
int main()
{
NODE *list = NULL, *address;
int n, choice, p1, p2;
do
{
printf("\n--------------------------------");
printf("\n 1.create \n 2.display \n3.search \n4.swap \n5.delete \n 6.Exit");
printf("\n--------------------------------");
printf("\n Enter your choice:");
scanf("%d", &choice);
switch (choice)
{
case 1:
list = create_list(list);
break;
case 2:
printf("\n The list is:\n");
display(list);
break;
case 3:
printf("\n Enter value for search in list:");
scanf("%d", &n);
address = search(list, n);
if (address == NULL)
{
printf("\n The element not found in list!");
}
else
{
printf("\n Element are founded at %d node position of list!", address);
}
break;
case 4:
printf("\n Enter two positions for swap its data:");
scanf("%d%d", &p1, &p2);
list = swap(list, p1, p2);
printf("\n After swap list is:\n");
display(list);
break;
case 5:
printf("\n Enter position for delete a node:");
scanf("%d", &p1);
list = delete (list, p1);
break;
}
} while (choice != 6);
getch();
return 0;
}
--------------------------------------------------------------------------------------------
3) Write a ‘C’ program to sort elements of a singly linked list in ascending order and display
the sorted List.
ANS:
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
typedef struct node
{
int data;
struct node *next;
} NODE;
NODE *create_list(NODE *list)
{
NODE *temp = list, *new_node;
int i, n;
printf("\n Enter how many nodes you want:");
scanf("%d", &n);
for (i = 1; i <= n; i++)
{
new_node = (NODE *)malloc(sizeof(NODE));
new_node->next = NULL;
printf("\n Enter [%d] node data:", i);
scanf("%d", &new_node->data);
if (list == NULL)
{
list = temp = new_node;
}
else
{
temp->next = new_node;
temp = new_node;
}
}
return list;
}
void display(NODE *list)
{
while (list != NULL)
{
printf("\t%d", list->data);
list = list->next;
}
}
void bubble_sort(NODE *list, int n)
{
NODE *temp;
int pass, i, temp1;
for (pass = 1; pass <= n && temp != NULL; pass++)
{
for (i = 1, temp = list; i <= n - pass && temp != NULL; i++, temp = temp->next)
{
if (temp->data > temp->next->data)
{
temp1 = temp->data;
temp->data = temp->next->data;
temp->next->data = temp1;
}
}
}
}
int count(NODE *list)
{
int count = 0;
while (list != NULL)
{
count++;
list = list->next;
}
return count;
}
int main()
{
NODE *list = NULL;
int n;
list = create_list(list);
printf("\n The original list is:\n");
display(list);
n = count(list);
bubble_sort(list, n);
printf("\n The sorted list is:\n");
display(list);
getch();
return 0;
}
------------------------------------------------------------
4) Write a ‘C’ program to create doubly link list and display nodes having odd value.
ANS:
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
typedef struct node
{
struct node *pre;
int data;
struct node *next;
} NODE;
NODE *create_list(NODE *list)
{
NODE *temp = list, *new_node;
int i, n;
printf("\n Enter length of list:");
scanf("%d", &n);
for (i = 1; i <= n; i++)
{
new_node = (NODE *)malloc(sizeof(NODE));
new_node->next = NULL;
new_node->pre = NULL;
printf("\n Enter [%d] node data:", i);
scanf("%d", &new_node->data);
if (list == NULL)
{
list = temp = new_node;
}
else
{
temp->next = new_node;
temp->next->pre = temp;
temp = new_node;
}
}
return list;
}
void display(NODE *list)
{
NODE *temp = list;
while(temp!=NULL)
{
printf("\t%d", temp->data);
temp = temp->next;
}
}
void odd_nodes(NODE *list)
{
NODE *temp = list;
while(temp!=NULL)
{
if (temp->data % 2 == 1)
{
printf("\t%d", temp->data);
}
temp = temp->next;
}
}
int main()
{
NODE *list = NULL;
list = create_list(list);
printf("\n The doubly list is:\n");
display(list);
printf("\n The nodes having odd value:\n");
odd_nodes(list);
getch() ;
return 0;
}
------------------------------------------------------------------------
SET C:
1) Write a C program to find intersection of two singly linked lists.
ANS:
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
typedef struct node
{
int data;
struct node *next;
} NODE;
NODE *create_list(NODE *list)
{
NODE *temp = list, *new_node;
int n, i;
printf("\n Enter size of list:");
scanf("%d", &n);
for (i = 1; i <= n; i++)
{
new_node = (NODE *)malloc(sizeof(NODE));
new_node->next = NULL;
printf("\n Enter [%d] node data:", i);
scanf("%d", &new_node->data);
if (list == NULL)
{
list = temp = new_node;
}
else
{
temp->next = new_node;
temp = new_node;
}
}
return list;
}
void display(NODE *list)
{
while (list != NULL)
{
printf("\t%d", list->data);
list = list->next;
}
}
int count(NODE *list)
{
int count = 0;
while (list != NULL)
{
count++;
list = list->next;
}
return count;
}
NODE*insert(NODE*list,int n)
{
NODE*new_node;
new_node=(NODE*)malloc(sizeof(NODE));
new_node->data=n;
new_node->next=list;
list=new_node;
return list;
}
NODE*intersection(NODE*list1,NODE*list2,NODE*list,int n1,int n2)
{
NODE*temp=list1;
NODE*temp1=list2;
int i,j;
for(i=1,temp=list1;i<=n1&&temp!=NULL;i++,temp=temp->next)
{
for(j=1,temp1=list2;j<=n2&&temp1!=NULL;j++,temp1=temp1->next)
{
if (temp->data==temp1->data)
{
list=insert(list,temp->data);
}
}
}
return list;
}
int main()
{
NODE *list = NULL, *list1 = NULL, *list2 = NULL;
int size1, size2;
list = create_list(list);
list1 = create_list(list1);
printf("\n The list is:\n");
display(list);
size1 = count(list);
printf("\n The list is:\n");
display(list1);
size2 = count(list1);
list2 = intersection(list, list1, list2, size1, size2);
printf("\n The intersection is:\n");
display(list2);
getch();
return 0;
}
---------------------------------------------------------------------------------------------
2) Write a C program to divide a singly linked list into two almost equal size lists.
ANS:
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
typedef struct node
{
int data;
struct node *next;
} NODE;
NODE *create_list(NODE *list)
{
NODE *temp = list, *new_node;
int i, n;
printf("\n Enter size of list:");
scanf("%d", &n);
for (i = 1; i <= n; i++)
{
new_node = (NODE *)malloc(sizeof(NODE));
new_node->next = NULL;
printf("\n Enter [%d] node data:", i);
scanf("%d", &new_node->data);
if (list == NULL)
{
list = temp = new_node;
}
else
{
temp->next = new_node;
temp = new_node;
}
}
return list;
}
void display(NODE *list)
{
while (list != NULL)
{
printf("\t%d", list->data);
list = list->next;
}
}
int count(NODE *list)
{
int count = 0;
while (list != NULL)
{
count++;
list = list->next;
}
return count;
}
int main()
{
NODE *list = NULL, *list1 = NULL, *list2 = NULL, *temp;
int size, mid, i;
list = create_list(list);
list1=list;
printf("\n List is:\n");
display(list);
size = count(list);
mid = size / 2;
for(i=1,temp=list;i<mid&&temp!=NULL;i++,temp=temp->next);
list2=temp->next;
temp->next=NULL;
printf("\nFirst list is:\n");
display(list1);
printf("\n Second list is:\n");
display(list2);
getch();
return 0;
}
----------------------------------------------------------------------------
Comments
Post a Comment
Enter comment here!