Linked Lists: One step at a time!

Jyotiprakash MishraJyotiprakash Mishra
9 min read

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;
 }
13
Subscribe to my newsletter

Read articles from Jyotiprakash Mishra directly inside your inbox. Subscribe to the newsletter, and don't miss out.

DSAdata structuresdata structure and algorithms linked list, singly linked listlinked list

Written by

Jyotiprakash Mishra
Jyotiprakash Mishra

I am Jyotiprakash, a deeply driven computer systems engineer, software developer, teacher, and philosopher. With a decade of professional experience, I have contributed to various cutting-edge software products in network security, mobile apps, and healthcare software at renowned companies like Oracle, Yahoo, and Epic. My academic journey has taken me to prestigious institutions such as the University of Wisconsin-Madison and BITS Pilani in India, where I consistently ranked among the top of my class. At my core, I am a computer enthusiast with a profound interest in understanding the intricacies of computer programming. My skills are not limited to application programming in Java; I have also delved deeply into computer hardware, learning about various architectures, low-level assembly programming, Linux kernel implementation, and writing device drivers. The contributions of Linus Torvalds, Ken Thompson, and Dennis Ritchie—who revolutionized the computer industry—inspire me. I believe that real contributions to computer science are made by mastering all levels of abstraction and understanding systems inside out. In addition to my professional pursuits, I am passionate about teaching and sharing knowledge. I have spent two years as a teaching assistant at UW Madison, where I taught complex concepts in operating systems, computer graphics, and data structures to both graduate and undergraduate students. Currently, I am an assistant professor at KIIT, Bhubaneswar, where I continue to teach computer science to undergraduate and graduate students. I am also working on writing a few free books on systems programming, as I believe in freely sharing knowledge to empower others.