C Linked List Implementation: Single and Doubly Linked

Posted on Feb 14, 2025 in Computer Engineering in Computer Engineering

Single Linked List Implementation in C

This section demonstrates the implementation of a single linked list in C. The code includes functions for inserting nodes at the beginning and end of the list, deleting nodes from the beginning and end, and displaying the contents of the list.

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

struct Node {
    int data;
    struct Node *next;
};

void insert(struct Node **head, int data, int atEnd) {
    struct Node *newNode = (struct Node *)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = NULL;

    if (*head == NULL) {
        *head = newNode;
    } else {
        struct Node *temp = *head;
        if (atEnd) {
            while (temp->next != NULL) {
                temp = temp->next;
            }
            temp->next = newNode;
        } else {
            newNode->next = *head;
            *head = newNode;
        }
    }
    printf("\n%d Inserted%s\n", newNode->data, atEnd ? " at end" : " at start");
}

void delete(struct Node **head, int atEnd) {
    struct Node *temp = *head;
    struct Node *prev = NULL;

    if (*head == NULL) {
        printf("Linked List Empty, nothing to delete");
        return;
    }

    if (atEnd) {
        while (temp->next != NULL) {
            prev = temp;
            temp = temp->next;
        }
        if (prev == NULL) {
            *head = NULL;
        } else {
            prev->next = NULL;
        }
    } else {
        *head = (*head)->next;
    }
    printf("\n%d deleted%s\n", temp->data, atEnd ? " from end" : " from start");
    free(temp);
}

void display(struct Node *node) {
    printf("\nLinked List: ");
    while (node != NULL) {
        printf("%d ", node->data);
        node = node->next;
    }
    printf("\n");
}

int main() {
    struct Node *head = NULL;
    int choice, value;

    do {
        printf("\n1. Insert at start\n2. Insert at end\n3. Delete at start\n4. Delete at end\n5. Display\n6. Exit\n");
        printf("Enter your choice: ");
        scanf("%d", &choice);

        switch (choice) {
            case 1:
                printf("Enter the value to insert at start: ");
                scanf("%d", &value);
                insert(&head, value, 0);
                break;
            case 2:
                printf("Enter the value to insert at end: ");
                scanf("%d", &value);
                insert(&head, value, 1);
                break;
            case 3:
                delete(&head, 0);
                break;
            case 4:
                delete(&head, 1);
                break;
            case 5:
                display(head);
                break;
            case 6:
                printf("Exiting program...\n");
                break;
            default:
                printf("Invalid choice\n");
        }
    } while (choice != 6);

    return 0;
}

Doubly Linked List Implementation in C

This section provides the implementation of a doubly linked list in C. The code includes functions for inserting nodes at the front and rear of the list, deleting nodes from the front and rear, and displaying the linked list.

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

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

struct Node *head = NULL;
struct Node *tail = NULL;

void insertFront(int data) {
    struct Node *newNode = (struct Node *)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->prev = NULL;
    newNode->next = head;

    if (head != NULL) {
        head->prev = newNode;
    }
    head = newNode;

    if (tail == NULL) {
        tail = newNode;
    }
    printf("\n%d Inserted at front\n", data);
}

void insertRear(int data) {
    struct Node *newNode = (struct Node *)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = NULL;
    newNode->prev = tail;

    if (tail != NULL) {
        tail->next = newNode;
    }
    tail = newNode;

    if (head == NULL) {
        head = newNode;
    }
    printf("\n%d Inserted at rear\n", data);
}

void deleteFront() {
    if (head == NULL) {
        printf("Linked List Empty, nothing to delete");
        return;
    }

    struct Node *temp = head;
    head = head->next;

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

    if (temp == tail) {
        tail = NULL;
    }
    printf("\n%d deleted from front\n", temp->data);
    free(temp);
}

void deleteRear() {
    if (tail == NULL) {
        printf("Linked List Empty, nothing to delete");
        return;
    }

    struct Node *temp = tail;
    tail = tail->prev;

    if (tail != NULL) {
        tail->next = NULL;
    }

    if (temp == head) {
        head = NULL;
    }
    printf("\n%d deleted from rear\n", temp->data);
    free(temp);
}

void display() {
    printf("\nLinked List: ");
    struct Node *current = head;
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }
    printf("\n");
}

int main() {
    int choice, data;

    do {
        printf("\n1. Insert at front\n2. Insert at rear\n3. Delete from front\n4. Delete from rear\n5. Display\n6. Exit\n");
        printf("Enter your choice: ");
        scanf("%d", &choice);

        switch (choice) {
            case 1:
                printf("Enter the value to insert at front: ");
                scanf("%d", &data);
                insertFront(data);
                break;
            case 2:
                printf("Enter the value to insert at rear: ");
                scanf("%d", &data);
                insertRear(data);
                break;
            case 3:
                deleteFront();
                break;
            case 4:
                deleteRear();
                break;
            case 5:
                display();
                break;
            case 6:
                printf("Exiting program...\n");
                break;
            default:
                printf("Invalid choice\n");
        }
    } while (choice != 6);

    return 0;
}