What is a Singly Linked List?
A Singly Linked List (SLL) is a linear data structure where each element (node) contains data and a pointer to the next node in the sequence.
Structure of a Node
struct node { int data; struct node *next; };
Creation of Singly Linked List
Syntax
struct node *head = NULL;
Example:
#include <stdio.h> #include <stdlib.h> struct node { int data; struct node *next; }; struct node* createNode(int quiz) { struct node* certification = (struct node*)malloc(sizeof(struct node)); certification->data = quiz; certification->next = NULL; return certification; }
Traversal of Singly Linked List
Traversal involves visiting each node in the list to perform operations like displaying data.
void traverse(struct node *head) { struct node *test = head; while (test != NULL) { printf("%d -> ", test->data); test = test->next; } printf("NULL\n"); }
Insertion in Singly Linked List
Insertion involves adding a new node to the list at the beginning, end, or a specific position based on the requirement.
Insert at Beginning
struct node* insertAtBeginning(struct node *head, int quiz) { struct node* mcqs = createNode(quiz); mcqs->next = head; return mcqs; }
Insert at End
struct node* insertAtEnd(struct node *head, int quiz) { struct node* mcqs = createNode(quiz); if (head == NULL) return mcqs; struct node *certification = head; while (certification->next != NULL) certification = certification->next; certification->next = mcqs; return head; }
Insert After a Given Node
void insertAfter(struct node *prev_node, int quiz) { if (prev_node == NULL) return; struct node* mcqs = createNode(quiz); mcqs->next = prev_node->next; prev_node->next = mcqs; }
Deletion in Singly Linked List
Deletion involves removing a node from the list—either from the beginning, end, or a specific position—while maintaining the structure of the remaining nodes.
Delete from Beginning
struct node* deleteBeginning(struct node *head) { if (head == NULL) return NULL; struct node *temp = head; head = head->next; free(temp); return head; }
Delete from End
struct node* deleteEnd(struct node *head) { if (head == NULL) return NULL; if (head->next == NULL) { free(head); return NULL; } struct node *test = head; while (test->next->next != NULL) test = test->next; free(test->next); test->next = NULL; return head; }
Delete a Specific Node (by value)
struct node* deleteNode(struct node *head, int key) { if (head == NULL) return NULL; if (head->data == key) { struct node* temp = head; head = head->next; free(temp); return head; } struct node *current = head; while (current->next != NULL && current->next->data != key) current = current->next; if (current->next == NULL) return head; struct node* temp = current->next; current->next = current->next->next; free(temp); return head; }
Searching in Singly Linked List
Searching involves scanning each node in the list to find a node containing a specific value or key.
int search(struct node *head, int quiz) { struct node *mcqs = head; while (mcqs != NULL) { if (mcqs->data == quiz) return 1; mcqs = mcqs->next; } return 0; }
Complete Example of Singly Linked List Operations in C
#include <stdio.h> #include <stdlib.h> // Node structure struct node { int data; struct node *next; }; // Function to create a new node struct node* createNode(int quiz) { struct node* certification = (struct node*)malloc(sizeof(struct node)); certification->data = quiz; certification->next = NULL; return certification; } // Traversal of Linked List void traverse(struct node *head) { struct node *test = head; while (test != NULL) { printf("%d -> ", test->data); test = test->next; } printf("NULL\n"); } // Insertion at Beginning struct node* insertAtBeginning(struct node *head, int quiz) { struct node* mcqs = createNode(quiz); mcqs->next = head; return mcqs; } // Insertion at End struct node* insertAtEnd(struct node *head, int quiz) { struct node* mcqs = createNode(quiz); if (head == NULL) return mcqs; struct node *certification = head; while (certification->next != NULL) certification = certification->next; certification->next = mcqs; return head; } // Insert After a Given Node void insertAfter(struct node *prev_node, int quiz) { if (prev_node == NULL) return; struct node* mcqs = createNode(quiz); mcqs->next = prev_node->next; prev_node->next = mcqs; } // Delete from Beginning struct node* deleteBeginning(struct node *head) { if (head == NULL) return NULL; struct node *temp = head; head = head->next; free(temp); return head; } // Delete from End struct node* deleteEnd(struct node *head) { if (head == NULL) return NULL; if (head->next == NULL) { free(head); return NULL; } struct node *test = head; while (test->next->next != NULL) test = test->next; free(test->next); test->next = NULL; return head; } // Delete Node by Value struct node* deleteNode(struct node *head, int key) { if (head == NULL) return NULL; if (head->data == key) { struct node* temp = head; head = head->next; free(temp); return head; } struct node *current = head; while (current->next != NULL && current->next->data != key) current = current->next; if (current->next == NULL) return head; struct node* temp = current->next; current->next = current->next->next; free(temp); return head; } // Search in Linked List int search(struct node *head, int quiz) { struct node *mcqs = head; while (mcqs != NULL) { if (mcqs->data == quiz) return 1; mcqs = mcqs->next; } return 0; } // Main Function int main() { struct node* head = NULL; // Insert elements head = insertAtBeginning(head, 30); head = insertAtBeginning(head, 20); head = insertAtBeginning(head, 10); printf("List after inserting at beginning:\n"); traverse(head); head = insertAtEnd(head, 40); head = insertAtEnd(head, 50); printf("List after inserting at end:\n"); traverse(head); insertAfter(head->next, 25); // Insert after 20 printf("List after inserting 25 after second node:\n"); traverse(head); // Search for a node printf("Searching for 25: %s\n", search(head, 25) ? "Found" : "Not Found"); printf("Searching for 100: %s\n", search(head, 100) ? "Found" : "Not Found"); // Delete operations head = deleteBeginning(head); printf("List after deleting from beginning:\n"); traverse(head); head = deleteEnd(head); printf("List after deleting from end:\n"); traverse(head); head = deleteNode(head, 25); printf("List after deleting node with value 25:\n"); traverse(head); return 0; }
Sample Output:
List after inserting at beginning: 10 -> 20 -> 30 -> NULL List after inserting at end: 10 -> 20 -> 30 -> 40 -> 50 -> NULL List after inserting 25 after second node: 10 -> 20 -> 25 -> 30 -> 40 -> 50 -> NULL Searching for 25: Found Searching for 100: Not Found List after deleting from beginning: 20 -> 25 -> 30 -> 40 -> 50 -> NULL List after deleting from end: 20 -> 25 -> 30 -> 40 -> NULL List after deleting node with value 25: 20 -> 30 -> 40 -> NULL
Explanation:
- The program defines a node structure with an integer data field and a pointer to the next node.
- It uses dynamic memory allocation to create new nodes with the createNode() function.
- The traverse() function prints the elements of the linked list from head to NULL.
- Nodes are inserted at the beginning, end, and after a specified node using insertAtBeginning(), insertAtEnd(), and insertAfter() respectively.
- Deletion functions include removing from the beginning, end, and by a specific value.
- The search() function checks if a given value exists in the list and returns a boolean result.
- The main() function demonstrates each operation and prints the list after each step to show the changes.
Sanfoundry Global Education & Learning Series – 1000 C Tutorials.
- Practice Computer Science MCQs
- Apply for Computer Science Internship
- Check Computer Science Books
- Watch Advanced C Programming Videos
- Practice BCA MCQs