Delete a Doubly Linked List node at a given position

Last Updated on November 18, 2022 by Prepbytes

Introduction

In this article, we will discuss how to delete a doubly linked list node at a given position. Linked List is one of the most important topics for the interview of big tech giants like Samsung, Amazon, SquadStack, and lots more. In a coding interview, having a thorough understanding of Linked Lists might be a major benefit. Let’s move to our topic of how to delete a doubly linked list node at a given position

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 For doubly linked list deletion at specific position

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 N^th 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 N^th 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 3^rd 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 To Delete A Doubly Linked List node at a given position

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 the approach in more depth with some corner cases.

Algorithm To Delete A Doubly Linked List node at a given position

• 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, 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 To Delete A Doubly Linked List node at a given position

Code Implementation To Delete A Doubly Linked List node at a given position:

#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 To Delete A Doubly Linked List node at a given position: O(N), Since we have traversed through the list once.

In this article, we have discussed an efficient approach on how to delete a Doubly Linked List node at a given position. Linked List is one of the important data structures which will help you to move ahead in your career in the IT field, you can follow this link Linked List To Practice more questions on Linked List..

FAQ Related To Delete A Doubly Linked List Node At A Given Position

1. What are the 3 conditions for deleting a node in a linked list?

To delete a node from the linked list, we need to do the following steps.

1. Find the previous node of the node to be deleted.
2. Change the next of the previous node.
3. Free memory for the node to be deleted.
2. Why is deletion easier in a doubly linked list?

Deletion of nodes is easy as compared to a Singly Linked List. A singly linked list deletion requires a pointer to the node and previous node to be deleted but in the doubly linked list, it only required the pointer which is to be deleted.

3. What are the limitations of a double-linked list?

Disadvantages of Doubly Linked List:

1. In a doubly-linked list, each node has an extra pointer which requires extra space.
2. Doubly linked list operations require more pointers to be handled hence, more time.
3. Random access to elements is not allowed.