Last Updated on July 5, 2023 by Mayank Dham
Linked lists are fundamental data structures used in computer science and programming to efficiently store and manipulate data. Their dynamic nature and flexibility make them an essential tool for various applications. One of the key operations performed on linked lists is the insertion and deletion of elements.
In this article, we will delve into the world of linked lists and explore an efficient C program that demonstrates how to perform insertion and deletion operations. By understanding the concepts behind these operations and studying the implementation in C, readers will gain valuable insights into the power and versatility of linked lists.
What is a Linked List in C?
A linked list in C is a linear data structure consisting of nodes, where each node contains a data element and a reference (or pointer) to the next node in the list. Unlike arrays, linked lists do not require contiguous memory allocation, allowing for dynamic memory allocation during runtime.
In the diagram above, each node contains two components: the data field, which stores the actual value or information, and the next field, which points to the next node in the list. The last node in the list has a "NULL" value in its next field, indicating the end of the list.
By following the next pointers, we can traverse the linked list and access or modify its elements. This dynamic structure allows for efficient insertion and deletion operations at any position within the list, as nodes can be easily rearranged by updating the appropriate pointers.
Insertion in Linked List in C
Before we delve into the code, let’s briefly recap the different types of insertions that can be performed in a linked list:
-
Insertion at the Beginning: In this operation, a new node is added at the beginning of the list, and it becomes the new head of the list.
-
Insertion at the End: Here, a new node is appended to the end of the list, becoming the new tail node.
-
Insertion at a Specific Position: This operation involves adding a new node at a particular position within the list, shifting the existing nodes accordingly.
Insertion at the Beginning:
void insertAtBeginning(struct Node** head, int value) {
// Create a new node
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
// Set the value of the new node
newNode->data = value;
// Point the new node to the current head
newNode->next = *head;
// Update the head to point to the new node
*head = newNode;
}Insertion at the End:
void insertAtEnd(struct Node** head, int value) {
// Create a new node
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
struct Node* temp = *head;
// Set the value of the new node
newNode->data = value;
// Make the new node the tail
newNode->next = NULL;
// If the list is empty, make the new node the head
if (*head == NULL) {
*head = newNode;
return;
}
// Traverse to the end of the list
while (temp->next != NULL) {
temp = temp->next;
}
// Append the new node at the end
temp->next = newNode;
}Insertion at a Specific Position:
void insertAtPosition(struct Node** head, int value, int position) {
// Create a new node
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
struct Node* temp = *head;
// Set the value of the new node
newNode->data = value;
// Traverse to the desired position
for (int i = 1; i < position - 1; i++) {
if (temp->next != NULL) {
temp = temp->next;
} else {
printf("Invalid position\n");
return;
}
}
// Insert the new node at the desired position
newNode->next = temp->next;
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
void insertAtBeginning(struct Node** head, int value) {
// Create a new node
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
// Set the value of the new node
newNode->data = value;
// Point the new node to the current head
newNode->next = *head;
// Update the head to point to the new node
*head = newNode;
}
void deleteAtBeginning(struct Node** head) {
if (*head == NULL) {
printf("Linked list is already empty.\n");
return;
}
struct Node* temp = *head;
*head = (*head)->next;
free(temp);
}
void deleteAtEnd(struct Node** head) {
if (*head == NULL) {
printf("Linked list is already empty.\n");
return;
}
struct Node* temp = *head;
struct Node* prev = NULL;
while (temp->next != NULL) {
prev = temp;
temp = temp->next;
}
if (prev == NULL) {
*head = NULL;
} else {
prev->next = NULL;
}
free(temp);
}
void deleteAtPosition(struct Node** head, int position) {
if (*head == NULL) {
printf("Linked list is already empty.\n");
return;
}
struct Node* temp = *head;
struct Node* prev = NULL;
if (position == 1) {
*head = temp->next;
free(temp);
return;
}
for (int i = 1; temp != NULL && i < position; i++) {
prev = temp;
temp = temp->next;
}
if (temp == NULL) {
printf("Invalid position.\n");
return;
}
prev->next = temp->next;
free(temp);
}
void displayList(struct Node* head) {
struct Node* temp = head;
// Traverse and print the list
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
int main() {
struct Node* head = NULL;
// Insert elements at the beginning
insertAtBeginning(&head, 3);
insertAtBeginning(&head, 2);
insertAtBeginning(&head, 1);
// Display the original list
printf("Linked List: ");
displayList(head);
// Delete node at the beginning
deleteAtBeginning(&head);
// Display the list after deletion at the beginning
printf("Linked List after deletion at the beginning: ");
displayList(head);
// Delete node at the end
deleteAtEnd(&head);
// Display the list after deletion at the end
printf("Linked List after deletion at the end: ");
displayList(head);
// Delete node at a specific position
deleteAtPosition(&head, 1);
// Display the list after deletion at a specific position
printf("Linked List after deletion at a specific position: ");
displayList(head);
return 0;
}
temp->next = newNode;
}Code Implementation
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
void insertAtBeginning(struct Node** head, int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = *head;
*head = newNode;
}
void insertAtEnd(struct Node** head, int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
struct Node* temp = *head;
newNode->data = value;
newNode->next = NULL;
if (*head == NULL) {
*head = newNode;
return;
}
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
}
void insertAtPosition(struct Node** head, int value, int position) {
if (position <= 0) {
printf("Invalid position\n");
return;
}
if (position == 1 || *head == NULL) {
insertAtBeginning(head, value);
return;
}
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
struct Node* temp = *head;
int count = 1;
while (count < position - 1 && temp->next != NULL) {
temp = temp->next;
count++;
}
if (count < position - 1) {
printf("Invalid position\n");
return;
}
newNode->next = temp->next;
temp->next = newNode;
}
void displayLinkedList(struct Node* head) {
struct Node* temp = head;
if (temp == NULL) {
printf("Linked list is empty.\n");
return;
}
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}
int main() {
struct Node* head = NULL;
// Insertion at the beginning
insertAtBeginning(&head, 10);
insertAtBeginning(&head, 20);
insertAtBeginning(&head, 30);
printf("Linked list after insertion at the beginning: ");
displayLinkedList(head);
// Insertion at the end
insertAtEnd(&head, 40);
insertAtEnd(&head, 50);
printf("Linked list after insertion at the end: ");
displayLinkedList(head);
// Insertion at a specific position
insertAtPosition(&head, 25, 2);
insertAtPosition(&head, 35, 4);
printf("Linked list after insertion at specific positions: ");
displayLinkedList(head);
return 0;
} Output
Linked list after insertion at the beginning: 30 -> 20 -> 10 -> NULL
Linked list after insertion at the end: 30 -> 20 -> 10 -> 40 -> 50 -> NULL
Linked list after insertion at specific positions: 30 -> 25 -> 20 -> 35 -> 10 -> 40 -> 50 -> NULLTime Complexity Analysis:
-
Insertion at the beginning: The time complexity for inserting a node at the beginning of the linked list is O(1). It involves creating a new node, updating the pointers, and reassigning the head, all of which take constant time.
-
Insertion at the end: To insert a node at the end of the linked list, we need to traverse the entire list to reach the last node. Therefore, the time complexity for this operation is O(n), where n is the number of elements in the list.
–Insertion at a specific position: Similar to insertion at the end, inserting a node at a specific position requires traversing the list to reach the desired position. Thus, the time complexity is also O(n), where n is the number of elements in the list.
Deletion in Linked List in C
Before we delve into the code, let’s briefly recap the different types of deletions that can be performed in a linked list:
-
Deletion at the Beginning: In this operation, the first node (head) of the list is removed, and the second node becomes the new head.
-
Deletion at the End: Here, the last node (tail) of the list is removed, and the second-to-last node becomes the new tail.
-
Deletion at a Specific Position: This operation involves removing a node at a particular position within the list, and then adjusting the pointers of the adjacent nodes accordingly.
Deletion at the Beginning:
void deleteAtBeginning(struct Node** head) {
if (*head == NULL) {
printf("Linked list is already empty.\n");
return;
}
struct Node* temp = *head;
*head = (*head)->next;
free(temp);
}Deletion at the End:
void deleteAtEnd(struct Node** head) {
if (*head == NULL) {
printf("Linked list is already empty.\n");
return;
}
struct Node* temp = *head;
struct Node* prev = NULL;
while (temp->next != NULL) {
prev = temp;
temp = temp->next;
}
if (prev == NULL) {
*head = NULL;
} else {
prev->next = NULL;
}
free(temp);
}Deletion at a Specific Position:
void deleteAtPosition(struct Node** head, int position) {
if (*head == NULL) {
printf("Linked list is already empty.\n");
return;
}
struct Node* temp = *head;
struct Node* prev = NULL;
if (position == 1) {
*head = temp->next;
free(temp);
return;
}
for (int i = 1; temp != NULL && i < position; i++) {
prev = temp;
temp = temp->next;
}
if (temp == NULL) {
printf("Invalid position.\n");
return;
}
prev->next = temp->next;
free(temp);
}Code Implementation
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
void insertAtBeginning(struct Node** head, int value) {
// Create a new node
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
// Set the value of the new node
newNode->data = value;
// Point the new node to the current head
newNode->next = *head;
// Update the head to point to the new node
*head = newNode;
}
void deleteAtBeginning(struct Node** head) {
if (*head == NULL) {
printf("Linked list is already empty.\n");
return;
}
struct Node* temp = *head;
*head = (*head)->next;
free(temp);
}
void deleteAtEnd(struct Node** head) {
if (*head == NULL) {
printf("Linked list is already empty.\n");
return;
}
struct Node* temp = *head;
struct Node* prev = NULL;
while (temp->next != NULL) {
prev = temp;
temp = temp->next;
}
if (prev == NULL) {
*head = NULL;
} else {
prev->next = NULL;
}
free(temp);
}
void deleteAtPosition(struct Node** head, int position) {
if (*head == NULL) {
printf("Linked list is already empty.\n");
return;
}
struct Node* temp = *head;
struct Node* prev = NULL;
if (position == 1) {
*head = temp->next;
free(temp);
return;
}
for (int i = 1; temp != NULL && i < position; i++) {
prev = temp;
temp = temp->next;
}
if (temp == NULL) {
printf("Invalid position.\n");
return;
}
prev->next = temp->next;
free(temp);
}
void displayList(struct Node* head) {
struct Node* temp = head;
// Traverse and print the list
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
int main() {
struct Node* head = NULL;
// Insert elements at the beginning
insertAtBeginning(&head, 3);
insertAtBeginning(&head, 2);
insertAtBeginning(&head, 1);
// Display the original list
printf("Linked List: ");
displayList(head);
// Delete node at the beginning
deleteAtBeginning(&head);
// Display the list after deletion at the beginning
printf("Linked List after deletion at the beginning: ");
displayList(head);
// Delete node at the end
deleteAtEnd(&head);
// Display the list after deletion at the end
printf("Linked List after deletion at the end: ");
displayList(head);
// Delete node at a specific position
deleteAtPosition(&head, 1);
// Display the list after deletion at a specific position
printf("Linked List after deletion at a specific position: ");
displayList(head);
return 0;
} Output
Linked List: 1 2 3
Linked List after deletion at the beginning: 2 3
Linked List after deletion at the end: 2
Linked List after deletion at a specific position: Time Complexity Analysis:
The time complexity of deletion in a linked list depends on the type of deletion operation being performed.
Deletion at the Beginning:
The deletion at the beginning operation involves updating the head pointer to point to the second node in the list and freeing the memory of the deleted node.
Since this operation only requires a constant number of steps, the time complexity is O(1).
Deletion at the End:
Deletion at the end requires traversing the entire linked list until reaching the second-to-last node.
Therefore, the time complexity for deletion at the end is O(n), where n is the number of nodes in the linked list.
Deletion at a Specific Position:
To delete a node at a specific position, we need to traverse the list until reaching the desired position, adjusting the pointers accordingly.
In the worst case scenario, where the position is at the end of the list, the time complexity is O(n).
However, for positions closer to the beginning, the time complexity can be closer to O(1).
Conclusion
In this article, we explored the concepts of insertion and deletion in linked lists using the C programming language. We covered the code implementation for inserting nodes at the beginning, end, and specific positions in a linked list. We also discussed the code implementation for deleting nodes from the beginning, end, and specific positions in a linked list. Understanding these operations is crucial for effectively working with linked lists and managing data dynamically.
By studying the provided code examples and the time complexity analysis, readers should have gained a solid understanding of how to perform insertion and deletion operations in a linked list. They can now apply this knowledge to build more complex programs that require efficient data manipulation.
FAQs (Frequently Asked Questions):
Q1: What is a linked list?
A linked list is a data structure consisting of a sequence of nodes, where each node contains a data element and a reference (or pointer) to the next node in the sequence. It allows dynamic memory allocation and provides flexibility in storing and accessing data.
Q2: When should I use a linked list?
Linked lists are useful in scenarios where you need to perform frequent insertions and deletions of elements, as they provide efficient time complexity for these operations. They are also valuable when the size of the data is unknown or when there is a need for efficient memory allocation.
Q3: What is the difference between an array and a linked list?
Arrays are fixed-size structures that store elements in contiguous memory locations, whereas linked lists are dynamic structures that store elements in separate nodes with pointers linking them. Arrays offer fast random access but are less efficient for insertions and deletions, while linked lists provide efficient insertions and deletions but slower random access.
Q4: What are the time complexities for insertion and deletion in a linked list?
Insertion at the beginning: O(1)
Insertion at the end: O(n)
Insertion at a specific position: O(n)
Deletion at the beginning: O(1)
Deletion at the end: O(n)
Deletion at a specific position: O(n)
Q5: Can I insert and delete elements in a doubly linked list using similar techniques?
Yes, the techniques used for insertion and deletion in a singly linked list can be applied to a doubly linked list as well. The main difference is that in a doubly linked list, each node has references to both the next and previous nodes, allowing more efficient deletion operations.