Assignment No 5: Linked List
Practice Set
1) Write a C Program to find largest element of doubly linked list.
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <string.h>
typedef struct node
{
int data;
struct node *next, *prev;
} D_NODE;
D_NODE *createList(D_NODE *list);
void display(D_NODE *list);
int findLarge(D_NODE *list);
int main()
{
D_NODE *list = NULL;
int l;
list = createList(list);
display(list);
l = findLarge(list);
printf("\nThe largest value in Doubly
Linked List is = %d\n", l);
getch();
return 0;
}
D_NODE *createList(D_NODE *list)
{
D_NODE *newNode, *temp;
int n, i;
printf("Enter how many node
\n");
scanf("%d", &n);
for (i = 1; i <= n; i++)
{
newNode = (D_NODE
*)malloc(sizeof(D_NODE));
newNode->next = NULL;
newNode->prev = NULL;
printf("Enter the data
for %d node : ", i);
scanf("%d",
&newNode->data);
if (list == NULL)
{
list = temp = newNode;
list->prev = NULL;
}
else
{
temp->next = newNode;
newNode->prev = temp;
temp = newNode;
}
}
return list;
}
void display(D_NODE *list)
{
D_NODE *temp = list;
do
{
printf("%d \t",
temp->data);
temp = temp->next;
} while (temp != NULL);
}
int findLarge(D_NODE *list)
{
D_NODE *temp = list;
int max = temp->data;
while (temp != NULL)
{
if (temp->data > max)
{
max = temp->data;
}
else
{
temp = temp->next;
}
}
return max;
}
=================================================================
2.Write a C Program to interchange the two adjacent nodes in given circular
linked list.
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <string.h>
typedef struct node
{
int data;
struct node *next;
} Node;
Node *createList(Node *list);
void display(Node *list);
Node *interchangeAdj(Node *list, int n);
int main()
{
Node *head = NULL;
int pos;
head = createList(head);
display(head);
printf("\nEnter the position
to interchange of nodes : \n");
scanf("%d", &pos);
head = interchangeAdj(head, pos);
display(head);
getch();
return 0;
}
Node *createList(Node *list)
{
int i, n;
Node *temp, *newNode, *t;
printf("Enter the how many
node : \n");
scanf("%d", &n);
for (i = 0; i < n; i++)
{
newNode = (Node
*)malloc(sizeof(Node));
newNode->next = NULL;
printf("Enter the data
of %d node : ", i + 1);
scanf("%d", &newNode->data);
if (list == NULL)
{
list = temp = newNode;
}
else
{
temp->next = newNode;
newNode->next = list;
temp = newNode;
}
}
return list;
}
void display(Node *list)
{
Node *temp = list;
do
{
printf("%d \t",
list->data);
list = list->next;
} while (list != temp);
}
Node *interchangeAdj(Node *list, int n)
{
Node *temp, *temp1, *temp2;
int i;
for (i = 1, temp = list; i < n
- 1 && temp != NULL; i++, temp = temp->next)
;
temp1 = temp->next;
temp2 = temp1->next;
temp->next = temp2;
temp1->next = temp2->next;
temp2->next = temp1;
return list;
}
=============================================================
3) Write C Program to find length of linked list without using recursion.
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <string.h>
typedef struct node
{
int data;
struct node *next;
} Node;
Node *createList(Node *list);
void display(Node *list);
int k = 0;
int main()
{
Node *head = NULL;
int len;
head = createList(head);
display(head);
// len = lengthList(head);
printf("\n The length of
Linked List is %d \n", k);
return 0;
}
Node *createList(Node *list)
{
int i, n;
Node *temp, *newNode, *t;
printf("Enter the how many
node : \n");
scanf("%d", &n);
for (i = 0; i < n; i++)
{
newNode = (Node
*)malloc(sizeof(Node));
newNode->next = NULL;
printf("Enter the data
of %d node : ", i + 1);
scanf("%d",
&newNode->data);
if (list == NULL)
{
list = temp = newNode;
}
else
{
temp->next = newNode;
newNode->next = list;
temp = newNode;
}
}
return list;
}
void display(Node *list)
{
Node *temp = list;
do
{
printf("%d \t",
list->data);
list = list->next;
k++;
} while (list != temp);
}
===========================================================
4) Write C Program to print alternative nodes in linked list using
recursion.
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <string.h>
typedef struct node
{
int data;
struct node *next;
} Node;
Node *createList(Node *list);
void displayList(Node *list);
void printAlternate(Node *list);
int main()
{
Node *head = NULL;
head = createList(head);
printAlternate(head);
getch();
return 0;
}
Node *createList(Node *list)
{
int n, value;
Node *newNode, *temp;
printf("Enter the Size of
Node : ");
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
newNode = (Node
*)malloc(sizeof(Node));
printf("\nEnter the data
for %d node : ", i + 1);
scanf("%d",
&value);
newNode->data = value;
newNode->next = NULL;
if (list == NULL)
{
list = temp = newNode;
}
else
{
temp->next = newNode;
temp = newNode;
}
}
return list;
}
void printAlternate(Node *list)
{
if (list == NULL)
{
return;
}
printf("%d\t",
list->data);
if (list->next != NULL)
{
printAlternate(list->next->next);
}
}
void displayList(Node *list)
{
Node *temp = list;
printf("Linked list is :
\n");
while (temp != NULL)
{
printf("%d\t",
temp->data);
temp = temp->next;
}
}
=====================================================================
SET A:
1) Write a C program to implement a singly linked list with Create and
Display operation
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <string.h>
typedef struct node
{
int data;
struct node *next;
} Node;
Node *createList(Node *list);
void displayList(Node *list);
int main()
{
Node *head = NULL;
head = createList(head);
displayList(head);
getch();
return 0;
}
Node *createList(Node *list)
{
int n, value;
Node *newNode, *temp;
printf("Enter the Size of
Node : ");
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
newNode = (Node
*)malloc(sizeof(Node));
printf("\nEnter the data
for %d node : ", i + 1);
scanf("%d",
&value);
newNode->data = value;
newNode->next = NULL;
if (list == NULL)
{
list = temp = newNode;
}
else
{
temp->next = newNode;
temp = newNode;
}
}
return list;
}
void displayList(Node *list)
{
Node *temp = list;
printf("Linked list is :
\n");
while (temp != NULL)
{
printf("%d\t",
temp->data);
temp = temp->next;
}
}
====================================================
2) Write a C program to implement a Circular Singly linked list with Create
and Display
operation.
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <string.h>
typedef struct node
{
int data;
struct node *next;
} Node;
Node *createList(Node *list);
void displayList(Node *list);
int main()
{
Node *head = NULL;
head = createList(head);
displayList(head);
getch();
return 0;
}
Node *createList(Node *list)
{
int n, value;
Node *newNode, *temp;
printf("Enter the Size of
Node : ");
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
newNode = (Node
*)malloc(sizeof(Node));
printf("\nEnter the data
for %d node : ", i + 1);
scanf("%d",
&value);
newNode->data = value;
newNode->next = NULL;
if (list == NULL)
{
list = temp = newNode;
}
else
{
temp->next = newNode;
temp = newNode;
}
}
temp->next = list;
return list;
}
void displayList(Node *list)
{
Node *temp = list;
printf("Linked list is :
\n");
do
{
printf("%d\t",
temp->data);
temp = temp->next;
} while (temp != list);
}
=======================================================
3) Write a C program to implement a doubly linked list with Create and
Display operation
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <string.h>
typedef struct node
{
int data;
struct node *next, *prev;
} D_NODE;
D_NODE *createList(D_NODE *list);
void display(D_NODE *list);
int main()
{
D_NODE *head = NULL;
head = createList(head);
display(head);
getch();
return 0;
}
D_NODE *createList(D_NODE *list)
{
D_NODE *newNode, *temp;
int n, i;
printf("Enter how many node
\n");
scanf("%d", &n);
for (i = 1; i <= n; i++)
{
newNode = (D_NODE
*)malloc(sizeof(D_NODE));
newNode->next = NULL;
newNode->prev = NULL;
printf("Enter the data
for %d node : ", i);
scanf("%d",
&newNode->data);
if (list == NULL)
{
list = temp = newNode;
list->prev = NULL;
}
else
{
temp->next = newNode;
newNode->prev = temp;
temp = newNode;
}
}
return list;
}
void display(D_NODE *list)
{
D_NODE *temp = list;
do
{
printf("%d \t",
temp->data);
temp = temp->next;
} while (temp != NULL);
}
================================================
4) Write a C program to implement a Circular doubly linked list with Create
and Display
operation
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <string.h>
typedef struct node
{
int data;
struct node *next, *prev;
} D_NODE;
D_NODE *createList(D_NODE *list);
void display(D_NODE *list);
int main()
{
D_NODE *head = NULL;
head = createList(head);
display(head);
getch();
return 0;
}
D_NODE *createList(D_NODE *list)
{
D_NODE *temp, *newNode;
int i, n;
printf("Enter the how many
nodes : \n");
scanf("%d", &n);
for (i = 1; i <= n; i++)
{
newNode = (D_NODE
*)malloc(sizeof(D_NODE));
newNode->next = NULL;
newNode->prev = NULL;
printf("Enter the data
for %d node : \n", i);
scanf("%d",
&newNode->data);
if (list == NULL)
{
list = temp = newNode;
list->next = list;
list->prev = list;
}
else
{
temp->next = newNode;
newNode->prev = temp;
temp = newNode;
}
}
return list;
}
void display(D_NODE *list)
{
D_NODE *temp = list;
printf("Linked List is
\n");
do
{
printf("%d \t",
temp->data);
temp = temp->next;
} while (temp != 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
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <string.h>
typedef struct node
{
int data;
struct node *next;
} Node;
Node *createList(Node *list);
void displayList(Node *list);
int countNode(Node *list);
Node *insertBeg(Node *list, int value);
Node *reverseList(Node *list);
int main()
{
Node *head = NULL, *list2 = NULL;
int node_cnt, value;
head = createList(head);
node_cnt = countNode(head);
printf("Total node is = %d
\n", node_cnt);
printf("Enter the insert
value : \n");
scanf("%d",
&value);
head = insertBeg(head, value);
displayList(head);
printf("Before Reverse
Linked List is : \n");
displayList(head);
list2 = reverseList(head);
printf("After Reverse Linked
List is : \n");
displayList(list2);
getch();
return 0;
}
Node *createList(Node *list)
{
int n, value;
Node *newNode, *temp;
printf("Enter the Size of
Node : \n");
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
newNode = (Node
*)malloc(sizeof(Node));
printf("Enter the data
for %d node : \n", i + 1);
scanf("%d",
&value);
newNode->data = value;
newNode->next = NULL;
if (list == NULL)
{
list = temp = newNode;
}
else
{
temp->next = newNode;
temp = newNode;
}
}
return list;
}
void displayList(Node *list)
{
Node *temp = list;
printf("Linked list is :
\n");
while (temp != NULL)
{
printf("%d\t",
temp->data);
temp = temp->next;
}
printf("\n");
}
int countNode(Node *list)
{
Node *temp = list;
int node_cnt = 0;
while (temp != NULL)
{
node_cnt++;
temp = temp->next;
}
return node_cnt;
}
Node *insertBeg(Node *list, int value)
{
Node *temp = list, *new_node;
new_node = (Node
*)malloc(sizeof(Node));
new_node->data = value;
new_node->next = list;
list = new_node;
return list;
}
Node *reverseList(Node *list)
{
Node *temp, *newNode, *list2 =
NULL;
for (temp = list; temp != NULL;
temp = temp->next)
{
newNode = (Node
*)malloc(sizeof(Node));
newNode->data =
temp->data;
newNode->next = NULL;
if (list2 == NULL)
{
list2 = newNode;
}
else
{
newNode->next = list2;
list2 = newNode;
}
}
return list2;
}
=======================================================
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
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <string.h>
typedef struct node
{
int data;
struct node *next;
} Node;
Node *createList(Node *list);
void displayList(Node *list);
int search(Node *list, int value);
Node *swap(Node *list, int idx1, int idx2);
Node *deletePos(Node *list, int pos);
int main()
{
Node *head = NULL;
int choice, num, pos, result,
idx1, idx2;
printf("Create the Linked
List :\n");
head = createList(head);
displayList(head);
do
{
printf("\n--------- Menu
Bar ---------\n");
printf("1. Search the
Number in Linked List : \n");
printf("2. Swap mth and
nth element : \n");
printf("3. delete node
from specific position : \n");
printf("4. Exit
\n");
printf("--------- End
-------------- \n");
printf("Enter your
choice : \n");
scanf("%d",
&choice);
switch (choice)
{
case 1:
printf("Enter the
search value :\n");
scanf("%d",
&num);
result = search(head,
num);
if (result < 0)
{
printf("The
element is not found !!\n");
}
else
{
printf("The
element is found at %d index !!\n", result);
}
break;
case 2:
printf("Enter the first index :
\n");
scanf("%d",
&idx1);
printf("Enter the
second index : \n");
scanf("%d",
&idx2);
head = swap(head, idx1,
idx2);
displayList(head);
break;
case 3:
printf("Enter the
position : \n");
scanf("%d",
&pos);
head = deletePos(head,
pos);
printf("After Delete
element linked lins is : \n");
displayList(head);
break;
case 4:
exit(0);
break;
default:
printf("Wrong choice
\n");
break;
}
} while (choice != 4);
getch();
return 0;
}
Node *createList(Node *list)
{
int n, value;
Node *newNode, *temp;
printf("Enter the Size of
Node : \n");
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
newNode = (Node
*)malloc(sizeof(Node));
printf("Enter the data
for %d node : \n", i + 1);
scanf("%d",
&value);
newNode->data = value;
newNode->next = NULL;
if (list == NULL)
{
list = temp = newNode;
}
else
{
temp->next = newNode;
temp = newNode;
}
}
return list;
}
void displayList(Node *list)
{
Node *temp = list;
printf("Linked list is :
\n");
if (list == NULL)
{
printf("List is Empty !!
\n");
}
else
{
while (temp != NULL)
{
printf("%d\t",
temp->data);
temp = temp->next;
}
}
printf("\n");
}
int search(Node *list, int value)
{
Node *temp = list;
int i = 0;
while (temp != NULL)
{
if (temp->data == value)
{
return i;
}
temp = temp->next;
i++;
}
return -1;
}
Node *swap(Node *list, int idx1, int idx2)
{
Node *temp1 = list, *temp2 =
list;
int i, j, data;
i = 1;
while (temp1 != NULL && i
<= idx1 - 1)
{
temp1 = temp1->next;
i++;
}
j = 1;
while (temp2 != NULL && j
<= idx2 - 1)
{
temp2 = temp2->next;
j++;
}
if (temp1 == NULL || temp2 ==
NULL)
{
printf("You entered
index is out of range !! \n");
}
else
{
data = temp2->data;
temp2->data = temp1->data;
temp1->data = data;
}
return list;
}
Node *deletePos(Node *list, int pos)
{
Node *temp = list, *temp2 = list;
int i = 1;
while (temp != NULL && i
< pos - 1)
{
temp = temp->next;
i++;
}
i = 1;
while (temp2 != NULL && i
< pos)
{
temp2 = temp2->next;
i++;
}
temp->next = temp2->next;
free(temp2);
return list;
}
==========================================================
3) Write a ‘C’ program to sort elements of a singly linked list in
ascending order and display the sorted List.
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <string.h>
typedef struct node
{
int data;
struct node *next;
} Node;
int n;
Node *createList(Node *list);
void displayList(Node *list);
Node *bubbleSort(Node *list, int size);
int main()
{
Node *head = NULL;
head = createList(head);
head = bubbleSort(head, n);
displayList(head);
getch();
return 0;
}
Node *createList(Node *list)
{
int value;
Node *newNode, *temp;
printf("Enter the Size of
Node : \n");
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
newNode = (Node
*)malloc(sizeof(Node));
printf("Enter the data
for %d node : \n", i + 1);
scanf("%d",
&value);
newNode->data = value;
newNode->next = NULL;
if (list == NULL)
{
list = temp = newNode;
}
else
{
temp->next = newNode;
temp = newNode;
}
}
return list;
}
void displayList(Node *list)
{
Node *temp = list;
printf("Linked list is :
\n");
while (temp != NULL)
{
printf("%d\t",
temp->data);
temp = temp->next;
}
printf("\n");
}
Node *bubbleSort(Node *list, int size)
{
Node *temp = list, *temp2 = NULL;
int data;
if (list == NULL)
{
return list;
}
else
{
while (temp != NULL)
{
temp2 = temp->next;
while (temp2 != NULL)
{
if (temp->data
> temp2->data)
{
data =
temp->data;
temp->data =
temp2->data;
temp2->data =
data;
}
temp2 =
temp2->next;
}
temp = temp->next;
}
}
return list;
}
===========================================================
SET C :
1) Write a C program to find intersection of two singly linked lists.
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <string.h>
typedef struct node
{
int data;
struct node *next;
} Node;
Node *createList(Node *list);
void displayList(Node *list);
Node *interSection(Node *list1, Node *list2);
Node *insert(Node *list, int data);
int main()
{
Node *list1 = NULL, *list2 =
NULL, *list3 = NULL;
list1 = createList(list1);
displayList(list1);
printf("\nEnter data into
list 2 : \n");
list2 = createList(list2);
displayList(list2);
printf("\n Intersection of
two linked list \n");
list3 = interSection(list1,
list2);
displayList(list3);
getch();
return 0;
}
Node *createList(Node *list)
{
int n, value;
Node *newNode, *temp;
printf("Enter the Size of
Node : \n");
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
newNode = (Node
*)malloc(sizeof(Node));
printf("Enter the data
for %d node : ", i + 1);
scanf("%d",
&value);
newNode->data = value;
newNode->next = NULL;
if (list == NULL)
{
list = temp = newNode;
}
else
{
temp->next = newNode;
temp = newNode;
}
}
return list;
}
void displayList(Node *list)
{
Node *temp = list;
printf("Linked list is :
\n");
if (list == NULL)
{
printf("The list is
Empty : \n");
}
else
{
while (temp != NULL)
{
printf("%d\t",
temp->data);
temp = temp->next;
}
}
printf("\n");
}
Node *interSection(Node *list1, Node *list2)
{
Node *temp1 = list1;
Node *list3 = NULL;
Node *temp2 = list2;
while (temp1 != NULL)
{
while (temp2 != NULL)
{
if (temp1->data ==
temp2->data)
{
list3 = insert(list3,
temp1->data);
break;
}
temp2 = temp2->next;
}
temp1 = temp1->next;
}
return list3;
}
Node *insert(Node *list, int num)
{
Node *new_node = (Node
*)malloc(sizeof(Node));
new_node->data = num;
new_node->next = NULL;
if (list == NULL)
{
list = new_node;
}
else
{
Node *temp = list;
while (temp->next != NULL)
{
temp = temp->next;
}
temp->next = new_node;
}
return list;
}
==============================================================
2) Write a C program to divide a singly linked list into two almost equal
size lists.
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <string.h>
typedef struct node
{
int data;
struct node *next;
} Node;
Node *createList(Node *list);
void displayList(Node *list);
Node *divideList(Node *list);
int countNode(Node *list);
int main()
{
Node *head = NULL, *head2 = NULL;
head = createList(head);
displayList(head);
head2 = divideList(head);
printf("Divide List is :
\n");
displayList(head);
displayList(head2);
getch();
return 0;
}
Node *createList(Node *list)
{
int n, value;
Node *newNode, *temp;
printf("Enter the Size of
Node : \n");
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
newNode = (Node
*)malloc(sizeof(Node));
printf("Enter the data
for %d node : ", i + 1);
scanf("%d",
&value);
newNode->data = value;
newNode->next = NULL;
if (list == NULL)
{
list = temp = newNode;
}
else
{
temp->next = newNode;
temp = newNode;
}
}
return list;
}
void displayList(Node *list)
{
Node *temp = list;
printf("Linked list is :
\n");
if (list == NULL)
{
printf("The list is
Empty : \n");
}
else
{
while (temp != NULL)
{
printf("%d\t",
temp->data);
temp = temp->next;
}
}
printf("\n");
}
Node *divideList(Node *list)
{
int cnt = countNode(list);
Node *temp = list, *list2 = NULL;
int div = cnt / 2;
for (int i = 1; i < div; i++)
{
temp = temp->next;
}
list2 = temp->next;
temp->next = NULL;
return list2;
}
int countNode(Node *list)
{
int cnt = 0;
Node *temp = list;
while (temp != NULL)
{
temp = temp->next;
cnt++;
}
return cnt;
}
====================================================
0 Comments