Skip to main content

Delete a doubly linked list node at a given position

This article focuses on solving the problem of deleting a node at a given position in a Doubly Linked List. A Doubly Linked List is a data structure in which each node contains a value, a pointer to the next node, and a pointer to the previous node, allowing bidirectional traversal.

Before remove node at given position in doubly linked list After remove node at given position in doubly linked list

Problem Statement

The task is to design a program that can remove a node at a specified position in a Doubly Linked List. If the given position is valid, the program should adjust the pointers of the neighboring nodes to exclude the deleted node.

Example

Consider the following scenario:

Original Doubly Linked List: 11 → 22 → 33 → 44 → 55 → 66 → 77

Delete node at position 5.

Expected Result: 11 → 22 → 33 → 44 → 66 → 77

Idea to Solve

To solve this problem, we need to traverse the Doubly Linked List while counting the positions. Once the desired position is reached, we need to adjust the pointers of the neighboring nodes to bypass the node to be deleted.

Pseudocode

deleteNode(DoublyLinkedList list, int position):
    if position < 1:
        // Invalid position
        return
    if list.head is NULL:
        print "Empty linked list"
        return
    if position is 1:
        // Delete head node
        list.head = list.head.next
        if list.head is not NULL:
            list.head.prev = NULL
        else:
            list.tail = NULL
    else:
        temp = list.head
        n = 1
        // Find node at given position
        while temp is not NULL and n < position:
            temp = temp.next
            n = n + 1
        if temp is NULL:
            print "Deleted node position not found"
        else:
            temp.prev.next = temp.next
            if temp.next is not NULL:
                temp.next.prev = temp.prev
            else:
                // Delete tail node
                list.tail = temp.prev

Algorithm Explanation

  1. If the given position is less than 1, return as it's an invalid position.
  2. If the linked list is empty, print "Empty linked list" and return.
  3. If the position is 1:
    • Delete the head node by updating the head pointer.
    • If the list is not empty, update the prev pointer of the new head.
    • If the list becomes empty, update the tail pointer as well.
  4. If the position is not 1:
    • Traverse the list until the desired position is reached.
    • Update the pointers of neighboring nodes to bypass the node at the given position.
    • If the node to be deleted is the last node, update the tail pointer.

Code Solution

Time Complexity

  • For insertion, each insertion operation takes O(1) time.
  • For deletion, in the worst case, where the node to be deleted is at the end of the list, the time complexity is O(n), where n is the number of nodes in the linked list.




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment