If you want to practice data structure and algorithm programs, you can go through Java coding interview questions.
In this post, we will see about Doubly LinkedList implementation in java.
We have already seen the implementation of singly linked list. You can consider this as an extension of Singly linked list.It is quite complex to implement it as compared to singly linked list.
In doubly linked list, Node has data and pointers to next node and previous node. First node’s previous points to null and Last node‘s next also points to null, so you can iterate over linked list in both direction with these next and previous pointers.
An example of Doubly Linked List:
Node for doubly linked list can be presented as below:
|
1 2 3 4 5 6 7 8 9 10 11 |
class Node { public int data; public Node next; public Node prev; public void displayNodeData() { System.out.println("{ " + data + " } "); } } |
As you can see, we have one more extra reference(Node prev) in case of doubly linked list.
Let’s say, you want to do insert First operation in case of Doubly linked list, it will look like as below:
Doubly linked list in java example
Let’s implement Doubly Linked List in java.
Create a java file named DoublyLinkedList.java.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 |
package org.arpit.java2blog.algo; class Node { public int data; public Node next; public Node prev; public void displayNodeData() { System.out.println("{ " + data + " } "); } } public class DoublyLinkedList { private Node head; private Node tail; int size; public boolean isEmpty() { return (head == null); } // used to insert a node at the start of linked list public void insertFirst(int data) { Node newNode = new Node(); newNode.data = data; newNode.next = head; newNode.prev=null; if(head!=null) head.prev=newNode; head = newNode; if(tail==null) tail=newNode; size++; } // used to insert a node at the start of linked list public void insertLast(int data) { Node newNode = new Node(); newNode.data = data; newNode.next = null; newNode.prev=tail; if(tail!=null) tail.next=newNode; tail = newNode; if(head==null) head=newNode; size++; } // used to delete node from start of Doubly linked list public Node deleteFirst() { if (size == 0) throw new RuntimeException("Doubly linked list is already empty"); Node temp = head; head = head.next; head.prev = null; size--; return temp; } // used to delete node from last of Doubly linked list public Node deleteLast() { Node temp = tail; tail = tail.prev; tail.next=null; size--; return temp; } // Use to delete node after particular node public void deleteAfter(Node after) { Node temp = head; while (temp.next != null && temp.data != after.data) { temp = temp.next; } if (temp.next != null) temp.next.next.prev=temp; temp.next = temp.next.next; } // For printing Doubly Linked List forward public void printLinkedListForward() { System.out.println("Printing Doubly LinkedList (head --> tail) "); Node current = head; while (current != null) { current.displayNodeData(); current = current.next; } System.out.println(); } // For printing Doubly Linked List forward public void printLinkedListBackward() { System.out.println("Printing Doubly LinkedList (tail --> head) "); Node current = tail; while (current != null) { current.displayNodeData(); current = current.prev; } System.out.println(); } } |
Create another class named DoubleLinkedListMain as below:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
package org.arpit.java2blog.algo; public class DoubleLinkedListMain { public static void main(String args[]) { DoublyLinkedList myLinkedlist = new DoublyLinkedList(); myLinkedlist.insertFirst(5); myLinkedlist.insertFirst(6); myLinkedlist.insertFirst(7); myLinkedlist.insertFirst(1); myLinkedlist.insertLast(2); myLinkedlist.printLinkedListForward(); myLinkedlist.printLinkedListBackward(); System.out.println("================"); // Doubly Linked list will be // 1 -> 7 -> 6 -> 5 -> 2 Node node=new Node(); node.data=1; myLinkedlist.deleteAfter(node); myLinkedlist.printLinkedListForward(); myLinkedlist.printLinkedListBackward(); // After deleting node after 1,doubly Linked list will be // 2 -> 1 -> 6 -> 5 System.out.println("================"); myLinkedlist.deleteFirst(); myLinkedlist.deleteLast(); // After performing above operation, doubly Linked list will be // 6 -> 5 myLinkedlist.printLinkedListForward(); myLinkedlist.printLinkedListBackward(); } } |
When you run above program, you will get below output:
{ 1 }
{ 7 }
{ 6 }
{ 5 }
{ 2 }Printing Doubly LinkedList (tail –> head)
{ 2 }
{ 5 }
{ 6 }
{ 7 }
{ 1 }================
Printing Doubly LinkedList (head –> tail)
{ 1 }
{ 6 }
{ 5 }
{ 2 }
Printing Doubly LinkedList (tail –> head)
{ 2 }
{ 5 }
{ 6 }
{ 1 }
================
Printing Doubly LinkedList (head –> tail)
{ 6 }
{ 5 }
Printing Doubly LinkedList (tail –> head)
{ 5 }
{ 6 }
That’s all about Doubly linked list in java.
