How do you delete a node in a Doubly Linked List at a given position?

Deletion in doubly linked list after the specified node

In order to delete the node after the specified data, we need to perform the following steps.

• Copy the head pointer into a temporary pointer temp.

• Traverse the list until we find the desired data value.

• Check if this is the last node of the list. If it is so then we can't perform deletion.

• Check if the node which is to be deleted, is the last node of the list, if it so then we have to make the next pointer of this node point to null so that it can be the new last node of the list.

• Otherwise, make the pointer ptr point to the node which is to be deleted. Make the next of temp point to the next of ptr. Make the previous of next node of ptr point to temp. free the ptr.

Recommended: Please try your approach on {IDE} first, before moving on to the solution.

Delete node at given position in a doubly linked list in c++

C++ program for Delete node at given position in a doubly linked list. Here more information.

// Include header file #include <iostream> using namespace std; // C++ program for // Delete a node at specified position // In Doubly linked list // Define class of linked list Node class LinkNode { public: int data; LinkNode *next; LinkNode *prev; LinkNode(int data) { this->data = data; this->next = nullptr; this->prev = nullptr; } }; class DoublyLinkedList { public: LinkNode *head; LinkNode *tail; DoublyLinkedList() { this->head = nullptr; this->tail = nullptr; } // Insert new node at end position void insert(int value) { // Create a new node LinkNode *node = new LinkNode(value); if (this->head == nullptr) { // Add first node this->head = node; this->tail = node; return; } // Add node at last position this->tail->next = node; node->prev = this->tail; this->tail = node; } // Display node element of doubly linked list void display() { if (this->head == nullptr) { cout << "Empty Linked List" << endl; } else { cout << "Linked List Head to Tail :" << endl; // Get first node of linked list LinkNode *temp = this->head; // iterate linked list while (temp != nullptr) { // Display node value cout << " " << temp->data; // Visit to next node temp = temp->next; } cout << "\nLinked List Tail to Head :" << endl; // Get last node of linked list temp = this->tail; // iterate linked list while (temp != nullptr) { // Display node value cout << " " << temp->data; // Visit to prev node temp = temp->prev; } } } void deleteNode(int position) { if (position < 1) { // Invalid position return; } if (this->head == nullptr) { // When linked list is empty cout << "Empty linked list" << endl; return; } if (position == 1) { // When remove head this->head = this->head->next; if (this->head != nullptr) { this->head->prev = nullptr; } else { // When linked list empty after delete this->tail = nullptr; } } else { LinkNode *temp = this->head; int n = 1; // Find deleted node position while (temp != nullptr && n < position) { // Visit to next node temp = temp->next; // Change new position n++; } if (temp == nullptr) { // Position are greater than length of linked list cout << "Deleted node position are not found" << endl; } else { // Separating deleted node // And combine next and previous node temp->prev->next = temp->next; if (temp->next != nullptr) { // When deleted intermediate nodes temp->next->prev = temp->prev; } else { // When delete last node this->tail = temp->prev; } delete temp; } } } }; int main() { DoublyLinkedList *dll = new DoublyLinkedList(); int position = 5; // Insert following linked list nodes dll->insert(11); dll->insert(22); dll->insert(33); dll->insert(44); dll->insert(55); dll->insert(66); dll->insert(77); cout << "Before delete node value " << position << endl; // Display all node dll->display(); cout << "\nAfter delete node value " << position << endl; dll->deleteNode(position); // Display all node dll->display(); return 0; }

Output

Before delete node value 5 Linked List Head to Tail : 11 22 33 44 55 66 77 Linked List Tail to Head : 77 66 55 44 33 22 11 After delete node value 5 Linked List Head to Tail : 11 22 33 44 66 77 Linked List Tail to Head : 77 66 44 33 22 11

Delete a Doubly Linked List node at a given position in C++

---

In this tutorial, we are going to learn how to delete a node in doubly linked list with the given position.

Let's see the steps to solve the problem.

• Write struct with data, prev and next pointers.

• Write a function to insert the node into the doubly linked list.

• Initialize the doubly linked list with dummy data.

• Initialize the position to delete the node.

• Iterate over the linked list and find the node with the given position to delete the node.

• Write a function to delete the node. Consider the following three cases while deleting the node.

  • If the node is head node, then move the head to next node.

  • If the node is middle node, then link the next node to the previous node

  • If the node is end node, then remove the previous node link.

C Exercises: Delete node from any position of a doubly linked list

Last update on December 20 2021 09:11:00 (UTC/GMT +8 hours)