Linked Lists: One step at a time!

First Step: What is a node made up of?

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.

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

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.

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

Explanation:
- Create three nodes.
- Link them in a chain where each node points to the next node.
- The last node points to NULL.

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

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.

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

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.

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

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.

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** 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

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.

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

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.

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

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.

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;
 }

Linked Lists: One step at a time!

Comments

More from this blog

Computer Arithmetic: From Fast Adders to Floating-Point

The Complete Memory Hierarchy: From Semiconductor RAM to Virtual Memory

The Ultimate Spring Boot Guide: From Fundamentals to Production-Ready REST APIs

Understanding Functions, Memory, and Pointers in C: A Complete Guide

Datapath and Control

First Step: What is a node made up of?

Second Step: Creating Two Nodes and Linking Them

Third Step: Creating Three Nodes and Linking Them

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

Fifth Step: Printing the Linked List

Sixth Step: Adding a Node to the Beginning

Seventh Step: Inserting a Node After the Nth Node

Eighth Step: Deleting the Head Node

Ninth Step: Deleting a Node with a Specific Value

Command Palette

Comments

More from this blog

First Step: What is a node made up of?

Second Step: Creating Two Nodes and Linking Them

Third Step: Creating Three Nodes and Linking Them

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

Fifth Step: Printing the Linked List

Sixth Step: Adding a Node to the Beginning

Seventh Step: Inserting a Node After the Nth Node

Eighth Step: Deleting the Head Node

Ninth Step: Deleting a Node with a Specific Value