NEP-SYBCS-DS-I Assignment -4

 Assignment 4 Singly Linked List

Set A
a) Write a menu driven program for the following operations.
i. Insert an element in a linked list in a particular position
ii. Search an element in a linked list.
iii. Delete a particular element from a linked list.
 #include <stdio.h>

#include <stdlib.h>

struct node

{

    int data;

    struct node *next;

};

struct node *head = NULL;

// Insert at a particular position

void insert()

{

    struct node *newnode, *temp;

    int data, pos, i;

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

    printf("Enter data: ");

    scanf("%d", &data);

    newnode->data = data;

    newnode->next = NULL;

    printf("Enter position: ");

    scanf("%d", &pos);

    if (pos == 1)

    {

        newnode->next = head;

        head = newnode;

        return;

    }

    temp = head;

    for (i = 1; i < pos - 1 && temp != NULL; i++)

        temp = temp->next;

    if (temp == NULL)

    {

        printf("Invalid Position\n");

        free(newnode);

        return;

    }

    newnode->next = temp->next;

    temp->next = newnode;

    printf("Node Inserted Successfully.\n");

}

// Search an element

void search()

{

    struct node *temp = head;

    int key, pos = 1;

    printf("Enter element to search: ");

    scanf("%d", &key);

    while (temp != NULL)

    {

        if (temp->data == key)

        {

            printf("Element found at position %d\n", pos);

            return;

        }

        temp = temp->next;

        pos++;

    }

    printf("Element not found.\n");

}

// Delete a particular element

void deleteNode()

{

    struct node *temp = head, *prev = NULL;

    int key;

    printf("Enter element to delete: ");

    scanf("%d", &key);

    while (temp != NULL && temp->data != key)

    {

        prev = temp;

        temp = temp->next;

    }

    if (temp == NULL)

    {

        printf("Element not found.\n");

        return;

    }

    if (prev == NULL)

        head = temp->next;

    else

        prev->next = temp->next;

    free(temp);

    printf("Element deleted successfully.\n");

}

// Display linked list

void display()

{

    struct node *temp = head;

    if (head == NULL)

    {

        printf("List is Empty.\n");

        return;

    }

    printf("Linked List: ");

    while (temp != NULL)

    {

        printf("%d -> ", temp->data);

        temp = temp->next;

    }

    printf("NULL\n");

}

int main()

{

    int choice;

    while (1)

    {

        printf("\n----- MENU -----\n");

        printf("1. Insert at Particular Position\n");

        printf("2. Search Element\n");

        printf("3. Delete Element\n");

        printf("4. Display List\n");

        printf("5. Exit\n");

        printf("Enter your choice: ");

        scanf("%d", &choice);

        switch (choice)

        {

            case 1:

                insert();

                break;

            case 2:

                search();

                break;

            case 3:

                deleteNode();

                break;

            case 4:

                display();

                break;

            case 5:

                exit(0);

            default:

                printf("Invalid Choice!\n");

        }

    }

    return 0;

}

b) Write a menu driven program for the following operations.
i. Reverse a linked list and display it.
ii. Accept an element from user and Concatenate it with a created link list.
iii. Merge two linked list and display it.

#include <stdio.h>

#include <stdlib.h>

struct node

{

    int data;

    struct node *next;

};

struct node *head1 = NULL, *head2 = NULL;

// Create a linked list

void create(struct node **head)

{

    struct node *newnode, *temp;

    int n, i;

    printf("Enter number of nodes: ");

    scanf("%d", &n);

    for(i = 0; i < n; i++)

    {

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

        printf("Enter data: ");

        scanf("%d", &newnode->data);

        newnode->next = NULL;

        if(*head == NULL)

        {

            *head = newnode;

        }

        else

        {

            temp = *head;

            while(temp->next != NULL)

                temp = temp->next;

            temp->next = newnode;

        }

    }

}

// Display linked list

void display(struct node *head)

{

    while(head != NULL)

    {

        printf("%d -> ", head->data);

        head = head->next;

    }

    printf("NULL\n");

}

// Reverse linked list

void reverse()

{

    struct node *prev = NULL, *curr = head1, *next;

    while(curr != NULL)

    {

        next = curr->next;

        curr->next = prev;

        prev = curr;

        curr = next;

    }

    head1 = prev;

    printf("Reversed Linked List:\n");

    display(head1);

}

// Concatenate one element

void concatenate()

{

    struct node *newnode, *temp;

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

    printf("Enter element: ");

    scanf("%d", &newnode->data);

    newnode->next = NULL;

    if(head1 == NULL)

    {

        head1 = newnode;

    }

    else

    {

        temp = head1;

        while(temp->next != NULL)

            temp = temp->next;

        temp->next = newnode;

    }

    printf("After Concatenation:\n");

    display(head1);

}

// Merge two linked lists

void merge()

{

    struct node *temp;

    if(head1 == NULL)

    {

        head1 = head2;

    }

    else

    {

        temp = head1;

        while(temp->next != NULL)

            temp = temp->next;

        temp->next = head2;

    }

    printf("Merged Linked List:\n");

    display(head1);

}

int main()

{

    int ch;

    printf("Create First Linked List\n");

    create(&head1);

    while(1)

    {

        printf("\n----- MENU -----\n");

        printf("1. Reverse Linked List\n");

        printf("2. Concatenate Element\n");

        printf("3. Merge Two Linked Lists\n");

        printf("4. Display First List\n");

        printf("5. Exit\n");

        printf("Enter your choice: ");

        scanf("%d", &ch);

        switch(ch)

        {

            case 1:

                reverse();

                break;

            case 2:

                concatenate();

                break;

            case 3:

                printf("Create Second Linked List\n");

                create(&head2);

                merge();

                break;

            case 4:

                display(head1);

                break;

            case 5:

                exit(0);

            default:

                printf("Invalid Choice\n");

        }

    }

    return 0;

}

Set B
Implement a list library (doublylist.h) for a doubly linked list with Append, Insert, Search and Delete operations.
a) Write a menu driven program for the following operations.
i. Insert an element in a linked list in a particular position
ii. Search an element in a linked list.
iii. Delete a particular element from a linked list.

1. Header File: doublylist.h

#ifndef DOUBLYLIST_H
#define DOUBLYLIST_H

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

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

struct node *head = NULL;

// Append node
void append(int value)
{
    struct node *newnode, *temp;

    newnode = (struct node *)malloc(sizeof(struct node));
    newnode->data = value;
    newnode->next = NULL;
    newnode->prev = NULL;

    if(head == NULL)
    {
        head = newnode;
    }
    else
    {
        temp = head;
        while(temp->next != NULL)
            temp = temp->next;

        temp->next = newnode;
        newnode->prev = temp;
    }
}

// Display list
void display()
{
    struct node *temp = head;

    if(head == NULL)
    {
        printf("List is Empty\n");
        return;
    }

    while(temp != NULL)
    {
        printf("%d <-> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

// Insert at position
void insert(int value, int pos)
{
    struct node *newnode, *temp;
    int i;

    newnode = (struct node *)malloc(sizeof(struct node));
    newnode->data = value;
    newnode->next = NULL;
    newnode->prev = NULL;

    if(pos == 1)
    {
        newnode->next = head;

        if(head != NULL)
            head->prev = newnode;

        head = newnode;
        return;
    }

    temp = head;

    for(i = 1; i < pos - 1 && temp != NULL; i++)
        temp = temp->next;

    if(temp == NULL)
    {
        printf("Invalid Position\n");
        free(newnode);
        return;
    }

    newnode->next = temp->next;
    newnode->prev = temp;

    if(temp->next != NULL)
        temp->next->prev = newnode;

    temp->next = newnode;
}

// Search element
void search(int key)
{
    struct node *temp = head;
    int pos = 1;

    while(temp != NULL)
    {
        if(temp->data == key)
        {
            printf("Element found at position %d\n", pos);
            return;
        }
        temp = temp->next;
        pos++;
    }

    printf("Element not found\n");
}

// Delete element
void deleteElement(int key)
{
    struct node *temp = head;

    while(temp != NULL && temp->data != key)
        temp = temp->next;

    if(temp == NULL)
    {
        printf("Element not found\n");
        return;
    }

    if(temp == head)
    {
        head = temp->next;

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

        if(temp->next != NULL)
            temp->next->prev = temp->prev;
    }

    free(temp);
    printf("Element deleted successfully\n");
}

#endif

---

2. Main Program: main.c

#include "doublylist.h"

int main()
{
    int ch, value, pos;

    while(1)
    {
        printf("\n------ MENU ------\n");
        printf("1. Append Element\n");
        printf("2. Insert at Position\n");
        printf("3. Search Element\n");
        printf("4. Delete Element\n");
        printf("5. Display List\n");
        printf("6. Exit\n");

        printf("Enter your choice: ");
        scanf("%d", &ch);

        switch(ch)
        {
            case 1:
                printf("Enter element: ");
                scanf("%d", &value);
                append(value);
                break;

            case 2:
                printf("Enter element and position: ");
                scanf("%d%d", &value, &pos);
                insert(value, pos);
                break;

            case 3:
                printf("Enter element to search: ");
                scanf("%d", &value);
                search(value);
                break;

            case 4:
                printf("Enter element to delete: ");
                scanf("%d", &value);
                deleteElement(value);
                break;

            case 5:
                display();
                break;

            case 6:
                exit(0);

            default:
                printf("Invalid Choice\n");
        }
    }

    return 0;
}

b) Write a menu driven program for the following operations.
i. Reverse a linked list and display it.
ii. Accept an element from user and Concatenate it with a created link list.
iii. Merge two linked list and display it.

#include <stdio.h>

#include <stdlib.h>

struct node

{

    int data;

    struct node *next;

};

struct node *head1 = NULL, *head2 = NULL;

// Create a linked list

void create(struct node **head)

{

    struct node *newnode, *temp;

    int n, i;

    printf("Enter number of nodes: ");

    scanf("%d", &n);

    for(i = 0; i < n; i++)

    {

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

        printf("Enter data: ");

        scanf("%d", &newnode->data);

        newnode->next = NULL;

        if(*head == NULL)

        {

            *head = newnode;

        }

        else

        {

            temp = *head;

            while(temp->next != NULL)

                temp = temp->next;

            temp->next = newnode;

        }

    }

}

// Display linked list

void display(struct node *head)

{

    if(head == NULL)

    {

        printf("List is Empty\n");

        return;

    }

    while(head != NULL)

    {

        printf("%d -> ", head->data);

        head = head->next;

    }

    printf("NULL\n");

}

// Reverse linked list

void reverse()

{

    struct node *prev = NULL, *curr = head1, *next;

    while(curr != NULL)

    {

        next = curr->next;

        curr->next = prev;

        prev = curr;

        curr = next;

    }

    head1 = prev;

    printf("Reversed Linked List:\n");

    display(head1);

}

// Concatenate an element

void concatenate()

{

    struct node *newnode, *temp;

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

    printf("Enter element to concatenate: ");

    scanf("%d", &newnode->data);

    newnode->next = NULL;

    if(head1 == NULL)

    {

        head1 = newnode;

    }

    else

    {

        temp = head1;

        while(temp->next != NULL)

            temp = temp->next;

        temp->next = newnode;

    }

    printf("After Concatenation:\n");

    display(head1);

}

// Merge two linked lists

void merge()

{

    struct node *temp;

    printf("Create Second Linked List\n");

    create(&head2);

    if(head1 == NULL)

    {

        head1 = head2;

    }

    else

    {

        temp = head1;

        while(temp->next != NULL)

            temp = temp->next;

        temp->next = head2;

    }

    printf("Merged Linked List:\n");

    display(head1);

}

int main()

{

    int ch;

    printf("Create First Linked List\n");

    create(&head1);

    while(1)

    {

        printf("\n----- MENU -----\n");

        printf("1. Reverse Linked List\n");

        printf("2. Concatenate Element\n");

        printf("3. Merge Two Linked Lists\n");

        printf("4. Display Linked List\n");

        printf("5. Exit\n");

        printf("Enter your choice: ");

        scanf("%d", &ch);

        switch(ch)

        {

            case 1:

                reverse();

                break;

            case 2:

                concatenate();

                break;

            case 3:

                merge();

                break;

            case 4:

                display(head1);

                break;

            case 5:

                exit(0);

            default:

                printf("Invalid Choice\n");

        }

    }

    return 0;

}

c) Write a program that adds two single variable polynomials. Each polynomial should be
represented as a list with linked list implementation

#include <stdio.h>

#include <stdlib.h>

struct node

{

    int coeff;

    int exp;

    struct node *next;

};

// Create polynomial

void create(struct node **head)

{

    struct node *newnode, *temp;

    int n, i;

    printf("Enter number of terms: ");

    scanf("%d", &n);

    for(i = 0; i < n; i++)

    {

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

        printf("Enter coefficient and exponent: ");

        scanf("%d%d", &newnode->coeff, &newnode->exp);

        newnode->next = NULL;

        if(*head == NULL)

        {

            *head = newnode;

        }

        else

        {

            temp = *head;

            while(temp->next != NULL)

                temp = temp->next;

            temp->next = newnode;

        }

    }

}

// Display polynomial

void display(struct node *head)

{

    while(head != NULL)

    {

        printf("%dx^%d", head->coeff, head->exp);

        if(head->next != NULL)

            printf(" + ");

        head = head->next;

    }

    printf("\n");

}

// Add two polynomials

struct node* add(struct node *p1, struct node *p2)

{

    struct node *result = NULL, *temp = NULL, *newnode;

    while(p1 != NULL && p2 != NULL)

    {

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

        newnode->next = NULL;

        if(p1->exp == p2->exp)

        {

            newnode->coeff = p1->coeff + p2->coeff;

            newnode->exp = p1->exp;

            p1 = p1->next;

            p2 = p2->next;

        }

        else if(p1->exp > p2->exp)

        {

            newnode->coeff = p1->coeff;

            newnode->exp = p1->exp;

            p1 = p1->next;

        }

        else

        {

            newnode->coeff = p2->coeff;

            newnode->exp = p2->exp;

            p2 = p2->next;

        }

        if(result == NULL)

        {

            result = temp = newnode;

        }

        else

        {

            temp->next = newnode;

            temp = newnode;

        }

    }

    while(p1 != NULL)

    {

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

        newnode->coeff = p1->coeff;

        newnode->exp = p1->exp;

        newnode->next = NULL;

        temp->next = newnode;

        temp = newnode;

        p1 = p1->next;

    }

    while(p2 != NULL)

    {

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

        newnode->coeff = p2->coeff;

        newnode->exp = p2->exp;

        newnode->next = NULL;

        temp->next = newnode;

        temp = newnode;

        p2 = p2->next;

    }

    return result;

}

int main()

{

    struct node *poly1 = NULL, *poly2 = NULL, *result = NULL;

    printf("Enter First Polynomial (Descending order of exponents)\n");

    create(&poly1);

    printf("\nEnter Second Polynomial (Descending order of exponents)\n");

    create(&poly2);

    printf("\nFirst Polynomial:\n");

    display(poly1);

    printf("Second Polynomial:\n");

    display(poly2);

    result = add(poly1, poly2);

    printf("Resultant Polynomial:\n");

    display(result);

    return 0;

}