Skip to main content

Exercise 4: Double Linked List Implementation

Exercise 4:

i) Implement a doubly linked list and perform various operations to understand its properties and applications.

// C Program double linked list and its operations.

#include <stdio.h>
#include <stdlib.h>
struct Node {
    int data;
    struct Node *previous, *next;
} *head = NULL;
void insertAtBeginning(int);
void insertAtEnd(int);
void insertAfter(int, int);
void deleteBeginning();
void deleteEnd();
void deleteSpecific(int);
void display();
int main() {
    int choice1, choice2, value, location;

    while (1) {
        printf("\n*********** MENU *************\n");
        printf("1. Insert\n2. Delete\n3. Display\n4. Exit\n");
        printf("Enter your choice: ");
        scanf("%d", &choice1);
        switch (choice1) {
            case 1:
                printf("Enter the value to be inserted: ");
                scanf("%d", &value);
                while (1) {
                    printf("\nSelect Inserting option\n");
                    printf("1. At Beginning\n2. At End\n3. After a Node\n4. Cancel\n");
                    printf("Enter choice: ");
                    scanf("%d", &choice2);
                    switch (choice2) {
                        case 1:
                            insertAtBeginning(value);
                            break;
                        case 2:
                            insertAtEnd(value);
                            break;
                        case 3:
                            printf("Enter the node value after which to insert: ");
                            scanf("%d", &location);
                            insertAfter(value, location);
                            break;
                        case 4:
                            goto EndInsert;
                        default:
                            printf("Invalid option!\n");
                    }
                }
            EndInsert:
                break;
            case 2:
                while (1) {
                    printf("\nSelect Deleting option\n");
                    printf("1. At Beginning\n2. At End\n3. Specific Node\n4. Cancel\n");
                    printf("Enter choice: ");
                    scanf("%d", &choice2);
                    switch (choice2) {
                        case 1:
                            deleteBeginning();
                            break;
                        case 2:
                            deleteEnd();
                            break;
                        case 3:
                            printf("Enter the node value to delete: ");
                            scanf("%d", &location);
                            deleteSpecific(location);
                            break;
                        case 4:
                            goto EndDelete;
                        default:
                            printf("Invalid option!\n");
                    }
                }
            EndDelete:
                break;
            case 3:
                display();
                break;
            case 4:
                exit(0);
            default:
                printf("Invalid choice!\n");
        }
    }
}
void insertAtBeginning(int value) 
{
    struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->previous = NULL;
    if (head == NULL) {
        newNode->next = NULL;
        head = newNode;
    } else {
        newNode->next = head;
        head->previous = newNode;
        head = newNode;
    }
    printf("Insertion successful!\n");
}
void insertAtEnd(int value)
{
    struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->next = NULL;
    if (head == NULL) {
        newNode->previous = NULL;
        head = newNode;
    } else {
        struct Node *temp = head;
        while (temp->next != NULL)
            temp = temp->next;
        temp->next = newNode;
        newNode->previous = temp;
    }
    printf("Insertion successful!\n");
}
void insertAfter(int value, int location)
{
    struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    if (head == NULL) {
        newNode->next = newNode->previous = NULL;
        head = newNode;
        printf("Insertion successful!\n");
        return;
    }
    struct Node *temp1 = head;
    while (temp1 != NULL && temp1->data != location)
        temp1 = temp1->next;
    if (temp1 == NULL) {
        printf("Node not found!\n");
        free(newNode);
        return;
    }
    struct Node *temp2 = temp1->next;
    temp1->next = newNode;
    newNode->previous = temp1;
    newNode->next = temp2;
    if (temp2 != NULL)
        temp2->previous = newNode;
    printf("Insertion successful!\n");
}
void deleteBeginning()
{
    if (head == NULL) {
        printf("List is empty!\n");
        return;
    }
    struct Node *temp = head;
    if (head->next == NULL) {
        head = NULL;
    } else {
        head = head->next;
        head->previous = NULL;
    }
    free(temp);
    printf("Deletion successful!\n");
}
void deleteEnd()
{
    if (head == NULL) {
        printf("List is empty!\n");
        return;
    }
    struct Node *temp = head;
    if (head->next == NULL) {
        head = NULL;
        free(temp);
        printf("Deletion successful!\n");
        return;
    }
    while (temp->next != NULL)
        temp = temp->next;
    temp->previous->next = NULL;
    free(temp);
    printf("Deletion successful!\n");
}
void deleteSpecific(int delValue)
{
    if (head == NULL) {
        printf("List is empty!\n");
        return;
    }
    struct Node *temp = head;
    while (temp != NULL && temp->data != delValue)
        temp = temp->next;
    if (temp == NULL) {
        printf("Node not found!\n");
        return;
    }
    if (temp == head) {
        head = head->next;
        if (head != NULL)
            head->previous = NULL;
    } else {
        temp->previous->next = temp->next;
        if (temp->next != NULL)
            temp->next->previous = temp->previous;
    }
    free(temp);
    printf("Deletion successful!\n");
}
void display()
{
    if (head == NULL) {
        printf("List is empty!\n");
        return;
    }
    struct Node *temp = head;
    printf("NULL <--- ");
    while (temp != NULL) {
        printf("%d <===> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

ii) Implement a circular linked list and perform insertion, deletion, and traversal.

// C Program for Circular linked list & its operations.

#include <stdio.h>
#include <stdlib.h>
void insertAtBeginning(int);
void insertAtEnd(int);
void insertAfter(int, int);
void deleteBeginning();
void deleteEnd();
void deleteSpecific(int);
void display();
struct Node {
    int data;
    struct Node *next;
} *head = NULL;
int main()
{
    int choice1, choice2, value, location;
    while (1) {
        printf("\n*********** MENU *************\n");
        printf("1. Insert\n2. Delete\n3. Display\n4. Exit\n");
        printf("Enter your choice: ");
        scanf("%d", &choice1);
        switch (choice1) {
            case 1:
                printf("Enter the value to be inserted: ");
                scanf("%d", &value);
                while (1) {
                    printf("\nInsert Options\n");
                    printf("1. At Beginning\n2. At End\n3. After a Node\n4. Cancel\n");
                    printf("Enter choice: ");
                    scanf("%d", &choice2);
                    switch (choice2) {
                        case 1:
                            insertAtBeginning(value);
                            break;
                        case 2:
                            insertAtEnd(value);
                            break;
                        case 3:
                            printf("Enter node value after which to insert: ");
                            scanf("%d", &location);
                            insertAfter(value, location);
                            break;
                        case 4:
                            goto EndInsert;
                        default:
                            printf("Invalid option!\n");
                    }
                }
            EndInsert:
                break;
            case 2:
                while (1) {
                    printf("\nDelete Options\n");
                    printf("1. At Beginning\n2. At End\n3. Specific Node\n4. Cancel\n");
                    printf("Enter choice: ");
                    scanf("%d", &choice2);
                    switch (choice2) {
                        case 1:
                            deleteBeginning();
                            break;
                        case 2:
                            deleteEnd();
                            break;
                        case 3:
                            printf("Enter value to delete: ");
                            scanf("%d", &location);
                            deleteSpecific(location);
                            break;
                        case 4:
                            goto EndDelete;
                        default:
                            printf("Invalid option!\n");
                    }
                }
            EndDelete:
                break;
            case 3:
                display();
                break;
            case 4:
                exit(0);
            default:
                printf("Invalid choice!\n");
        }
    }
}
void insertAtBeginning(int value)
{
    struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    if (head == NULL) {
        head = newNode;
        newNode->next = head;
    } else {
        struct Node *temp = head;
        while (temp->next != head)
            temp = temp->next;
        newNode->next = head;
        head = newNode;
        temp->next = head;
    }
    printf("Insertion successful!\n");
}
void insertAtEnd(int value)
{
    struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    if (head == NULL) {
        head = newNode;
        newNode->next = head;
    } else {
        struct Node *temp = head;
        while (temp->next != head)
            temp = temp->next;
        temp->next = newNode;
        newNode->next = head;
    }
    printf("Insertion successful!\n");
}
void insertAfter(int value, int location)
{
    struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    if (head == NULL) {
        head = newNode;
        newNode->next = head;
        printf("Insertion successful!\n");
        return;
    }
    struct Node *temp = head;
    do {
        if (temp->data == location) {
            newNode->next = temp->next;
            temp->next = newNode;
            printf("Insertion successful!\n");
            return;
        }
        temp = temp->next;
    } while (temp != head);
    printf("Node not found!\n");
    free(newNode);
}
void deleteBeginning()
{
    if (head == NULL) {
        printf("List is empty!\n");
        return;
    }
    struct Node *temp = head;
    if (head->next == head) {
        head = NULL;
    } else {
        struct Node *last = head;
        while (last->next != head)
            last = last->next;
        head = head->next;
        last->next = head;
    }
    free(temp);
    printf("Deletion successful!\n");
}
void deleteEnd()
{
    if (head == NULL) {
        printf("List is empty!\n");
        return;
    }
    struct Node *temp = head, *prev = NULL;
    if (head->next == head) {
        head = NULL;
        free(temp);
        printf("Deletion successful!\n");
        return;
    }
    while (temp->next != head) {
        prev = temp;
        temp = temp->next;
    }
    prev->next = head;
    free(temp);
    printf("Deletion successful!\n");
}
void deleteSpecific(int delValue)
{
    if (head == NULL) {
        printf("List is empty!\n");
        return;
    }
    struct Node *temp = head, *prev = NULL;
    do {
        if (temp->data == delValue) {
            if (temp == head) {
                deleteBeginning();
            } else {
                prev->next = temp->next;
                free(temp);
                printf("Deletion successful!\n");
            }
            return;
        }
        prev = temp;
        temp = temp->next;
    } while (temp != head);
    printf("Node not found!\n");
}
void display()
{
    if (head == NULL) {
        printf("List is empty!\n");
        return;
    }
    struct Node *temp = head;
    printf("List: ");
    do {
        printf("%d -> ", temp->data);
        temp = temp->next;
    } while (temp != head);
    printf("(back to head)\n");
}

Comments

Post a Comment

Popular posts from this blog

23CS52 - DATA STRUCTURES (Lab)

Data Structures Lab is designed to provide hands-on experience in implementing and analyzing various data structures using the C programming language. Through a series of practical exercises, students learn to implement both linear and non-linear data structures such as arrays, linked lists, stacks, queues, trees, and hashing techniques.
1 comment
Read more

23CS02 - DATA STRUCTURES (Theory)

Data Structures is a fundamental subject in computer science that deals with organizing, storing, and managing data efficiently. It helps in performing operations such as insertion, deletion, searching, and sorting in an optimized way.
1 comment
Read more

23AD02 - ARTIFICIAL INTELLIGENCE

   Artificial Intelligence (AI) is a branch of computer science that enables machines to perform tasks that normally require human intelligence. It involves learning, reasoning, problem-solving, and decision-making using algorithms and data.  AI is widely used in applications such as virtual assistants, healthcare, robotics, and autonomous systems.
1 comment
Read more