A Singly Linked List is a linear data structure consisting of nodes where each node contains two components:
- Data: Stores the actual data.
- Pointer: Points to the next node in the list.
The last node in the list points to NULL, indicating the end of the list.
Structure of a Singly Linked List Node
In C, a node in a singly linked list is typically defined using a struct:
struct Node {
int data; // Data part
struct Node* next; // Pointer to the next node
};
Characteristics of Singly Linked Lists
- Dynamic Size: The size can change during runtime.
- Efficient Insertions/Deletions: Insertions and deletions are easier compared to arrays.
- Non-Contiguous Memory Allocation: Nodes are not stored in consecutive memory locations.
Operations on Singly Linked List
1. Traversal
Visiting each node to display or process its data.
void traverse(struct Node* head) {
struct Node* temp = head;
while (temp != NULL) {
printf(“%d -> “, temp->data);
temp = temp->next;
}
printf(“NULL\n”);
}
2. Insertion
Adding a new node at the beginning, end, or at a specific position.
a. Insert at the Beginning
void insertAtBeginning(struct Node** head, int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = *head;
*head = newNode;
}
b. Insert at the End
void insertAtEnd(struct Node** head, int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = NULL;
if (*head == NULL) {
*head = newNode;
return;
}
struct Node* temp = *head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
}
c. Insert at a Specific Position
void insertAtPosition(struct Node** head, int value, int position) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
if (position == 1) {
newNode->next = *head;
*head = newNode;
return;
}
struct Node* temp = *head;
for (int i = 1; i < position – 1 && temp != NULL; i++) {
temp = temp->next;
}
if (temp == NULL) {
printf(“Position out of range.\n”);
return;
}
newNode->next = temp->next;
temp->next = newNode;
}
3. Deletion
Removing a node from the beginning, end, or a specific position.
a. Delete from the Beginning
void deleteFromBeginning(struct Node** head) {
if (*head == NULL) {
printf(“List is empty.\n”);
return;
}
struct Node* temp = *head;
*head = (*head)->next;
free(temp);
}
b. Delete from the End
void deleteFromEnd(struct Node** head) {
if (*head == NULL) {
printf(“List is empty.\n”);
return;
}
struct Node* temp = *head;
if (temp->next == NULL) {
*head = NULL;
free(temp);
return;
}
while (temp->next->next != NULL) {
temp = temp->next;
}
free(temp->next);
temp->next = NULL;
}
c. Delete a Specific Node
void deleteByValue(struct Node** head, int value) {
if (*head == NULL) {
printf(“List is empty.\n”);
return;
}
struct Node* temp = *head;
struct Node* prev = NULL;
// If the head node itself holds the value
if (temp != NULL && temp->data == value) {
*head = temp->next;
free(temp);
return;
}
// Search for the node to be deleted
while (temp != NULL && temp->data != value) {
prev = temp;
temp = temp->next;
}
// If the value was not found
if (temp == NULL) {
printf(“Value not found in the list.\n”);
return;
}
prev->next = temp->next;
free(temp);
}
4. Searching
Finding a specific value in the linked list.
void search(struct Node* head, int value) {
struct Node* temp = head;
int position = 1;
while (temp != NULL) {
if (temp->data == value) {
printf(“Value %d found at position %d.\n”, value, position);
return;
}
temp = temp->next;
position++;
}
printf(“Value %d not found.\n”, value);
}
5. Reversing the Linked List
Reversing the order of nodes.
void reverse(struct Node** head) {
struct Node* prev = NULL;
struct Node* current = *head;
struct Node* next = NULL;
while (current != NULL) {
next = current->next;
current->next = prev;
prev = current;
current = next;
}
*head = prev;
}
Example Program
#include <stdio.h>
#include <stdlib.h>
// Node structure
struct Node {
int data;
struct Node* next;
};
// Function prototypes
void insertAtEnd(struct Node** head, int value);
void deleteFromBeginning(struct Node** head);
void traverse(struct Node* head);
int main() {
struct Node* head = NULL;
insertAtEnd(&head, 10);
insertAtEnd(&head, 20);
insertAtEnd(&head, 30);
printf(“Linked List after insertion:\n”);
traverse(head);
deleteFromBeginning(&head);
printf(“Linked List after deletion:\n”);
traverse(head);
return 0;
}
// Function implementations
void insertAtEnd(struct Node** head, int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = NULL;
if (*head == NULL) {
*head = newNode;
return;
}
struct Node* temp = *head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
}
void deleteFromBeginning(struct Node** head) {
if (*head == NULL) {
printf(“List is empty.\n”);
return;
}
struct Node* temp = *head;
*head = (*head)->next;
free(temp);
}
void traverse(struct Node* head) {
struct Node* temp = head;
while (temp != NULL) {
printf(“%d -> “, temp->data);
temp = temp->next;
}
printf(“NULL\n”);
}
Output Example
Linked List after insertion:
10 -> 20 -> 30 -> NULL
Linked List after deletion:
20 -> 30 -> NULL
Advantages of Singly Linked List
- Dynamic Memory Allocation: Adjusts its size dynamically.
- Efficient Insertions/Deletions: Faster than arrays as no shifting is required.
- Memory Utilization: Allocates memory as needed.
Disadvantages of Singly Linked List
- Sequential Access: Requires traversal for access.
- Extra Memory Overhead: Stores an additional pointer for each node.
- No Backward Traversal: Cannot move to previous nodes.
Applications of Singly Linked List
- Dynamic Memory Allocation: Managing growing or shrinking data.
- Stacks and Queues: Used in implementing these data structures.
- Graphs: Adjacency lists representation.