Index
Operations
Linked lists support various operations for manipulating the data they contain. Here are some common operations performed on linked lists:
- Traversal
2. Insertion
3. Deletion
4. Sorting
1. Traversal of a linked list
Traversal of a linked list involves visiting each node in the list in order to access or manipulate its data. This process typically requires starting from the head (or start) of the list and moving through each node until the end of the list is reached. Here’s a basic example of how traversal of a singly linked list can be implemented in C:
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
void traverseLinkedList(struct Node* head) {
struct Node* current = head;
while (current != NULL) {
printf("%d ", current->data);
current = current->next;
}
printf("\n");
}
int main() {
struct Node* head = (struct Node*)malloc(sizeof(struct Node));
struct Node* second = (struct Node*)malloc(sizeof(struct Node));
struct Node* third = (struct Node*)malloc(sizeof(struct Node));
head->data = 1;
head->next = second;
second->data = 2;
second->next = third;
third->data = 3;
third->next = NULL; // End of the list
printf("Linked list elements: ");
traverseLinkedList(head);
free(head);
free(second);
free(third);
return 0;
}
Output:
Linked list elements: 1 2 3
2. Delete a Node in a Linked List
Deleting a node in a linked list involves removing a specific node from the list while maintaining the integrity of the list’s structure. There are several cases to consider when deleting a node:
- Deleting the head node.
- Deleting a node in the middle of the list.
- Deleting the last node in the list.
Here’s how you can implement a function to delete a node with a given value from a singly linked list in C:
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node* next;
} Node;
void traverseAndPrint(Node* head) {
Node* currentNode = head;
while (currentNode != NULL) {
printf("%d -> ", currentNode->data);
currentNode = currentNode->next;
}
printf("null\n");
}
Node* deleteSpecificNode(Node* head, Node* nodeToDelete) {
if (head == nodeToDelete) {
Node* newHead = head->next;
free(head);
return newHead;
}
Node* currentNode = head;
while (currentNode->next && currentNode->next != nodeToDelete) {
currentNode = currentNode->next;
}
if (currentNode->next == NULL) {
return head;
}
Node* temp = currentNode->next;
currentNode->next = currentNode->next->next;
free(temp);
return head;
}
int main() {
Node* node1 = malloc(sizeof(Node));
node1->data = 3;
Node* node2 = malloc(sizeof(Node));
node2->data = 1;
Node* node3 = malloc(sizeof(Node));
node3->data = 6;
Node* node4 = malloc(sizeof(Node));
node4->data = 7;
Node* node5 = malloc(sizeof(Node));
node5->data = 9;
node1->next = node2;
node2->next = node3;
node3->next = node4;
node4->next = node5;
printf("Before deletion:\n");
traverseAndPrint(node1);
node1 = deleteSpecificNode(node1, node4);
printf("\nAfter deletion:\n");
traverseAndPrint(node1);
free(node1);
free(node2);
free(node3);
free(node5);
return 0;
}
Output:
Before deletion:
3 -> 1 -> 6 -> 7 -> 9 -> null
After deletion:
3 -> 1 -> 6 -> 9 -> null
3. Insert a Node in a Linked List
To insert a node into a linked list, you typically need to consider a few scenarios:
- Insertion at the Beginning: Inserting a node at the beginning of the linked list.
- Insertion at the End: Inserting a node at the end of the linked list.
- Insertion at a Specific Position: Inserting a node at a specific position within the linked list.
Here’s how you can implement these insertion operations in C:
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node* next;
} Node;
void traverseAndPrint(Node* head) {
Node* currentNode = head;
while (currentNode != NULL) {
printf("%d -> ", currentNode->data);
currentNode = currentNode->next;
}
printf("null\n");
}
Node* insertNodeAtPosition(Node* head, Node* newNode, int position) {
if (position == 1) {
newNode->next = head;
return newNode;
}
Node* currentNode = head;
for (int i = 1; i < position - 1 && currentNode != NULL; i++) {
currentNode = currentNode->next;
}
if (currentNode != NULL) {
newNode->next = currentNode->next;
currentNode->next = newNode;
}
return head;
}
int main() {
Node* node1 = malloc(sizeof(Node));
node1->data = 4;
Node* node2 = malloc(sizeof(Node));
node2->data = 9;
Node* node3 = malloc(sizeof(Node));
node3->data = 5;
Node* node4 = malloc(sizeof(Node));
node4->data = 8;
node1->next = node2;
node2->next = node3;
node3->next = node4;
printf("Original list:\n");
traverseAndPrint(node1);
// Insert a new node with value 97 at position 2
Node* newNode = malloc(sizeof(Node));
newNode->data = 70;
node1 = insertNodeAtPosition(node1, newNode, 2);
printf("\nAfter insertion:\n");
traverseAndPrint(node1);
free(node1);
free(node2);
free(node3);
free(node4);
free(newNode);
return 0;
}
Output:
Original list:
4 -> 9 -> 5 -> 8 -> null
After insertion:
4 -> 70 -> 9 -> 5 -> 8 -> null
4.Sorting
Sorting a linked list involves arranging the elements of the list in a specific order, such as ascending or descending order. One common sorting algorithm used for linked lists is Merge Sort, which is efficient for linked lists due to its divide-and-conquer approach.
Here’s how you can implement Merge Sort for sorting a singly linked list in C:
#include <stdio.h>
#include <stdlib.h>
// Define a structure for a node
struct Node {
int data;
struct Node* next;
};
// Function to merge two sorted linked lists
struct Node* merge(struct Node* left, struct Node* right) {
// Base cases
if (left == NULL) return right;
if (right == NULL) return left;
struct Node* result = NULL;
// Pick either left or right and recur
if (left->data <= right->data) {
result = left;
result->next = merge(left->next, right);
} else {
result = right;
result->next = merge(left, right->next);
}
return result;
}
// Function to perform Merge Sort on linked list
void mergeSort(struct Node** head_ref) {
struct Node* head = *head_ref;
struct Node* left;
struct Node* right;
// Base case: If the list is empty or has only one node
if (head == NULL || head->next == NULL) {
return;
}
// Split the list into two halves
struct Node* slow = head;
struct Node* fast = head->next;
while (fast != NULL) {
fast = fast->next;
if (fast != NULL) {
slow = slow->next;
fast = fast->next;
}
}
left = head;
right = slow->next;
slow->next = NULL;
// Recursively sort the two halves
mergeSort(&left);
mergeSort(&right);
// Merge the sorted halves
*head_ref = merge(left, right);
}
// Function to insert a new node at the beginning of the linked list
void insertAtBeginning(struct Node** head_ref, int new_data) {
// Allocate memory for a new node
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
// Assign data to the new node
new_node->data = new_data;
// Set the next of the new node to the current head
new_node->next = *head_ref;
// Move the head to point to the new node
*head_ref = new_node;
}
// Function to print the linked list
void printList(struct Node* node) {
while (node != NULL) {
printf("%d ", node->data);
node = node->next;
}
printf("\n");
}
// Main function
int main() {
// Start with an empty linked list
struct Node* head = NULL;
// Insert some elements into the linked list
insertAtBeginning(&head, 3);
insertAtBeginning(&head, 6);
insertAtBeginning(&head, 2);
insertAtBeginning(&head, 9);
insertAtBeginning(&head, 1);
// Print the original linked list
printf("Original linked list: ");
printList(head);
// Perform Merge Sort
mergeSort(&head);
// Print the sorted linked list
printf("Sorted linked list: ");
printList(head);
return 0;
}
Output:
Original linked list: 1 9 2 6 3
Sorted linked list: 1 2 3 6 9
Time Complexity of linked list operations
The time complexity of linked list operations varies depending on the specific operation and the size of the linked list. O(n), it does not mean they take the same amount of time.
Linear search for linked lists works the same as for arrays. A list of unsorted values are traversed from the head node until the node with the specific value is found. Time complexity is O(n).
Binary search is not possible for linked lists because the algorithm is based on jumping directly to different array elements, and that is not possible with linked lists.
