A linked list is a data structure that consists of a sequence of nodes, where each node contains a value and a pointer to the next node in the list. In a singly linked list, each node only contains a pointer to the next node, while in a doubly linked list, each node contains a pointer to both the next and previous nodes. Linked lists are commonly used in computer science because of their dynamic nature, as they can easily be added to or removed from without needing to shift other elements.
Deletion in a linked list refers to the process of removing a node from the list. In C++, deletion can be done in several ways, including the following:
- Deleting the first node in the list: This is the simplest form of deletion, as it only requires changing the head pointer to point to the next node in the list. The code for this would look something like this:
void deleteFirstNode(node *&head) { node *temp = head; head = head->next;
delete temp; }
In this code, the head pointer is passed by reference so that it can be modified. The temp variable is used to store the address of the first node, which is then deleted. The head pointer is then updated to point to the next node in the list.
- Deleting a node at a specific position: This involves finding the node at the desired position and updating the pointers of the previous and next nodes to bypass the node that is to be deleted. The code for this would look something like this:
void deleteNodeAtPosition(node *&head, int pos) { if (pos == 1) { deleteFirstNode(head);
return; } node *temp = head; for (int i = 1; i < pos - 1; i++) { temp = temp->next; } node *toDelete = temp->next; temp->next = toDelete->next; delete toDelete; }
In this code, the head pointer and the desired position are passed as parameters. The function first checks if the position is 1, in which case it calls the deleteFirstNode function. If the position is not 1, the temp variable is used to iterate through the list until the node before the desired position is found. The toDelete variable is then used to store the address of the node that is to be deleted. The next pointer of the previous node is then updated to point to the next node, bypassing the node that is to be deleted. The node is then deleted.
- Deleting the last node in the list: This is similar to deleting a node at a specific position, but it requires iterating through the entire list to find the last node. The code for this would look something like this:
void deleteLastNode(node *&head) { node *temp = head; while (temp->next->next != NULL) { temp = temp->next; } node *toDelete = temp->next; temp->next = NULL; delete toDelete;
}
In this code, the head pointer is passed by reference so that it can be modified. The temp variable is used to iterate through the list until the second to last node is found. The toDelete variable is then used to store the address of the last node, which is then deleted. The next pointer of the second
