Do you think IIT Guwahati certified course can help you in your career?
No
Introduction
A linked list is a linear data structure that consists of nodes. Each Node contains a data field and a pointer to the next Node. In Linked List, unlike arrays, elements are not stored at contiguous memory locations but rather at different memory locations.Linked Lists are one of the most fundamental and important data structures having a wide range of applications. Linked Lists are also important from the perspective of interviews as well.
In a given doubly linked list, and a key X is given, we have to delete all the occurrences of the given key X from the linked list.
Explanation of Problem Statement
In this problem statement, we have deleted all the occurrences of the given key X from the Linked List. Let’s understand the problem using the example:-
E.g.:-
Input: 1<-> 2<-> 2<-> 3<-> 2<-> 4<-> 2<-> 2 X=2
Output: 1<->3<->4
As we see the above doubly linked list with the given value of X=2, we see 5 values of 2 match with the value of X, so we have to remove all the nodes with value 2 from the doubly linked list.
Then after removing all the occurrences of 2 from the list, we have output as 1 <-> 3 <-> 4.
Removing all the occurrences of given key X from the linked list means removing all the nodes from the Linked List with data equal to X.
Approach for Solving
The approach for solving the problem is simple: we have to traverse through the Linked List from start to end and apply a check for every node. If the current node data is equal to X, we will join the current node to its next node and delete the current node.
The steps we followed to make a doubly-linked list:-
We declared globally head and tail null, as doubly linked lists have access to the next and previous node addresses.
The steps to perform all the occurrences of X to be deleted from the linked list:-
If we have head==null, then nothing is there. Just return it.
We traverse the list one by one and check with the current.data==X if it’s found it’s a match, then call a delete function to delete the current node and link the next previous to the previous next , if current.data!=X, then we have to just shift to another node by current=current.next.
These two steps are one for creating and one for checking if it’s a match. Just delete it; otherwise, move it one step ahead.
Code
public class DoublyLinkedList {
// Creating Node Class for data and storing the next and prev node
class Node{
int data;
Node prev;
Node next;
public Node(int data){
this.data=data;
}
}
Node head=null;
Node tail=null;
// Delete the Node
public Node deleteNode(Node head,Node del){
// Base Condition
if(head==null||del==null){
return null;
}
// If the deleted node is head, then we perform it
if(head==del){
head=del.next;
}
// Change the next, only when we have not to delete the last node
if(del.next!=null){
del.next.prev=del.prev;
}
// Change the previous, only when we have not to delete the first node
if(del.prev!=null){
del.prev.next=del.next;
}
del=null;
return head;
}
//Delete all X elements in the Doubly Linked List
public void deleteX(int X){
if(head==null){
return;
}
Node current=head;
Node temp_time;
while(current!=null){
if(current.data==X){
temp_time=current.next;
head=deleteNode(head,current);
current=temp_time;
}
else {
current=current.next;
}
}
}
// We can add the node in the Doubly Linked List
public void addNode(int data){
Node newNode=new Node(data);
if(head==null){
head=tail=newNode;
head.prev=null;
tail.next=null;
}
else {
tail.next=newNode;
newNode.prev=tail;
tail=newNode;
tail.next=null;
}
}
// Print the Doubly Linked List.
public void printList(){
Node temp=head;
if(temp==null){
System.out.println("Doubly Linked List is Empty");
}
while(temp!=null){
System.out.print(temp.data+" ");
temp=temp.next;
}
}
public static void main(String[] args){
DoublyLinkedList dl=new DoublyLinkedList();
dl.addNode(1);
dl.addNode(2);
dl.addNode(2);
dl.addNode(3);
dl.addNode(2);
dl.addNode(4);
dl.addNode(2);
dl.addNode(2);
System.out.println("Original Doubly Linked List :");
dl.printList();
int X=2;
dl.deleteX(X);
System.out.println();
System.out.println("Final Doubly Linked List after delete all X: ");
dl.printList();
}
}
You can also try this code with Online Java Compiler
Now Let's take the above example and explain it furthermore in detail with each step working, in a dry-run manner:-
We choose value X=2, in which all the occurrences of node data value equal to 2 get removed.
We create two nodes for doing some operations so that the head of the linked list doesn't shift, now call a deleteX function to delete all the occurrences, and now declare current and temp_time in the deleteX function.
Now traverse the whole linked list until we have current !=null, with a condition statement over each current node if current.data!=X, then we move forward with current=current.next, if we encounter current.data==X then we have done the following steps:-
Now we have found the current.data==X, then we have to delete the current node.
For that, we have declared the temp_time node to store the address of current.next for further use.
Now we call a deleteNode function where we delete the Node of node data equal to X.
The action we do after calling the deleteNode function.
We perform the action we have to delete the head of the Linked List; then we have to just shift the head, as head=del.next;
Now we have to change the previous head node, as del.next.prev=del.prev.
Now we have to change the next, if we have not deleted the last node, as del.prev.next=del.next.
Now, at last, return the head of the linked list after applying the required modification.
After that present linked list gets modified.
Now call the print function to print the Linked List.
Let's perform by example:-
I= 1<-> 2<-> 2<-> 3 X=2
O= 1<->3
We have head=1, the we declare current =head=1 and temp_time
If current !=null we have a condition over current.data==X or !=X.
Here current =1 !=2 , then current=current.next=2.
Now current =2=2 , here current.data==X , then we assign temp_time=current.next=2 and call deleteNode function, after that current=temp_time=2.
1<->2<->3
Now current=2 =2 here current.data==X , then we assign temp_time=current.next=3 and call deleteNode function, after that current=temp_time=3.
1<->3
Now current=3!=2 here then current=current.next=null, while condition breaks as current are null, we come out from the loop and return head.
Now print the doubly linked list modified one is 1<-> 3 by removing all the given values of X from the Doubly Linked List.
Complexity
Now it's time to discuss the Time Complexity and Space Complexity problem for Delete all the occurrences of the given key in a Doubly Linked List. As we see, we are forming the linked list, which generally takes O(constant) time for each node creating at every time and space it occupies as a doubly-linked list for storing the next and previous address of the node.
Now, let’s talk about the Time Complexity after completion of the linked list, Time Complexity to delete all the occurrences of the X in the Linked List, as we see in the code. We are iterating from start to end of the list one by one to check current.data==X, which will happen in O(Length of Linked List==L), i.e., O(L) where L is the length of the doubly linked list.
If we talk about the Space Complexity, as we are just maintaining the created doubly linked list, we are not going to make duplicate, or we have not moved anywhere node by creating another node and assigning to create another linked list, we are just creating the variable Node for pointing the same Doubly Linked List, So the Space Complexity of the problem is O(1). We are not using any extra space.
Doubly Linked List contains a link element called first and last. Each link is linked with its next link using its next link. Each link is linked with its previous link using its previous link.
What are Time Complexity and Space Complexity for deleting all X elements in a list?
Time Complexity is O(N) and Space Complexity is O(1).
What is next in the Doubly Linked List?
Each link of a linked list contains a link to the next link called Next.
What is previous in the Doubly Linked List?
Each link of a linked list contains a link to the previous link called Previous.
What is the operation performed on the Doubly Linked List?
All the standard data structure operations we can perform over it. Like: Insertion, Deletion, etc.
Conclusion
In this blog, we learn about the Doubly Linked List, how to create the DLL, how the delete operation performs in the Doubly Linked List, and how the next and prev of the node maintain the address of the next and previous the current node. We also discussed the time and space complexity with a dry run over an example.
Apart from this, you can practice a wide range of coding questions commonly asked in interviews in Coding Ninjas Studio. Along with coding questions, we can also find the interview experience of scholars working in renowned product-based companies here.