Queue using doubly linked list Java

This Tutorial Explains the Doubly Linked List in Java along with Double Linked List Implementation, Circular Doubly Linked List Java Code & Examples:

The linked list is a sequential representation of elements. Each element of the linked list is called a Node. One type of linked list is called Singly linked list.

In this, each node contains a data part that stores actual data and a second part that stores pointer to the next node in the list. We have already learned the details of the singly linked list in our previous tutorial.

=> Check ALL Java Tutorials Here.

Doubly Linked List In Java

A linked list has another variation called doubly linked list. A doubly linked list has an additional pointer known as the previous pointer in its node apart from the data part and the next pointer as in the singly linked list.

A node in the doubly linked list looks as follows:

Here, Prev and Next are pointers to the previous and next elements of the node respectively. The Data is the actual element that is stored in the node.

The following figure shows a doubly linked list.

The above diagram shows the doubly linked list. There are four nodes in this list. As you can see, the previous pointer of the first node, and the next pointer of the last node is set to null. The previous pointer set to null indicates that this is the first node in the doubly linked list while the next pointer set to null indicates the node is the last node.

Advantages

1. As each node has pointers pointing to the previous and next nodes, the doubly linked list can be traversed easily in forward as well as backward direction
2. You can quickly add the new node just by changing the pointers.
3. Similarly, for delete operation since we have previous as well as next pointers, the deletion is easier and we need not traverse the whole list to find the previous node as in case of the singly linked list.

Disadvantages

1. Since there is an extra pointer in the doubly linked list i.e. the previous pointer, additional memory space is required to store this pointer along with the next pointer and data item.
2. All the operations like addition, deletion, etc. require that both previous and next pointers are manipulated thus imposing operational overhead.

Implementation In Java

The implementation of doubly linked list in Java comprises of creating a doubly-linked list class, the node class and adding nodes to the doubly linked list

The addition of new nodes is usually done at the end of the list. The below diagram shows the addition of the new node at the end of the doubly linked list.

As shown in the above diagram, to add a new node at the end of the list, the next pointer of the last node now points to the new node instead of null. The previous pointer of the new node points to the last node. Also, the next pointer of the new node points to null, thereby making it a new last node.

The program below shows Java implementation of a doubly-linked list with the addition of new nodes at the end of the list.

class DoublyLinkedList { //A node class for doubly linked list class Node{ int item; Node previous; Node next; public Node[int item] { this.item = item; } } //Initially, heade and tail is set to null Node head, tail = null; //add a node to the list public void addNode[int item] { //Create a new node Node newNode = new Node[item]; //if list is empty, head and tail points to newNode if[head == null] { head = tail = newNode; //head's previous will be null head.previous = null; //tail's next will be null tail.next = null; } else { //add newNode to the end of list. tail->next set to newNode tail.next = newNode; //newNode->previous set to tail newNode.previous = tail; //newNode becomes new tail tail = newNode; //tail's next point to null tail.next = null; } } //print all the nodes of doubly linked list public void printNodes[] { //Node current will point to head Node current = head; if[head == null] { System.out.println["Doubly linked list is empty"]; return; } System.out.println["Nodes of doubly linked list: "]; while[current != null] { //Print each node and then go to next. System.out.print[current.item + " "]; current = current.next; } } } class Main{ public static void main[String[] args] { //create a DoublyLinkedList object DoublyLinkedList dl_List = new DoublyLinkedList[]; //Add nodes to the list dl_List.addNode[10]; dl_List.addNode[20]; dl_List.addNode[30]; dl_List.addNode[40]; dl_List.addNode[50]; //print the nodes of DoublyLinkedList dl_List.printNodes[]; } }

Output:

Nodes of doubly linked list:
10 20 30 40 50

Apart from adding a new node at the end of the list, you can also add a new node at the beginning of the list or in between the list. We leave this implementation to the reader so that the readers can understand the operations in a better way.

Circular Doubly Linked List In Java

A circular doubly linked list is one of the complex structures. In this list, the last node of the doubly linked list contains the address of the first node and the first node contains the address of the last node. Thus in a circular doubly linked list, there is a cycle and none of the node pointers are set to null.

The following diagram shows the circular doubly linked list.

As shown in the above diagram, the next pointer of the last node points to the first node. The previous pointer of the first node points to the last node.

Circular doubly linked lists have wide applications in the software industry. One such application is the musical app which has a playlist. In the playlist, when you finish playing all the songs, then at the end of the last song, you go back to the first song automatically. This is done using circular lists.

Advantages of a Circular Double Linked List:

1. The circular doubly linked list can be traversed from head to tail or tail to head.
2. Going from head to tail or tail to head is efficient and takes only constant time O [1].
3. It can be used for implementing advanced data structures including Fibonacci heap.

Disadvantages:

1. As each node needs to make space for the previous pointer, extra memory is required.
2. We need to deal with lots of pointers while performing operations on a circular doubly linked list. If pointers are not handled properly, then the implementation may break.

The below Java program shows the implementation of the Circular doubly linked list.

import java.util.*; class Main{ static Node head; // Doubly linked list node definition static class Node{ int data; Node next; Node prev; }; // Function to insert node in the list static void addNode[int value] { // List is empty so create a single node furst if [head == null] { Node new_node = new Node[]; new_node.data = value; new_node.next = new_node.prev = new_node; head = new_node; return; } // find last node in the list if list is not empty Node last = [head].prev; //previous of head is the last node // create a new node Node new_node = new Node[]; new_node.data = value; // next of new_node will point to head since list is circular new_node.next = head; // similarly previous of head will be new_node [head].prev = new_node; // change new_node=>prev to last new_node.prev = last; // Make new node next of old last last.next = new_node; } static void printNodes[] { Node temp = head; //traverse in forward direction starting from head to print the list while [temp.next != head] { System.out.printf["%d ", temp.data]; temp = temp.next; } System.out.printf["%d ", temp.data]; //traverse in backward direction starting from last node System.out.printf["\nCircular doubly linked list travesed backward: \n"]; Node last = head.prev; temp = last; while [temp.prev != last] { System.out.printf["%d ", temp.data]; temp = temp.prev; } System.out.printf["%d ", temp.data]; } public static void main[String[] args] { //the empty list Node l_list = null; // add nodes to the list addNode[40]; addNode[50]; addNode[60]; addNode[70]; addNode[80]; //print the list System.out.printf["Circular doubly linked list: "]; printNodes[]; } }

Output:

Circular doubly linked list: 40 50 60 70 80
Circular doubly linked list travesed backward:
80 70 60 50 40

In the above program, we have added the node at the end of the list. As the list is circular, when the new node is added, the next pointer of the new node will point to the first node and the previous pointer of the first node will point to the new node.

Similarly, the previous pointer of the new node will point to the current last node which will now become the second last node. We leave the implementation of adding a new node at the beginning of the list and in between the nodes to the readers.

Frequently Asked Questions

Q #1] Can the Doubly Linked List be circular?

Answer: Yes. It is a more complex data structure. In a circular doubly linked list, the previous pointer of the first node contains the address of the last node and the next pointer of the last node contains the address of the first node.

Q #2] How do you create a Doubly Circular Linked List?

Answer: You can create a class for a doubly circular linked list. Inside this class, there will be a static class to represent the node. Each node will contain two pointers previous and next and a data item. Then you can have operations to add nodes to the list and to traverse the list.

Q #3] Is Doubly Linked List linear or circular?

Answer: The doubly linked list is a linear structure but a circular doubly linked list that has its tail pointed to head and head pointed to tail. Hence its a circular list.

Q #4] What is the difference between the Doubly linked list and the Circular linked list?

Answer: A doubly linked list has nodes that keep information about its previous as well as next nodes using the previous and next pointers respectively. Also, the previous pointer of the first node and the next pointer of the last node is set to null in the doubly linked list.

In the circular linked list, there is no start or end nodes and the nodes form a cycle. Also, none of the pointers are set to null in the circular linked list.

Q #5] What are the Advantages of a Doubly Linked List?

Answer: The Advantages of the Doubly Linked List are:

1. It can be traversed in forward as well as backward direction.
2. Insertion operation is easier as we need not traverse the whole list to find the previous element.
3. Deletion is efficient as we know that the previous and next nodes and manipulating is easier.

Conclusion

In this tutorial, we discussed the Doubly linked list in Java in detail. A doubly linked list is a complex structure wherein each node contains pointers to its previous as well as the next nodes. The management of these links is sometimes difficult and can lead to the breakdown of code if not handled properly.

Overall the operations of a doubly-linked list are more efficient as we can save the time for traversing the list as we have got both the previous and next pointers.

The circular doubly linked list is more complex and they form a circular pattern with the previous pointer of the first node pointing to the last node and the next pointer of the last node pointing to the first node. In this case, also, the operations are efficient.

With this, we are done with the linked list in Java. Stay tuned for many more tutorials on searching and sorting techniques in Java.

=> Visit Here For The Exclusive Java Training Tutorial Series.

Video liên quan