Deletion at the Beginning of doubly linked list
Deletion at the Beginning in Doubly Linked List
To delete a node at the beginning in doubly linked list, we can use the following steps:
- Check If the list is empty, there is nothing to delete. Return.
- Check if the node to be deleted is the head node, update the head pointer to point to the next node.
- If the node to be deleted is not the head node, update the previous pointer of the next node to point to the previous node of the node to be deleted.
- If the node to be deleted is not the tail node, update the next pointer of the previous node to point to the next node of the node to be deleted.
- Free the memory allocated to the node to be deleted.
Below is the implementation of the above approach:
// Structure to represent a node in a doubly linked list
struct Node {
int data; // Data stored in the node
Node* next; // Pointer to the next node in the list
Node* prev; // Pointer to the previous node in the list
};
// Function to delete the node at the beginning of a doubly
// linked list
void deleteAtBeginning(Node** head) {
// Check if the list is empty
if (*head == nullptr) {
return;
}
// Check if the node to be deleted is the head node
if (*head == (*head)->next) {
// If the node to be deleted is the head node,
// update the head pointer to point to the next node
*head = (*head)->next;
// If the list has only one node, set the head
// pointer to NULL
if (*head == nullptr) {
return;
}
// Update the previous pointer of the new head node
// to point to NULL
(*head)->prev = nullptr;
// Delete the old head node
delete *head;
return;
}
// If the node to be deleted is not the head node,
// update the previous pointer of the next node to point
// to the previous node of the node to be deleted
Node* temp = *head;
*head = (*head)->next;
(*head)->prev = nullptr;
// Delete the node to be deleted
delete temp;
}
Doubly Linked List Tutorial
A doubly linked list is a more complex data structure than a singly linked list, but it offers several advantages. The main advantage of a doubly linked list is that it allows for efficient traversal of the list in both directions. This is because each node in the list contains a pointer to the previous node and a pointer to the next node. This allows for quick and easy insertion and deletion of nodes from the list, as well as efficient traversal of the list in both directions.
Doubly Linked List in Data Structure