Suyash Pandey Assignment 3 2020KUEC2045

SUBMITTED BY: SUYASH PANDEY ROLL NO: 2045 Linked List Lab Assignment No. 3 Submitted to: Priyanka Mishra Ma’am Date of Allotment: 5th May 2021 Date of Submission: 11th May 2021 SUBMITTED BY: SUYASH PANDEY ROLL NO: 2045

SUBMITTED BY: SUYASH PANDEY ROLL NO: 2045 Q 1. (A) Write a C program to create a linked list #include <stdio.h> #include <stdlib.h> struct node { int data; struct node* next; }; int main() { struct node* first = NULL; struct node* second = NULL; struct node* third = NULL; first = (struct node*)malloc(sizeof(struct node)); second = (struct node*)malloc(sizeof(struct node)); third = (struct node*)malloc(sizeof(struct node)); first->data = 1; first->next = second; second->data = 2; second->next = third; third->data = 3; third->next = NULL; return 0; } Q 1. (B) Write a C program to search a linked list #include<stdio.h> #include<stdlib.h> #include<stdbool.h> struct Node { int key; struct Node* next; }; void push(struct Node** head_ref, int new_key) { struct Node* new_node = (struct Node*) malloc(sizeof(struct Node)); new_node->key = new_key; SUBMITTED BY: SUYASH PANDEY ROLL NO: 2045

SUBMITTED BY: SUYASH PANDEY ROLL NO: 2045 new_node->next = (*head_ref); (*head_ref) = new_node; } bool search(struct Node* head, int x) { struct Node* current = head; while (current != NULL) { if (current->key == x) return true; current = current->next; } return false; } int main() { struct Node* head = NULL; int x = 45; push(&head, 40); push(&head, 384); push(&head, 983); push(&head, 45); push(&head, 392); search(head, 45)? printf(\"Yes\") : printf(\"No\"); return 0; } Q 1. (C) Write a C program for traversing a linked list #include <stdio.h> #include <stdlib.h> struct node { int data; struct node* next; }; void printList(struct node* n) { while (n != NULL) { printf(\" %d \", n->data); n = n->next; } } SUBMITTED BY: SUYASH PANDEY ROLL NO: 2045

SUBMITTED BY: SUYASH PANDEY ROLL NO: 2045 int main() { struct node* first = NULL; struct node* second = NULL; struct node* third = NULL; first = (struct node*)malloc(sizeof(struct node)); second = (struct node*)malloc(sizeof(struct node)); third = (struct node*)malloc(sizeof(struct node)); first->data = 344; first->next = second; second->data = 667; second->next = third; third->data = 443; third->next = NULL; printList(first); return 0; } Q 1. (D) Write a C program for insertion (at begin, at a given intermediate node, and at the end) #include<stdio.h> #include<stdlib.h> struct Node{ int data; struct Node * next; }; void linkedListTraversal(struct Node *ptr) { while (ptr != NULL) { printf(\"Element: %d\\n\", ptr->data); ptr = ptr->next; } } struct Node * insertAtFirst(struct Node *head, int data){ struct Node * ptr = (struct Node *) malloc(sizeof(struct Node)); ptr->data = data; ptr->next = head; return ptr; } SUBMITTED BY: SUYASH PANDEY ROLL NO: 2045

SUBMITTED BY: SUYASH PANDEY ROLL NO: 2045 struct Node * insertAtIndex(struct Node *head, int data, int index){ struct Node * ptr = (struct Node *) malloc(sizeof(struct Node)); struct Node * p = head; int i = 0; while (i!=index-1) { p = p->next; i++; } ptr->data = data; ptr->next = p->next; p->next = ptr; return head; } struct Node * insertAtEnd(struct Node *head, int data){ struct Node * ptr = (struct Node *) malloc(sizeof(struct Node)); ptr->data = data; struct Node * p = head; while(p->next!=NULL){ p = p->next; } p->next = ptr; ptr->next = NULL; return head; } struct Node * insertAfterNode(struct Node *head, struct Node *prevNode, int data){ struct Node * ptr = (struct Node *) malloc(sizeof(struct Node)); ptr->data = data; ptr->next = prevNode->next; prevNode->next = ptr; return head; } int main(){ struct Node *head; struct Node *second; struct Node *third; struct Node *fourth; head = (struct Node *)malloc(sizeof(struct Node)); second = (struct Node *)malloc(sizeof(struct Node)); third = (struct Node *)malloc(sizeof(struct Node)); fourth = (struct Node *)malloc(sizeof(struct Node)); head->data = 95; head->next = second; SUBMITTED BY: SUYASH PANDEY ROLL NO: 2045

SUBMITTED BY: SUYASH PANDEY ROLL NO: 2045 second->data = 1041; second->next = third; third->data = 687; third->next = fourth; fourth->data = 495; fourth->next = NULL; printf(\"Linked list before insertion\\n\"); linkedListTraversal(head); head = insertAfterNode(head, third, 693); printf(\"\\nLinked list after insertion\\n\"); linkedListTraversal(head); return 0; } Q 1. (E) Write a C program to delete (First node, an intermediate node, and the last node) #include <stdio.h> #include <stdlib.h> struct Node { int data; struct Node *next; }; void linkedListTraversal(struct Node *ptr) { while (ptr != NULL) { printf(\"Element: %d\\n\", ptr->data); ptr = ptr->next; } } struct Node *deleteFirst(struct Node * head){ struct Node * ptr = head; head = head->next; free(ptr); return head; } struct Node *deleteAtIndex(struct Node * head, int index){ struct Node *p = head; struct Node *q = head->next; for (int i = 0; i < index-1; i++) SUBMITTED BY: SUYASH PANDEY ROLL NO: 2045

SUBMITTED BY: SUYASH PANDEY ROLL NO: 2045 { p = p->next; q = q->next; } p->next = q->next; free(q); return head; } struct Node *deleteAtLast(struct Node * head){ struct Node *p = head; struct Node *q = head->next; while(q->next !=NULL) { p = p->next; q = q->next; } p->next = NULL; free(q); return head; } struct Node *deleteAtkey(struct Node * head, int value){ struct Node *p = head; struct Node *q = head->next; while(q->data!=value && q->next!= NULL) { p = p->next; q = q->next; } if(q->data == value){ p->next = q->next; free(q); } return head; } int main() { struct Node *head; struct Node *second; struct Node *third; struct Node *fourth; head = (struct Node *)malloc(sizeof(struct Node)); second = (struct Node *)malloc(sizeof(struct Node)); third = (struct Node *)malloc(sizeof(struct Node)); fourth = (struct Node *)malloc(sizeof(struct Node)); SUBMITTED BY: SUYASH PANDEY ROLL NO: 2045

SUBMITTED BY: SUYASH PANDEY ROLL NO: 2045 head->data = 4473; head->next = second; second->data = 30985; second->next = third; third->data =10088; third->next = fourth; fourth->data = 968; fourth->next = NULL; printf(\"Linked list before deletion\\n\"); linkedListTraversal(head); head = deleteAtLast(head); printf(\"Linked list after deletion\\n\"); linkedListTraversal(head); return 0; } Q 2. Write a C program for find the middle element of a given linked list in C #include<stdio.h> #include<stdlib.h> struct Node { int data; struct Node* next; }; void printMiddle(struct Node *head) { struct Node *slow_ptr = head; struct Node *fast_ptr = head; if (head!=NULL) { while (fast_ptr != NULL && fast_ptr->next != NULL) { fast_ptr = fast_ptr->next->next; slow_ptr = slow_ptr->next; } printf(\"The middle element is [%d]\\n\\n\", slow_ptr->data); } } SUBMITTED BY: SUYASH PANDEY ROLL NO: 2045

SUBMITTED BY: SUYASH PANDEY ROLL NO: 2045 void push(struct Node** head_ref, int new_data) { struct Node* new_node = (struct Node*) malloc(sizeof(struct Node)); new_node->data = new_data; new_node->next = (*head_ref); (*head_ref) = new_node; } void printList(struct Node *ptr) { while (ptr != NULL) { printf(\"%d->\", ptr->data); ptr = ptr->next; } printf(\"NULL\\n\"); } int main() { struct Node* head = NULL; int i; for (i=5; i>0; i--) { push(&head, i); printList(head); printMiddle(head); } return 0; } Q 3. Write a program for printing the nth node from the end of a linked list #include <stdio.h> #include <stdlib.h> struct Node { int data; SUBMITTED BY: SUYASH PANDEY ROLL NO: 2045

SUBMITTED BY: SUYASH PANDEY ROLL NO: 2045 struct Node *next; }; int count = 0; void linkedlisttraversal(struct Node *ptr) { while (ptr != NULL) { printf(\"%d \", ptr->data); ptr = ptr->next; count++; } } int nthfromlast(struct Node *head, int n) { struct Node *ptr = head; if (n== count) { int x; x = head->data; return x; } else { int pos = count - n + 1; int index = pos - 1; int i = 0; while (i < index - 1) { ptr = ptr->next; i++; } ptr = ptr->next; int x = ptr->data; return x; } } struct Node *Insertatend(struct Node *head, int req) { struct Node *ptr = (struct Node *)malloc(sizeof(struct Node)); struct Node *p = head; while (p->next != NULL) { p = p->next; } ptr->data = req; ptr->next = p->next; SUBMITTED BY: SUYASH PANDEY ROLL NO: 2045

SUBMITTED BY: SUYASH PANDEY ROLL NO: 2045 p->next = ptr; return head; } int main() { struct Node *head = (struct Node *)malloc(sizeof(struct Node)); head->data = 1; head->next = NULL; Insertatend(head, 43); Insertatend(head, 69); Insertatend(head, 3939); Insertatend(head, 9873); Insertatend(head, 1048576); Insertatend(head, 1392); linkedlisttraversal(head); int n; printf(\"\\nEnter the node from the end which you want to access\\n\"); scanf(\"%d\", &n); printf(\"Nth node from end is : %d\\n\", nthfromlast(head, n)); return 0; } Q.4. Reverse a linked list #include <stdio.h> #include <stdlib.h> struct Node { int data; struct Node *next; }; void linklisttraversal(struct Node *ptr) { while (ptr != NULL) { printf(\"Element: %d\\n\", ptr->data); ptr = ptr->next; } } void *linklist_reversal(struct Node *head) SUBMITTED BY: SUYASH PANDEY ROLL NO: 2045

SUBMITTED BY: SUYASH PANDEY ROLL NO: 2045 { struct Node *current= head; struct Node *nodenext; struct Node *pre=NULL; while(current!=NULL) { nodenext=current->next; current->next=pre; pre=current; current=nodenext; } return pre; } int main() { struct Node *head; struct Node *second; struct Node *third; struct Node *fourth; head = (struct Node *)malloc(sizeof(struct Node)); second = (struct Node *)malloc(sizeof(struct Node)); third = (struct Node *)malloc(sizeof(struct Node)); fourth = (struct Node *)malloc(sizeof(struct Node)); head->data = 7; head->next = second; second->data = 56; second->next = third; third->data = 766; third->next = fourth; fourth->data = 94; fourth->next = NULL; linklisttraversal(head); head = linklist_reversal(head); printf(\"After reversing\\n\"); linklisttraversal(head); return 0; } SUBMITTED BY: SUYASH PANDEY ROLL NO: 2045

SUBMITTED BY: SUYASH PANDEY ROLL NO: 2045 Q 5. Write a program to split a given linked list #include <stdio.h> #include <stdlib.h> struct node { int data; struct node *next; }; struct node *ptr = NULL; struct node *create(struct node *head, int n) { struct node *temp = NULL; ptr = head; for (int i = 0; i < n; i++) { if (ptr == NULL) { printf(\"Enter element %d \\n\",i+1); head = (struct node *)malloc(sizeof(struct node)); ptr = head; scanf(\"%d\", &ptr->data); } else { printf(\"Enter element %d \\n\",i+1); ptr->next = (struct node *)malloc(sizeof(struct node)); ptr = ptr->next; scanf(\"%d\", &ptr->data); temp = ptr; if ((i + 1) == n) { ptr->next = NULL; } } } temp = head; return temp; } struct node *split(struct node *head, int n) { struct node *p; p = head; SUBMITTED BY: SUYASH PANDEY ROLL NO: 2045

SUBMITTED BY: SUYASH PANDEY ROLL NO: 2045 ptr = head; int i = 0; while (i < n) { if (i % 2 == 0) { printf(\"Even: %d \\n\", p->data); } p = p->next; i++; } printf(\"\\n\"); i = 0; while (i < n) { if (i % 2 != 0) { printf(\"Odd: %d \\n\", ptr->data); } ptr = ptr->next; i++; } return NULL; } void traversal(struct node *head) { ptr = head; while (ptr != NULL) { printf(\"Element: %d \\n\", ptr->data); ptr = ptr->next; } } int main() { int n; printf(\"Enter the required number of nodes in the linked list \\n\"); scanf(\"%d\", &n); struct node *head = NULL; head = create(head, n); ptr = split(head, n); return 0; } SUBMITTED BY: SUYASH PANDEY ROLL NO: 2045

SUBMITTED BY: SUYASH PANDEY ROLL NO: 2045 Q 6. Count the number of nodes in a linked list #include <stdio.h> #include <stdlib.h> struct node { int data; struct node *next; }*head; void createList(int n); int countNodes(); void displayList(); int main() { int n, total; printf(\"Enter the total number of nodes: \"); scanf(\"%d\", &n); createList(n); printf(\"\\nData in the list \\n\"); displayList(); total = countNodes(); printf(\"\\nTotal number of nodes = %d\\n\", total); return 0; } void createList(int n) { struct node *newNode, *temp; int data, i; head = (struct node *)malloc(sizeof(struct node)); if(head == NULL) SUBMITTED BY: SUYASH PANDEY ROLL NO: 2045

SUBMITTED BY: SUYASH PANDEY ROLL NO: 2045 { printf(\"Unable to allocate memory.\"); } else { printf(\"Enter the data of node 1: \"); scanf(\"%d\", &data); head->data = data; head->next = NULL; temp = head; for(i=2; i<=n; i++) { newNode = (struct node *)malloc(sizeof(struct node)); if(newNode == NULL) { printf(\"Unable to allocate memory.\"); break; } else { printf(\"Enter the data of node %d: \", i); scanf(\"%d\", &data); newNode->data = data; newNode->next = NULL; temp->next = newNode; temp = temp->next; } } } } int countNodes() { int count = 0; struct node *temp; temp = head; SUBMITTED BY: SUYASH PANDEY ROLL NO: 2045

SUBMITTED BY: SUYASH PANDEY ROLL NO: 2045 while(temp != NULL) { count++; temp = temp->next; } return count; } void displayList() { struct node *temp; if(head == NULL) { printf(\"List is empty.\"); } else { temp = head; while(temp != NULL) { printf(\"Data = %d\\n\", temp->data); temp = temp->next; } } } Q 7. Search an element in a Linked List #include<stdio.h> #include<stdlib.h> #include<stdbool.h> struct Node { int key; struct Node* next; }; void push(struct Node** head_ref, int new_key) { SUBMITTED BY: SUYASH PANDEY ROLL NO: 2045

SUBMITTED BY: SUYASH PANDEY ROLL NO: 2045 struct Node* new_node = (struct Node*) malloc(sizeof(struct Node)); new_node->key = new_key; new_node->next = (*head_ref); (*head_ref) = new_node; } bool search(struct Node* head, int x) { struct Node* current = head; while (current != NULL) { if (current->key == x) return true; current = current->next; } return false; } int main() { struct Node* head = NULL; int x = 49; push(&head, 9); push(&head, 30); push(&head, 51); push(&head, 49); push(&head, 76); search(head, x)? printf(\"Yes\") : printf(\"No\"); printf(\"\\n\"); return 0; } Q 8. Swap two elements of given index positions in a linked list #include <stdio.h> #include <stdlib.h> struct Node SUBMITTED BY: SUYASH PANDEY ROLL NO: 2045

SUBMITTED BY: SUYASH PANDEY ROLL NO: 2045 { int data; struct Node *next; }; int count = 0; void linkedlisttraversal(struct Node *ptr) { while (ptr != NULL) { printf(\"%d \", ptr->data); ptr = ptr->next; count++; } } void swapping(struct Node * head , int i1 , int i2) { struct Node * p1 = head; struct Node * p2 = head; int i =0; while (i<i1) { p1 = p1->next; i++; } int j =0; while (j<i2) { p2 = p2->next; j++; } int temp; temp = p1->data; p1->data = p2->data; p2->data = temp; } struct Node *Insertatend(struct Node *head, int req) { struct Node *ptr = (struct Node *)malloc(sizeof(struct Node)); struct Node *p = head; while (p->next != NULL) { p = p->next; } ptr->data = req; ptr->next = p->next; p->next = ptr; SUBMITTED BY: SUYASH PANDEY ROLL NO: 2045

SUBMITTED BY: SUYASH PANDEY ROLL NO: 2045 return head; } int main() { struct Node *head = (struct Node *)malloc(sizeof(struct Node)); head->data = 1; head->next = NULL; Insertatend(head, 63); Insertatend(head, 71); Insertatend(head, 82); Insertatend(head, 45); Insertatend(head, 93); Insertatend(head, 100); int i1,i2; printf(\"Enter the two indices\\n\"); scanf(\"%d%d\",&i1,&i2); printf(\"Linked List before swapping:\\n\"); linkedlisttraversal(head); swapping(head,i1,i2); printf(\"\\n\"); printf(\"\\nLinked List after swapping:\\n\"); linkedlisttraversal(head); printf(\"\\n\"); return 0; } Q 9. WAP to swap pairwise elements of a given linked list #include <stdio.h> #include <stdlib.h> struct Node { int data; struct Node* next; }; void swap(int* a, int* b); void pairWiseSwap(struct Node* head) { struct Node* temp = head; while (temp != NULL && temp->next != NULL) { swap(&temp->data, &temp->next->data); SUBMITTED BY: SUYASH PANDEY ROLL NO: 2045

SUBMITTED BY: SUYASH PANDEY ROLL NO: 2045 temp = temp->next->next; } } void swap(int* a, int* b) { int temp; temp = *a; *a = *b; *b = temp; } void push(struct Node** head_ref, int new_data) { struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); new_node->data = new_data; new_node->next = (*head_ref); (*head_ref) = new_node; } void printList(struct Node* node) { while (node != NULL) { printf(\"%d \", node->data); node = node->next; } } int main() { struct Node* start = NULL; push(&start, 5); push(&start, 4); push(&start, 3); push(&start, 2); push(&start, 1); printf(\"Linked list before calling pairWiseSwap()\\n\"); printList(start); pairWiseSwap(start); printf(\"\\nLinked list after calling pairWiseSwap()\\n\"); printList(start); return 0; SUBMITTED BY: SUYASH PANDEY ROLL NO: 2045

SUBMITTED BY: SUYASH PANDEY ROLL NO: 2045 } Q 10. WAP to move last element to front of a given linked list #include<stdio.h> #include<stdlib.h> struct Node { int data; struct Node *next; }; void moveToFront(struct Node **head_ref) { if (*head_ref == NULL || (*head_ref)->next == NULL) return; struct Node *secLast = NULL; struct Node *last = *head_ref; while (last->next != NULL) { secLast = last; last = last->next; } secLast->next = NULL; last->next = *head_ref; *head_ref = last; } void push(struct Node** head_ref, int new_data) { struct Node* new_node = (struct Node*) malloc(sizeof(struct Node)); new_node->data = new_data; new_node->next = (*head_ref); (*head_ref) = new_node; } void printList(struct Node *node) { while(node != NULL) { printf(\"%d \", node->data); node = node->next; } } SUBMITTED BY: SUYASH PANDEY ROLL NO: 2045

SUBMITTED BY: SUYASH PANDEY ROLL NO: 2045 int main() { struct Node *start = NULL; push(&start, 99); push(&start, 100); push(&start, 101); push(&start, 102); push(&start, 103); printf(\"Linked list before moving last to front\\n\"); printList(start); moveToFront(&start); printf(\"\\nLinked list after removing last to front\\n\"); printList(start); return 0; } SUBMITTED BY: SUYASH PANDEY ROLL NO: 2045