Doubly Linked List
Doubly Linked List

Doubly Linked List

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
  • Java implementation code for doubly linked list
  • Doubly linked list java implementation code explanation
    • Add to head doubly linked list
    • Add to tail doubly linked list
    • Delete from doubly linked list
    • Delete from head doubly linked list
    • Insert to doubly linked list
    • Delete in doubly linked list
  • Quick Rap

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

 

"<yoastmark
Add to head empty list

 

"<yoastmark
Add to head non- empty list

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.

"<yoastmark
Add to tail non-empty list

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.

Audy Ranathunga

Audy Ranathunga, Author of myexamnote is our most experienced author. She has been working as a blog post writer for 4 years. She joined with myexamnote before 1 year ago and she has contribute lots of valuable posts for readers.

Leave a Reply