Queue using Array
Here we have already learned implementation of Queues using Stack in C , click the button below to learn the implementation of queue using array
Programming
Aptitude
Syllabus
Interview Preparation
Interview Exp.
Off Campus
Java program for deletion in doubly linked list
Java Program for Deletion in Doubly Linked List
Now Since we’ve already learnt enough about the Insertion Operation in a Doubly Linked List, let’s learn about the Deletion operation. We have three kinds of deletion in singly linked list in the same way we have three kinds of deletion in doubly linked list are as follows:
- Deletion at the beginning of the linked list.
- Deletion at Nth node/in middle of the linked list.
- Deletion at the end of the linked list.
Deletion from the Beginning of a Doubly Linked List
For deletion at the beginning first we have to create a linked list and have to check if the list is empty or not. If it is empty then both head and tail points towards the new node . if it is not empty then we can delete our first node very easily.
Algorithm
- if (head == null) // if ended loop closed
- make ptr = head
- make head = head->next
- make head->prev = NULL
- free the pointer node
- END.
Deletion from the Specific Position of a Doubly Linked List
Deleting the nth node is as simple as it was in singly linked list. For deleting the node on nth node we have to go through the same process of deletion in beginning but there is a slight change this time we have to delete the nth node. So when you insert a function of deletion it should be for nth node.
Algorithm
- if (head == null) // if ended
- make temp = head so we can freely move our pointer
- temp->data= node
- make temp = temp->next // loop ended
- Make pointer ptr = temp->next
- temp->next = ptr->next
- make ptr->next->prev = temp
- free temp node
- END
Deletion from the End of a Doubly Linked List
Here we have to delete the node from the end. It requires the traversing of list in order to reach the last node of the doubly linked list and after that we can run loop to delete a node from the end of the doubly linked list.
Algorithm.
- (head == null) then return.
- make temp = head
- while temp ->next != NULL
- make temp = temp->next // [loop ended]
- make temp->previous->next = NULL
- Free temp node
- Return
Java code for deletion in a doubly linked list
public class PrepInsta
{
//Constitiute a node of the doubly linked list
class Node{
int data;
Node prev;
Node next;
public Node(int data) {
this.data = data;
}
}
// Function to traverse and print the linked list
public void display() {
Node temp = head;
while (temp != null) {
System.out.print(temp.data + "–>");
// Set temp to point to the next node
temp = temp.next;
}
System.out.println("END");
}
//Constitiute the head and tail of the doubly linked list
Node head, tail = null;
//appendAtEnd function will add a node to the end of the list
public void addNode(int data) {
//Create a new node
Node newNode = new Node(data);
//Check if the list is empty
if(head == null) {
//Both head and tail will point towards the newNode
head = tail = newNode;
//head's previous will point towards null
head.prev = null;
//tail's next will point towards null, as it is the last node of the list
tail.next = null;
}
//Append newNode as new tail of the list
else {
//newNode will be added after tail such that tail's next will point to newNode
tail.next = newNode;
//newNode's previous will point to tail
newNode.prev = tail;
//newNode will become new tail
tail = newNode;
//As it is last node, tail's next will point to null
tail.next = null;
}
}
public void deleteInitial() {
if(head == null) {
System.out.println("List is empty");
return;
}
else {
//testing for the presence of a single node in the list, If not, Then head and tail will be re-directed
if(head != tail) {
head = head.next;
}
//if only one node exist both head and tail will be redirected to null
else {
head = tail = null;
}
}
}
public void deleteLast() {
if(head == null) {
return;
}
else {
if(head != tail) {
tail = tail.prev;
tail.next = null;
}
else {
head = tail = null;
}
}
}
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 == tail) {
tail = tail.prev;
}
else {
current.prev.next = current.next;
current.next.prev = current.prev;
}
//Delete the middle node
current = null;
}
}
//print() will print the nodes of the doubly linked list
void print() {
//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();
}
public static void main(String[] args) {
PrepInsta dList = new PrepInsta();
dList.addNode(10);
dList.addNode(20);
dList.addNode(30);
dList.addNode(40);
dList.addNode(50);
System.out.println("Initial Doubly Linked List: ");
dList.print();
dList.deleteInitial();
System.out.println("Doubly Linked List after Deletion from Beginning: ");
dList.print();
dList.deleteLast();
System.out.println("Doubly Linked List after Deletion from End: ");
dList.print();
dList.deletenth(2);
System.out.println("Doubly Linked List after Deletion from Nth Position: ");
dList.print();
}
}Initial Doubly Linked List: 10 20 30 40 50 Doubly Linked List after Deletion from Beginning: 20 30 40 50 Doubly Linked List after Deletion from End: 20 30 40 Doubly Linked List after Deletion from Beginning: 20 40
Login/Signup to comment