Delete a Doubly Linked List node at a given position

Introduction

One of the most crucial data structures to learn while preparing for interviews is the linked list. In a coding interview, having a thorough understanding of Linked Lists might be a major benefit.

Problem Statement

Given a doubly linked list and a position N. Our task is to delete the node of the doubly linked list at a given position N from the beginning.

Problem Statement Understanding

According to the problem statement, we will be given a doubly linked list and a position N; we have to delete the node present at the Nth position from the beginning.

Note: We will take 1 based indexing in this problem.

Let's understand this problem using some examples:

If the given doubly linked list is:

and N = 2

  • According to the problem statement, we need to delete the node present at position Nth from the given doubly linked list.
  • As we can see in the above example, the node present at position 2 is 8, which needs to be deleted.
  • So after deleting the node at position 2, the resultant linked list will be:

Let's see another example:

If the given doubly linked list is: 1 ←→ 2 ←→ 4 ←→ 5 ←→ 7 ←→ 8 and N = 3

  • In this case, we can see that the node present at 3rd position is the node with value 4. So we need to delete this node.
  • So after deleting the node at position 3, the resultant linked list will be 1 ←→ 2 ←→ 5 ←→ 7 ←→ 8.

Now I think from the above examples, the problem is clear. So let’s see how we can approach it.

Before moving to the approach section, try to think about how you can approach this problem.

  • If stuck, no problem, we will thoroughly see how we can approach this problem in the next section.

Let’s move to the approach section.

Approach

The approach will be straightforward.

  • We will start traversing through the list and the moment we reached the correct position i.e. the given position N, we will delete that node and connect its previous node with its next node.

Let's move to the algorithm section to see approach in more depth with some corner cases.

Algorithm

  • If the head of the list is NULL, that means the list is empty or if Nnext), now the next node of del has become pointer_to_head** node.
    • Check if the node to be deleted is not the first node, then update next of the previous node of del del->prev->next = del->next.
    • Also check, if the node to be deleted is not the last node, then update the prev pointer of the next node of del del->next->prev = del->prev and delete the del node.
  • Finally, output the desired linked list.

Dry Run


Code Implementation

#include 
using namespace std;

/* Structure of a doubly linked list node */
struct Node {
    int data;
    struct Node* next;
    struct Node* prev;
};

/* Using this function we will be deleting a specific node from the linked list */
void delete_node(struct Node** pointer_to_head, struct Node* del)
{
    if (*pointer_to_head == NULL || del == NULL)
        return;

    if (*pointer_to_head == del)
        *pointer_to_head = del->next;

    if (del->next != NULL)
        del->next->prev = del->prev;

    if (del->prev != NULL)
        del->prev->next = del->next;

    free(del);
}

/* Using this function we will delete node at position N from the linked list */
void deleteNodeAtPositionN(struct Node** pointer_to_head, int N)
{
    if (*pointer_to_head == NULL || N <= 0)
        return;

    struct Node* current = *pointer_to_head;
    int i;

    for (int i = 1; current != NULL && i < N; i++)
        current = current->next;

    if (current == NULL)
        return;

    delete_node(pointer_to_head, current);
}

/* Using this function we will insert a new node in the linked list at head */
void push(struct Node** pointer_to_head, int new_data)
{
    struct Node* new_node =
        (struct Node*)malloc(sizeof(struct Node));

    new_node->data = new_data;

    new_node->prev = NULL;

    new_node->next = (*pointer_to_head);

    if ((*pointer_to_head) != NULL)
        (*pointer_to_head)->prev = new_node;

    (*pointer_to_head) = new_node;
}

/* Using this function we will printing the content of linked list */
void printList(struct Node* head)
{
    while (head != NULL) {
        cout << head->data << " ";
        head = head->next;
    }
}

int main()
{
    struct Node* head = NULL;

    push(&head, 9);
    push(&head, 7);
    push(&head, 5);
    push(&head, 8);
    push(&head, 1);

    cout << "Doubly linked list before deletion :"<

						 

Output

Doubly linked list before deletion :
1 8 5 7 9
Doubly linked list after deletion :
1 5 7 9

Time Complexity: O(N), Since we have traversed through the list once.

So, In this blog, we have learned how to delete a Doubly Linked List node at a given position. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.

Previous post Find the first node of the loop in a Linked List
Next post Convert a given Binary Tree To Doubly Linked List | Set 3

Leave a Reply

Your email address will not be published. Required fields are marked *