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

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.
Post a Comment
Read more

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.
Post a Comment
Read more

Operating Systems - 20CS11 Lecture Notes

  COURSE OUTCOMES (COs): At the end of the course, students will be able to CO1 Demonstrate the underlying principles and techniques of the operating system     (Understand-l2) CO2 Interpret scheduling and communication methods of processes handled by operating systems (Understand-L2) CO3 Distinguish the process synchronization methods and deadlock handling approaches employed in operating systems (Understand-L2) CO4 Classify memory management techniques and virtual memory mechanisms     (Understand-L2) CO5 Interpret the strategies of disk scheduling algorithms and file system architecture(Understand-L2) Unit-Wise Lecture Notes:
Post a Comment
Read more