Deletion

Deleting elements from different positions in a doubly linked list, including from the beginning, end, and specific positions

Deletion At Beginning

Check if the list is empty

If the head is NULL (list is empty), simply return NULL.

Save the current head node in a temporary variable

Assign the current head node to a temporary variable (temp).

Move the `head` pointer to the `next` node

Update head to point to the next node of the current head.

Update the `prev` pointer of the new head (if it exists)

If the new head is not NULL, set its prev pointer to NULL.

Delete the old head node

Deallocate the memory for the node stored in temp.

Return the updated head pointer

Return the new head.

// deletionatbeginning.cpp
#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* prev;
    Node* next;
    Node(int d) {
        data = d;
        prev = NULL;
        next = NULL;
    }
};

Node* delHead(Node* head) {
    if (head == NULL) return NULL;
    
    Node* temp = head;
    head = head->next;
    
    if (head != NULL) {
        head->prev = NULL;
    }
    
    delete temp;
    return head;
}

void display(Node* head) {
    Node* curr = head;
    while (curr != NULL) {
        cout << curr->data << " ";
        curr = curr->next;
    }
    cout << endl;
}

int main() {
    Node* head = new Node(1);
    head->next = new Node(2);
    head->next->prev = head;
    head->next->next = new Node(3);
    head->next->next->prev = head->next;
    
    cout << "Original Linked List: ";
    display(head);
    
    cout << "After Deletion at the beginning: ";
    head = delHead(head);
    display(head);
    
    return 0;
}

# deletionatbeginning.py
class Node:
 def __init__(self, data):
     self.data = data
     self.prev = None
     self.next = None

def delHead(head):
 if head is None:
     return None
 temp = head
 head = head.next
 if head is not None:
     head.prev = None
 del temp
 return head

def display(head):
 curr = head
 while curr:
     print(curr.data, end=" ")
     curr = curr.next
 print()

if __name__ == "__main__":
 # Create the doubly linked list
 head = Node(1)
 head.next = Node(2)
 head.next.prev = head
 head.next.next = Node(3)
 head.next.next.prev = head.next

 print("Original Linked List: ", end="")
 display(head)

 print("After Deletion at the beginning: ", end="")
 head = delHead(head)
 display(head)

console.log("We're Working");

Deletion At Position

Handle the case of an empty list

If head is NULL, return head as the list is already empty.

Initialize a traversal pointer

Set a pointer curr to the head of the list.

Traverse the list to locate the node at the given position

Use a loop to move curr to the node at position pos:
For each iteration, move curr to the next node.
Stop when the desired position is reached or the end of the list is encountered.

Handle invalid positions

If curr is NULL after traversal, the position is invalid. Return head without making changes.

Update the pointers to remove the node

If the node has a previous node (curr->prev is not NULL):
Update the next pointer of the previous node to skip the current node.
If the node has a next node (curr->next is not NULL):
Update the prev pointer of the next node to skip the current node.

Update the head pointer if necessary

If the node to be deleted is the head node, update head to point to the next node.

Delete the node

Deallocate the memory for the node curr.

Return the updated head pointer

Return the modified head pointer.

//deletionatposition.cpp
#include <iostream>
using namespace std;
struct Node {
int data;
Node * prev;
Node * next;
Node(int d) {
    data = d;
    prev = next = NULL;
}
};
Node * delPos(Node * head, int pos) {
if (!head)
    return head;

Node * curr = head;
for (int i = 1; curr && i < pos; ++i) {
    curr = curr -> next;
}
if (!curr)
    return head;
if (curr -> prev)
    curr -> prev -> next = curr -> next;
if (curr -> next)
    curr -> next -> prev = curr -> prev;
if (head == curr)
    head = curr -> next;
delete curr;
return head;
}
void display(Node * head) {
Node * curr = head;
while (curr != nullptr) {
    cout << curr -> data << " ";
    curr = curr -> next;
}
}

int main() {
struct Node * head = new Node(1);
head -> next = new Node(2);
head -> next -> prev = head;
head -> next -> next = new Node(3);
head -> next -> next -> prev = head -> next;

cout << "Original Linked List: ";
display(head);
cout<<endl;
cout << "After Deletion at the position 2: ";
head = delPos(head, 2);

display(head);

return 0;
}

# deletionatposition.py
class Node:
 def __init__(self, data):
     self.data = data
     self.prev = None
     self.next = None

def delPos(head, pos):
 if not head:
     return head

 curr = head
 for i in range(1, pos):
     if curr is None:
         return head
     curr = curr.next

 if not curr:
     return head

 if curr.prev:
     curr.prev.next = curr.next
 if curr.next:
     curr.next.prev = curr.prev
 if head == curr:
     head = curr.next

 del curr
 return head

def display(head):
 curr = head
 while curr:
     print(curr.data, end=" ")
     curr = curr.next
 print()

if __name__ == "__main__":
 head = Node(1)
 head.next = Node(2)
 head.next.prev = head
 head.next.next = Node(3)
 head.next.next.prev = head.next

 print("Original Linked List: ", end="")
 display(head)

 print("After Deletion at the position 2: ", end="")
 head = delPos(head, 2)
 display(head)

console.log("We're Working");

Deletion At Tail

Check if the list is empty

If head is NULL, return NULL as the list is empty.
Handle the case of deleting the head node:

If pos is 1:

Move head to the next node.
If the new head is not NULL, set its prev pointer to NULL.
Delete the old head node.
Return the updated head.

Traverse the list to locate the node

Initialize a pointer curr to head. Use a loop to move curr to the node at position pos:
For each iteration, move curr to the next node.
Stop if curr is NULL (end of list) or the desired position is reached.

Handle invalid positions

If curr is NULL after traversal, the position is invalid. Return the original head without changes.

Update the pointers to remove the node

If curr is NULL after traversal, the position is invalid. Return the original head without changes.

Handle invalid positions

If the node has a previous node (curr->prev is not NULL):

Update the next pointer of the previous node to skip the current node.

If the node has a next node (curr->next is not NULL):

Update the prev pointer of the next node to skip the current node.

Delete the node

Deallocate the memory for curr.

Return the updated head pointer

Return the modified head pointer.

//deletionatend.cpp
#include <iostream>
using namespace std;

struct Node {
int data;
Node *prev;
Node *next;
Node(int d) {
    data = d;
    prev = NULL;
    next = NULL;
}
};
Node *delLast(Node *head) {
if (head == NULL)
    return NULL;
if (head->next == NULL) {
    delete head;
    return NULL;
}
Node *curr = head;
while (curr->next != NULL)
    curr = curr->next;
curr->prev->next = NULL;
delete curr; 
return head;
}

void display(Node *head) {
Node *curr = head;
while (curr != NULL) {
    cout << curr->data << " ";
    curr = curr->next;
}
}

int main() {
struct Node *head = new Node(1);
head->next = new Node(2);
head->next->prev = head;
head->next->next = new Node(3);
head->next->next->prev = head->next;

cout<<"Original Linked List: ";
display(head);
cout<<endl;
cout<<"After Deletion at the end: ";
head = delLast(head);

display(head);

return 0;
}

# deletionatend.py
class Node:
 def __init__(self, data):
     self.data = data
     self.prev = None
     self.next = None

def delLast(head):
 if head is None:
     return None
 if head.next is None:
     del head
     return None
 curr = head
 while curr.next is not None:
     curr = curr.next
 curr.prev.next = None
 del curr
 return head

def display(head):
 curr = head
 while curr is not None:
     print(curr.data, end=" ")
     curr = curr.next
 print()

if __name__ == "__main__":
 # Create the doubly linked list
 head = Node(1)
 head.next = Node(2)
 head.next.prev = head
 head.next.next = Node(3)
 head.next.next.prev = head.next

 print("Original Linked List: ", end="")
 display(head)

 print("After Deletion at the end: ", end="")
 head = delLast(head)

 display(head)

console.log("We're Working");

Deletion

On this page