Delete node at specified position from Doubly Linked List

In this article we will look at how to delete a node from a specified position in a doubly linked list.

To delete nodes from a specified position in doubly linked list, we will traverse the linked list till that node and change the target node's previous and next links.

Diagram

Algorithm

1. If the head is null then simply return.
2. If position is 1 then set head as head.next and head.prev as NULL.
3. Else, create a current pointer and set on head and traverse till that position using a for loop.
4. If current.next is not null, then
   1. current.prev.next=current.next;
   2. current.next.prev=current.prev;
5. Else
   1. current.prev.next=NULL;
   2. current.prev=NULL;

Complexity

• Time Complexity : O(n) , where n is the number of nodes in binary search tree.
• Space Complexity : O(1)

Code

# Java Code

import java.util.ArrayList;
import java.util.List;

class RemoveNodeDoublyLinkedList {
    private static class Node {
        int data;
        Node next, prev;

        Node(int data) {
            this.data = data;
            this.next = null;
            this.prev = null;
        }
    }

    private Node head;

    public void buildLinkedList(List<Integer> dataList) {
        if (dataList.isEmpty()) {
            head = null;
            return;
        }

        Node temp = new Node(dataList.get(0));
        head = temp;
        Node last = head;

        for (int i = 1; i < dataList.size(); i++) {
            temp = new Node(dataList.get(i));
            temp.prev = last;
            last.next = temp;
            last = temp;
        }
    }

    public void printLinkedList() {
        List<String> allNodesList = new ArrayList<>();
        Node temp = head;

        while (temp != null) {
            allNodesList.add(String.valueOf(temp.data));
            temp = temp.next;
        }

        System.out.println(String.join(" -> ", allNodesList));
    }

    public void deleteNode(int position) {
        if (head == null || position < 1) {
            System.out.println("Invalid position or empty list.");
            return;
        }

        if (position == 1) {
            head = head.next;
            if (head != null)
                head.prev = null;
            return;
        }

        Node current = head;
        for (int i = 1; current != null && i < position; i++) {
            current = current.next;
        }

        if (current == null) {
            System.out.println("Position out of range.");
            return;
        }

        if (current.prev != null)
            current.prev.next = current.next;
        if (current.next != null)
            current.next.prev = current.prev;
    }

    public static void main(String[] args) {
        List<Integer> linkedListElements = List.of(5, 10, 15, 20, 25);
        RemoveNodeDoublyLinkedList linkedList = new RemoveNodeDoublyLinkedList();
        linkedList.buildLinkedList(linkedListElements);

        System.out.println("Given Linked List:");
        linkedList.printLinkedList();

        System.out.println("Linked List after deleting node at position 3:");
        linkedList.deleteNode(3);
        linkedList.printLinkedList();
    }
}

Output

Given Linked List:
5 -> 10 -> 15 -> 20 -> 25
Linked List after deleting node at position 3:
5 -> 10 -> 20 -> 25