C Program to Implement Singly Linked List

Introduction

A singly linked list is a dynamic data structure where each element, called a node, contains a data part and a pointer to the next node in the list. The last node points to NULL, indicating the end of the list. Singly linked lists allow efficient insertion and deletion of elements at both ends of the list and are commonly used in various applications.

Example:

• Operations: Insert nodes at the beginning, at the end, and in the middle of the list; delete nodes; traverse the list.
• Output: The linked list elements are displayed after each operation.

Problem Statement

Create a C program that:

• Implements a singly linked list with basic operations such as insertion, deletion, and traversal.
• Allows the user to perform these operations interactively.

Solution Steps

1. Include the Standard Libraries: Use #include <stdio.h> and #include <stdlib.h> for standard input-output functions and dynamic memory allocation.
2. Define the Node Structure: Create a structure for the node containing an integer data part and a pointer to the next node.
3. Implement Linked List Operations: Implement functions for inserting a node at the beginning, at the end, and after a specific node; deleting a node; and traversing the list.
4. Create a Menu-Driven Program: Allow the user to interactively choose and perform operations on the linked list.
5. Display the Linked List: Display the contents of the linked list after each operation.

C Program to Implement Singly Linked List

#include <stdio.h> #include <stdlib.h> // Step 2: Define the Node Structure struct Node { int data; struct Node* next; }; // Function to insert a node at the beginning void insertAtBeginning(struct Node** head_ref, int new_data) { struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); new_node->data = new_data; new_node->next = (*head_ref); (*head_ref) = new_node; } // Function to insert a node at the end void insertAtEnd(struct Node** head_ref, int new_data) { struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); struct Node* last = *head_ref; new_node->data = new_data; new_node->next = NULL; if (*head_ref == NULL) { *head_ref = new_node; return; } while (last->next != NULL) { last = last->next; } last->next = new_node; } // Function to insert a node after a specific node void insertAfter(struct Node* prev_node, int new_data) { if (prev_node == NULL) { printf("The given previous node cannot be NULL.\n"); return; } struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); new_node->data = new_data; new_node->next = prev_node->next; prev_node->next = new_node; } // Function to delete a node by key void deleteNode(struct Node** head_ref, int key) { struct Node* temp = *head_ref; struct Node* prev = NULL; if (temp != NULL && temp->data == key) { *head_ref = temp->next; free(temp); return; } while (temp != NULL && temp->data != key) { prev = temp; temp = temp->next; } if (temp == NULL) return; prev->next = temp->next; free(temp); } // Function to traverse and display the linked list void traverseList(struct Node* node) { while (node != NULL) { printf("%d -> ", node->data); node = node->next; } printf("NULL\n"); } int main() { struct Node* head = NULL; int choice, data, key; while (1) { // Step 4: Create a Menu-Driven Program printf("\nMenu:\n"); printf("1. Insert at Beginning\n"); printf("2. Insert at End\n"); printf("3. Insert After\n"); printf("4. Delete a Node\n"); printf("5. Display List\n"); printf("6. Exit\n"); printf("Enter your choice: "); scanf("%d", &choice); switch (choice) { case 1: printf("Enter data to insert at beginning: "); scanf("%d", &data); insertAtBeginning(&head, data); break; case 2: printf("Enter data to insert at end: "); scanf("%d", &data); insertAtEnd(&head, data); break; case 3: printf("Enter the data of the node after which to insert: "); scanf("%d", &key); printf("Enter data to insert: "); scanf("%d", &data); struct Node* temp = head; while (temp != NULL && temp->data != key) { temp = temp->next; } if (temp != NULL) { insertAfter(temp, data); } else { printf("Node with data %d not found.\n", key); } break; case 4: printf("Enter data of the node to delete: "); scanf("%d", &key); deleteNode(&head, key); break; case 5: printf("Linked List: "); traverseList(head); break; case 6: exit(0); default: printf("Invalid choice! Please enter a valid option.\n"); } } return 0; // Return 0 to indicate successful execution } 

Explanation

Step 2: Define the Node Structure

• The Node structure contains two members: an integer data to store the node’s data, and a pointer next to point to the next node in the list.

Insertion Functions

• insertAtBeginning: Inserts a node at the beginning of the list.
• insertAtEnd: Inserts a node at the end of the list.
• insertAfter: Inserts a node after a specified node.

Deletion Function

• deleteNode: Deletes the first node with the specified key.

Traversal Function

• traverseList: Traverses the linked list and prints each node’s data.

Step 4: Create a Menu-Driven Program

• The main() function provides a menu to the user for performing different operations on the linked list. The program continues to run until the user chooses to exit.

Output Example

Example Output:

Menu: 1. Insert at Beginning 2. Insert at End 3. Insert After 4. Delete a Node 5. Display List 6. Exit Enter your choice: 1 Enter data to insert at beginning: 10 Menu: 1. Insert at Beginning 2. Insert at End 3. Insert After 4. Delete a Node 5. Display List 6. Exit Enter your choice: 2 Enter data to insert at end: 20 Menu: 1. Insert at Beginning 2. Insert at End 3. Insert After 4. Delete a Node 5. Display List 6. Exit Enter your choice: 5 Linked List: 10 -> 20 -> NULL 

Conclusion

This C program demonstrates how to implement a singly linked list with basic operations such as insertion, deletion, and traversal. The menu-driven interface allows users to interactively perform operations on the linked list, making it a useful example for beginners learning data structures in C programming.