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

 



Thanks for feedback.



Read More....
Delete all occurrence of a node from Doubly Linked List
Remove duplicates from a sorted DLL
Remove duplicates from an unsorted Doubly Linked List
Reverse a doubly linked list