# 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**:
    
    ```c
    #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**:
    
    ```c
    #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**:
    
    ```c
    #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**:
    
    ```c
    #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**:
    
    ```c
    #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**:
    
    ```c
    #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** pointerToHead, int value) {
        struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
        newNode->data = value;
        newNode->next = *pointerToHead;
        *pointerToHead = 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**:
    
    ```c
    #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**:
    
    ```c
    #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**:
    
    ```c
    #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;
    }
    ```