Hi! Readers, today I am going to share my knowledge with you regarding doubly linked lists. Doubly linked list is a one of data structure and algorithm. I have published many posts related to data structures and algorithms. So I have thought to publish another post related to data structures and algorithm today. Doubly linked lists also mostly same like singly linked lists. There are small differences. Let’s start the today’s content.
Topic Outline |
|
What are doubly linked lists?
Doubly linked list is a data structure we use in programming. It also consists of nodes. Unlike singly linked list, it has three parts in the nodes. In singly linked list nodes there were only two parts. Those three parts are prev, info and next. Prev also similar like next. Next implies what is the node after the current node. Likewise prev implies what is the previous node for the current node. So doubly linked list connected from both sides.
Java implementation code for doubly linked list
</span></p>
<pre class="wp-block-syntaxhighlighter-code"><span style="font-family: arial, helvetica, sans-serif;">
class DllNode{
char info;
DllNode prev,next;
DllNode(char el){
infoe=el;
prev=next=null;
}
DllNode(DllNode p, char el, DllNode n){
prev=p;
info=el;
next=n;
}
}
class List{
protected DllNode head,tail;
public void list(){
head=tail=null;
}
public void addToTail(char el){
if(tail==null)
head=tail= new DllNode(el);
else{
tail.next = new DllNode(tail,el,null);
tail=tail.next;
}
}
public void addToHead(char el){
if(tail==null)
head=tail= new DllNode(el);
else{
head = new DllNOde(null,el,head);
head.next.prev=head;
if(tail==null)
tail=head;
}
}
public char deleteFromHead(){
char el =head.info;
if(head==tail)
head=tail=null;
else{
head=head.next;
head.prev=null;
}
return el;
}
public char deleteFromTail(){
char el = tail.info;
if(heaf==tail)
head=tail=null;
else{
tail=tail.prev;
tail.next=null;
}
return el;
}
public char delete(char el){
if(head==tail && el=head.info)
head=tail=null;
else{
if(el==head.info){
head=head.next;
head.prev=null;
}
else{
DllNode temp;
for(temp=head.nexct;temp!=null&&temp.info!=el;temp=temp.next);
if(temp!=null)
temp.prev.next=temp.next;
temp.next.prev=temp.prev;
else
if(temp==tail)
tail=tail.prev;
tail.next=null;
}
}
return el;
}
public void insert(char el){
if(head==null)
head=tail= new DllNode(el);
else if(el<head.info)
head=new DllNode(null,el,head);
head.next.prev=head;
else
DllNode temp;
for(temp=head.next;temp!=null&&temp.info<el;temp=temp.next);
if(temp!=null)
temp.prev.next=temp.prev= new DllNode(temp.prev,el,temp);
else
tail.next = new DllNode(tail,el);
tail=tail.next;
}
}</span></pre>
<p><span style="font-family: arial, helvetica, sans-serif;">
Doubly linked list java implementation code explanation
Add to head doubly linked list
When a node added to the head. There are no nodes before to the adding node. It is the first node in the linked list. Therefore both prev and next are null. Then both head and tail nodes will take new node address. If the linked list is not empty then the adding will be like this. Currently head and tail have a node’s address value. That node prev and next is null. When adding a new node that node needs to be the new head. So head is assign to the node. Now the head is the new node. New node and previous node should also linked. The new node next value is the previous head value. We can change in the node creation time from code. The previous head node’s prev value should also updated to the new head address. It is done by head.next.prev = head statement. Head.next = 100 node. So head.next.prev = 100.prev. Let’s see an example.
There is a doubly linked list with 1 node.
Head address – 100
Tail address – 100
100 node’s prev = null
100 node’s next = null
New adding node = 99
99 node’s prev = null
99 node’s next = 100 = head value
New head value = 99
New tail value = 100
Head.next = 99.next = 100
New 100 node’s prev = 99
Add to tail
Add to tail is also similar to add to head method. If the list is empty then a new node will added and head and tail nodes will take new node address. If not a new node will added to the linked list. Tail node address will change to the new node address. Head node address will remain as it is. In add to head previous head node’s prev address needs to update. In here previous tail node’s next value should update. Because when adding to the head new node is after the previous node. So next value should updated. New nodes prev value we can update at the creation time. It has to take the tail node’s address in the node adding time.
Delete from head
If the both head and tail nodes consists the same value then that means there is only one node in the linked list. After removing that node both head and tail should take the null. Therefore when there is only one node in the list we can simply tell head = tail = null. If there are nodes in the list then after removing the current head next node after the current head should be the head. So in that node’s prev should be null. Let’s see an example.
There is a linked list with three nodes. They are 99,100,101. We are removing the 99 node.
Current head = 99
Current Tail = 101
99 node prev = null
99 node next = 100
100 node prev = 99
100 node next = 101
Deleting node = 99
New head = 100
New 100 node prev = null
Delete from tail
Deleting from tail is also similar to deleting from head. If there is only one node both head and tail we can assign as null. There are nodes in the list already then after removing tail node address should change. The previous node to the current tail node should be now new tail. That node next value should be null.
Delete operation
This is also similar to the deletion operation we have spoken in the linked list. As always there is only one node in the list we can simply make head and tail = null. If we are deleting the head node this would similar like delete from head operation. If we are deleting middle node then there are things to be changed. Neither head nor tail value will be changed. After deleting a node in middle, the beside nodes next and prev addresses needs to change. For the deletion we use self for loop. We take a temp node and assign head.next value to the temp. temp.info = el we looked for that is node we wanted to delete. At that time loop will ended. And also the increment will be temp.next. Until the condition met temp will increasing with temp.next.
Insert operation
If you remember the singly linked list insert operation this is also similar to that. But we don’t need two nodes for this. In singly linked list we used two nodes for this. Because here we know what are the prev and next nodes. So we can do the insertion using one node only. The linked will be sorted and to the right place the node would added. After the adding like in the deletion beside node’s prev and next addresses have to updated.
Quick Rap
What are doubly linked lists?
Doubly linked lists are data structure.
- They have three parts in the node.
- Those are prev,info,next.
- Prev – indicate the previous node connected to the node
- Info – element or data inside the node.
- Next – contain next node address to the current node.
Doubly linked list operations
- Add to head
- Add to tail
- Delete from head
- Delete from tail
- Add to list
- Delete from list
Conclusion
Now I am going to conclude the this post. Hope you get more valuable information from this. If you like this post please share and comment. If you like to learn singly check our singly linked list post also. We will meet again with another nice topic until goodbye all.
