Linked Lists: One step at a time!

First Step: What is a node made up of?

1. Explanation:

   • A linked list is made up of nodes.

   • Each node contains some data and a pointer to the next node in the list.

   • Define a structure for the node that includes an integer and a pointer to the next node.

2. Code:

    #include <stdio.h>
    #include <stdlib.h>
   
    // Define the node structure
    struct Node {
        int data;          // Integer data
        struct Node* next; // Pointer to the next node
    };
   

Second Step: Creating Two Nodes and Linking Them

1. Explanation:

   • Create two nodes.

   • Set the first node to point to the second node.

   • Set the second node to point to NULL, indicating the end of the list.

   • Assign values to the nodes using scanf.

2. Code:

    #include <stdio.h>
    #include <stdlib.h>
   
    // Define the node structure
    struct Node {
        int data;
        struct Node* next;
    };
   
    int main() {
        struct Node* first = (struct Node*)malloc(sizeof(struct Node));
        struct Node* second = (struct Node*)malloc(sizeof(struct Node));
   
        // Get values from the user
        printf("Enter value for the first node: ");
        scanf("%d", &first->data);
        first->next = second;
   
        printf("Enter value for the second node: ");
        scanf("%d", &second->data);
        second->next = NULL;
   
        // Free allocated memory
        free(first);
        free(second);
   
        return 0;
    }
   

Third Step: Creating Three Nodes and Linking Them

1. Explanation:

   • Create three nodes.

   • Link them in a chain where each node points to the next node.

   • The last node points to NULL.

2. Code:

    #include <stdio.h>
    #include <stdlib.h>
   
    // Define the node structure
    struct Node {
        int data;
        struct Node* next;
    };
   
    int main() {
        struct Node* first = (struct Node*)malloc(sizeof(struct Node));
        struct Node* second = (struct Node*)malloc(sizeof(struct Node));
        struct Node* third = (struct Node*)malloc(sizeof(struct Node));
   
        // Get values from the user
        printf("Enter value for the first node: ");
        scanf("%d", &first->data);
        first->next = second;
   
        printf("Enter value for the second node: ");
        scanf("%d", &second->data);
        second->next = third;
   
        printf("Enter value for the third node: ");
        scanf("%d", &third->data);
        third->next = NULL;
   
        // Free allocated memory
        free(first);
        free(second);
        free(third);
   
        return 0;
    }
   

Fourth Step: Creating a Linked List of 10 Nodes in a Loop

1. Explanation:

   • Create a linked list with 10 nodes using a loop.

   • Use a head pointer to point to the first node.

   • Use a temporary pointer to build the list.

   • Use scanf to get values for each node from the user.

2. Code:

    #include <stdio.h>
    #include <stdlib.h>
   
    // Define the node structure
    struct Node {
        int data;
        struct Node* next;
    };
   
    int main() {
        struct Node* head = NULL; // Head of the list
        struct Node* temp = NULL; // Temporary pointer
        struct Node* newNode = NULL; // Pointer to new node
   
        // Create 10 nodes
        for (int i = 0; i < 10; i++) {
            newNode = (struct Node*)malloc(sizeof(struct Node));
   
            printf("Enter value for node %d: ", i + 1);
            scanf("%d", &newNode->data);
            newNode->next = NULL;
   
            if (head == NULL) {
                // If the list is empty, set head to the new node
                head = newNode;
            } else {
                // Otherwise, link the new node to the last node
                temp->next = newNode;
            }
            // Move the temp pointer to the new node
            temp = newNode;
        }
   
        return 0;
    }
   

Fifth Step: Printing the Linked List

1. Explanation:

   • Write a function that takes the head of the list as a parameter.

   • Use a while loop to traverse the list until the end (NULL).

   • Print the data of each node.

2. Code:

    #include <stdio.h>
    #include <stdlib.h>
   
    // Define the node structure
    struct Node {
        int data;
        struct Node* next;
    };
   
    // Function to print the linked list
    void printList(struct Node* head) {
        struct Node* temp = head;
        printf("Linked List: ");
        while (temp != NULL) {
            printf("%d -> ", temp->data);
            temp = temp->next;
        }
        printf("NULL\n");
    }
   
    int main() {
        struct Node* head = NULL; // Head of the list
        struct Node* temp = NULL; // Temporary pointer
        struct Node* newNode = NULL; // Pointer to new node
   
        // Create 10 nodes
        for (int i = 0; i < 10; i++) {
            newNode = (struct Node*)malloc(sizeof(struct Node));
   
            printf("Enter value for node %d: ", i + 1);
            scanf("%d", &newNode->data);
            newNode->next = NULL;
   
            if (head == NULL) {
                // If the list is empty, set head to the new node
                head = newNode;
            } else {
                // Otherwise, link the new node to the last node
                temp->next = newNode;
            }
            // Move the temp pointer to the new node
            temp = newNode;
        }
   
        // Print the list
        printList(head);
   
        // Free allocated memory
        temp = head;
        while (temp != NULL) {
            struct Node* next = temp->next;
            free(temp);
            temp = next;
        }
   
        return 0;
    }
   

Sixth Step: Adding a Node to the Beginning

1. Explanation:

   • Write a function that takes a double pointer to the head of the list.

   • Create a new node, assign its value from the function parameter.

   • Make the new node point to the current head.

   • Update the head to point to the new node.

   • Use printList to print the updated list.

2. Code:

    #include <stdio.h>
    #include <stdlib.h>
   
    // Define the node structure
    struct Node {
        int data;
        struct Node* next;
    };
   
    // Function to print the linked list
    void printList(struct Node* head) {
        struct Node* temp = head;
        printf("Linked List: ");
        while (temp != NULL) {
            printf("%d -> ", temp->data);
            temp = temp->next;
        }
        printf("NULL\n");
    }
   
    // Function to add a node at the beginning of the list
    void addNodeAtBeginning(struct Node** head, int value) {
        struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
        newNode->data = value;
        newNode->next = *head;
        *head = newNode;
    }
   
    int main() {
        struct Node* head = NULL; // Head of the list
        struct Node* temp = NULL; // Temporary pointer
        struct Node* newNode = NULL; // Pointer to new node
   
        // Create 10 nodes
        for (int i = 0; i < 10; i++) {
            newNode = (struct Node*)malloc(sizeof(struct Node));
   
            printf("Enter value for node %d: ", i + 1);
            scanf("%d", &newNode->data);
            newNode->next = NULL;
   
            if (head == NULL) {
                // If the list is empty, set head to the new node
                head = newNode;
            } else {
                // Otherwise, link the new node to the last node
                temp->next = newNode;
            }
            // Move the temp pointer to the new node
            temp = newNode;
        }
   
        // Add a new node at the beginning
        int newValue;
        printf("Enter value for the new node at the beginning: ");
        scanf("%d", &newValue);
        addNodeAtBeginning(&head, newValue);
   
        // Print the list
        printList(head);
   
        // Free allocated memory
        temp = head;
        while (temp != NULL) {
            struct Node* next = temp->next;
            free(temp);
            temp = next;
        }
   
        return 0;
    }
   

Seventh Step: Inserting a Node After the Nth Node

1. Explanation:

   • Write a function that takes the head of the list, a position n, and a value.

   • Traverse the list to find the nth node.

   • If the nth node exists, create a new node.

   • Insert the new node after the nth node.

   • Use printList to print the updated list.

2. Code:

    #include <stdio.h>
    #include <stdlib.h>
   
    // Define the node structure
    struct Node {
        int data;
        struct Node* next;
    };
   
    // Function to print the linked list
    void printList(struct Node* head) {
        struct Node* temp = head;
        printf("Linked List: ");
        while (temp != NULL) {
            printf("%d -> ", temp->data);
            temp = temp->next;
        }
        printf("NULL\n");
    }
   
    // Function to insert a node after the nth node
    void insertNodeAfterNth(struct Node* head, int n, int value) {
        struct Node* temp = head;
        for (int i = 0; i < n; i++) {
            if (temp == NULL) return; // If n is beyond the end of the list, do nothing
            temp = temp->next;
        }
        if (temp != NULL) {
            struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
            newNode->data = value;
            newNode->next = temp->next;
            temp->next = newNode;
        }
    }
   
    int main() {
        struct Node* head = NULL; // Head of the list
        struct Node* temp = NULL; // Temporary pointer
        struct Node* newNode = NULL; // Pointer to new node
   
        // Create a simple list with 3 nodes for testing
        head = (struct Node*)malloc(sizeof(struct Node));
        head->data = 1;
        head->next = (struct Node*)malloc(sizeof(struct Node));
        head->next->data = 2;
        head->next->next = (struct Node*)malloc(sizeof(struct Node));
        head->next->next->data = 3;
        head->next->next->next = NULL;
   
        // Insert a new node after the nth node
        int n = 1, value = 99;
        insertNodeAfterNth(head, n, value);
   
        // Print the list
        printList(head);
   
        // Free allocated memory
        temp = head;
        while (temp != NULL) {
            struct Node* next = temp->next;
            free(temp);
            temp = next;
        }
   
        return 0;
    }
   

Eighth Step: Deleting the Head Node

1. Explanation:

   • Write a function that takes a double pointer to the head of the list.

   • If the list is not empty, make the head point to the second node.

   • Free the memory of the old head node.

   • Use printList to print the updated list.

2. Code:

    #include <stdio.h>
    #include <stdlib.h>
   
    // Define the node structure
    struct Node {
        int data;
        struct Node* next;
    };
   
    // Function to print the linked list
    void printList(struct Node* head) {
        struct Node* temp = head;
        printf("Linked List: ");
        while (temp != NULL) {
            printf("%d -> ", temp->data);
            temp = temp->next;
        }
        printf("NULL\n");
    }
   
    // Function to delete the head node
    void deleteHeadNode(struct Node** head) {
        if (*head != NULL) {
            struct Node* temp = *head;
            *head = (*head)->next;
            free(temp);
        }
    }
   
    int main() {
        struct Node* head = NULL; // Head of the list
        struct Node* temp = NULL; // Temporary pointer
        struct Node* newNode = NULL; // Pointer to new node
   
        // Create a simple list with 3 nodes for testing
        head = (struct Node*)malloc(sizeof(struct Node));
        head->data = 1;
        head->next = (struct Node*)malloc(sizeof(struct Node));
        head->next->data = 2;
        head->next->next = (struct Node*)malloc(sizeof(struct Node));
        head->next->next->data = 3;
        head->next->next->next = NULL;
   
        // Print the list
        printList(head);
   
        // Delete the head node
        deleteHeadNode(&head);
   
        // Print the list again
        printList(head);
   
        // Free allocated memory
        temp = head;
        while (temp != NULL) {
            struct Node* next = temp->next;
            free(temp);
            temp = next;
        }
   
        return 0;
    }
   

Ninth Step: Deleting a Node with a Specific Value

1. Explanation:

   • Write a function that takes a double pointer to the head of the list and a value.

   • Traverse the list to find the node with the given value.

   • If the node is found, remove it from the list.

   • Use printList to print the updated list.

2. Code:

    #include <stdio.h>
    #include <stdlib.h>
   
    // Define the node structure
    struct Node {
        int data;
        struct Node* next;
    };
   
    // Function to print the linked list
    void printList(struct Node* head) {
        struct Node* temp = head;
        printf("Linked List: ");
        while (temp != NULL) {
            printf("%d -> ", temp->data);
            temp = temp->next;
        }
        printf("NULL\n");
    }
   
    // Function to delete a node with a specific value
    void deleteNodeWithValue(struct Node** head, int value) {
        struct Node* temp = *head;
        struct Node* prev = NULL;
   
        // If the head node holds the value
        if (temp != NULL && temp->data == value) {
            *head = temp->next;
            free(temp);
            return;
        }
   
        // Search for the node with the given value
        while (temp != NULL && temp->data != value) {
            prev = temp;
            temp = temp->next;
        }
   
        // If the value was not found
        if (temp == NULL) return;
   
        // Unlink the node from the list
        prev->next = temp->next;
        free(temp);
    }
   
    int main() {
        struct Node* head = NULL; // Head of the list
        struct Node* temp = NULL; // Temporary pointer
        struct Node* newNode = NULL; // Pointer to new node
   
        // Create a simple list with 3 nodes for testing
        head = (struct Node*)malloc(sizeof(struct Node));
        head->data = 1;
        head->next = (struct Node*)malloc(sizeof(struct Node));
        head->next->data = 2;
        head->next->next = (struct Node*)malloc(sizeof(struct Node));
        head->next->next->data = 3;
        head->next->next->next = NULL;
   
        // Print the list
        printList(head);
   
        // Delete a node with a specific value
        int valueToDelete = 2;
        deleteNodeWithValue(&head, valueToDelete);
   
        // Print the list again
        printList(head);
   
        // Free allocated memory
        temp = head;
        while (temp != NULL) {
            struct Node* next = temp->next;
            free(temp);
            temp = next;
        }
   
        return 0;
    }