JAVA Program for Deletion from Nth Position of a Doubly Linked List
JAVA Program to Delete a Node from the Nth Position
In this page we’ll take a look at a comprehensive explanation of Deleting a Node from a specific index of a Doubly Linked List, one of the most widely used operation on a Doubly Linked List
Steps to be followed while Deleting a Node from the Nth Position of a Doubly Linked List
- Check for the presence of Node in the List, if there exists some Nodes, Continue.
- Now, to delete a node from Nth position of the Doubly Linked List, we’ll have to delete and redirect various links of the Linked List.
- First of all the next pointer of the (n-1)th Node of the Linked List will now point to the address of the (n+1)th node of the Doubly Linked List.
- Now the Previous Pointer of the (n+1)th Node of the Linked List will now be re-directed to the address of (n-1)th node of the List.
Example:
If we have a list (10 –> 20 –> 30 –> 40 –> 50) and we have to delete a node on the Second Index of the List, that is i=2, then after deleting a node. Updated Linked list will be (10 –> 20 –> 40 –> 50) . We will be learning more about the whole process in the explanation below.
Algorithm to be used for the Deletion of a Node from a Specific Index of a Doubly Linked List
- IF(HEAD == NULL)
- RETURN
- ELSE
- NODE CURRENT = HEAD;
- INT POS =N;
- FOR(INT I = 1; I < POS; I++)
- CURRENT = CURRENT.NEXT
- IF(CURRENT == HEAD)
- HEAD = CURRENT.NEXT
- ELSE IF(CURRENT == TAIL)
- TAIL = TAIL.PREV
- ELSE
- CURRENT.PREV.NEXT = CURRENT.NEXT
- CURRENT.NEXT.PREV = CURRENT.PREV
- CURRENT = NULL
Java Program for Deletion from the Nth Position of a Doubly Linked List
Method 1
Method 2
Method 1
Run
import java.lang.*;
class DoublyLinkedList
{
Node head;
// not using parameterized constructor would by default
// force head instance to become null
// Node head = null; // can also do this, but not required
// Node Class
class Node
{
int data;
Node next, prev;
Node (int x) // parameterized constructor
{
data = x;
next = null;
prev = null;
}
}
public void insertBeginning (int data)
{
// Creating newNode memory & assigning data value
Node freshNode = new Node (data);
freshNode.next = head;
freshNode.prev = null;
// if DLL had already >=1 nodes
if (head != null)
head.prev = freshNode;
// changing head to this
head = freshNode;
}
// function for deleting Nth node
public void deletenth (int n)
{
if (head == null)
{
return;
}
else
{
Node current = head;
int pos = n;
for (int i = 1; i < pos; i++)
{
current = current.next;
}
if (current == head)
{
head = current.next;
}
else if (current == null)
{
current = current.prev;
}
else
{
current.prev.next = current.next;
current.next.prev = current.prev;
}
//Delete the middle node
current = null;
}
}
void printList ()
{
//Node current will point to head
Node curr = head;
if (head == null)
{
System.out.println ("List is empty");
return;
}
while (curr != null)
{
//Prints each node by increasing order of the pointer
System.out.print (curr.data + " ");
curr = curr.next;
}
System.out.println ();
}
}
class Main
{
public static void main (String args[])
{
DoublyLinkedList doublylist = new DoublyLinkedList ();
doublylist.insertBeginning (3);
doublylist.insertBeginning (2);
doublylist.insertBeginning (1);
doublylist.insertBeginning (4);
doublylist.insertBeginning (7);
System.out.println ("List before deletion : ");
doublylist.printList ();
doublylist.deletenth (2);
doublylist.deletenth (3);
System.out.println ("List after deleting 2nd node : ");
doublylist.printList ();
}
}
Output
List before deletion : 7 4 1 2 3 List after deleting 2nd node : 7 1 3
Method 2
Run
import java.lang.*;
// Node Class
class Node {
int data;
Node next, prev;
Node(int x) // parameterized constructor
{
data = x;
next = null;
prev = null;
}
}
class Main
{
static Node insertBeginning(Node head, int data)
{
// Creating newNode memory & assigning data value
Node newNode = new Node(data);
newNode.next = head;
newNode.prev = null;
// if DLL had already >=1 nodes
if(head !=null)
head.prev = newNode;
// changing head to this
head = newNode;
return head;
}
// function for deleting Nth node
static Node deletenth (int n, Node head)
{
if (head == null)
{
return head;
}
else
{
Node current = head;
int pos = n;
for (int i = 1; i < pos; i++)
{
current = current.next;
}
if (current == head)
{
head = current.next;
}
else if (current == null)
{
current = current.prev;
}
else
{
current.prev.next = current.next;
current.next.prev = current.prev;
}
//Delete the middle node
current = null;
}
return head;
}
static void printList (Node head)
{
//Node current will point to head
Node curr = head;
if (head == null)
{
System.out.println ("List is empty");
return;
}
while (curr != null)
{
//Prints each node by increasing order of the pointer
System.out.print (curr.data + " ");
curr = curr.next;
}
System.out.println ();
}
// required for insertAfterPosition() method
static int getLength(Node node){
int size=0;
// traverse to the last node each time incrementing the size
while(node!=null)
{
node = node.next;
size++;
}
return size;
}
public static void main(String args[])
{
Node head = null;
head = insertBeginning(head,3);
head = insertBeginning(head,2);
head = insertBeginning(head,1);
head = insertBeginning(head,4);
head = insertBeginning(head,7);
System.out.println ("List before deletion : ");
printList (head);
head=deletenth (2,head);
head=deletenth (3,head);
System.out.println ("List after deleting 2nd node : ");
printList (head);
}
}
Output
List before deletion : 7 4 1 2 3 List after deleting 2nd node : 7 1 3
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Doubly Linked List
- Introduction to Doubly Linked list in Data Structure
Click Here - Doubly Linked List in –
- Insertion in doubly linked list –
- Insertion at beginning in doubly linked list –
- Insertion at end in doubly linked list –
- Insertion at nth node in doubly linked list –
- Deletion in doubly linked list –
- Deletion from beginning in doubly linked list :
- Deletion from nth in doubly linked list :
- Deletion from end in doubly linked list :
- Insertion and Deletion in a doubly linked list :
- Insertion in the middle in a doubly linked list :
Doubly Linked List
- Introduction to Doubly Linked list in Data Structure
- Doubly Linked List in – C | C++ | Java
- Insertion in doubly linked list – C | C++ | Java
- Deletion in doubly linked list – C | C++ | Java
- Insertion and Deletion in doubly linked list – C | C++ | Java
- Insertion in the middle in a doubly linked list – C | C++ | Java
Login/Signup to comment