Doubly linked list using Java
Doubly linked list is slight alteration of singly linked list. If you haven’t gone through the singly linked list then I have also made a blog of it!
here if you note carefully, there are three components of node and start and end is null. The components here are previous →which points towards previous node which is null in the case of 1st node because there is no node before first node and same with the case of last node with respect to next node pointer.
Hence there are three components, we add a Node prev to class Node
public static class Node
{
int data;
Node next;
Node prev;
}
Now how to insert the values?
Algorithm :
Create a new node (Node name = new Node())
assign newnode data as data that we got from function
set newnode next as head and newnode previous as null
If head is not null then set newnode previous as newnode
Set head as newnode or head points towards newnode
Diagrammatic Explanation :
Code :
public static void insertatbeg(int data){
Node newnode = new Node();
newnode.data = data;
newnode.next = head;
newnode.prev = null;
if(head!=null){
head.prev = newnode;
}
head = newnode;
}
It’s really super simple, you take a fresh node and assign next pointer to head, previous pointer to null and data. And what if there are already nodes alive, at that time if you assign previous pointer as null then every node’s previous will be null. But we dont want it. So if there is no nodes then we need to assign both next and previous as null but if head is not null then we mark head of previous to newnode. Wait it’s not over yet. Everything you have done is only saved to newnode but inorder to make it global, we have to save head to newnode.
Traversal of linked list
Now it’s really cool that we can print the double linked list with same algorithm as linked list. Now, I wanted to ask you a question.
Print all the values of linked list in reverse order
How to do?
Code :
public static void reverseprintList()
{
Node currNode = head;
System.out.print(“LinkedList: “);
while (currNode.next != null) {
currNode = currNode.next;
}
while(currNode != null){
System.out.print(currNode.data + “ “);
currNode = currNode.prev;
}
}
Now as usual we while till we get last node and from there we go in reverse and at the same time, we print the value. The concept you should learn is that doubly linked list is Bidirectional
Now, instead of making each section and wasting your time, I have given all the operations code in next section.
All other operations :
→Insert at end
public static void insertatlast(int data){
Node newnode = new Node();
Node dummy = head;
newnode.data = data;
if(head == null){
newnode.next = null;
newnode.prev = null;
head = newnode;
}
else{
while(dummy.next != null){
dummy = dummy.next;
}
dummy.next = newnode;
newnode.prev = dummy;
newnode.next = null;
}
}
→Insert at any position
public static void insertpos(int n, int data){
Node newnode = new Node();
newnode.data = data;
Node dummy = head;
for(int i = 0; n>i; i++){
dummy = dummy.next;
}
newnode.next = dummy.next;
newnode.prev = dummy;
if(newnode.next != null){
dummy.next.prev = newnode;
}
dummy.next = newnode;
}
→Deletion can be done same as singly linked list
public static void delete(int pos){
Node newnode = new Node();
Node temp = new Node();
Node dummy = head;
if(dummy.next = null){
head = null;
}
for(int i = 0;pos>i;i++){
temp = dummy;
dummy = dummy.next;
newnode = dummy.next;
}
temp.next = dummy.next;
newnode = temp;
}
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — -
— Yours Mathav Krishnan