How to Perform Union of Two Linked Lists Using Priority Queue in Java? Example Tutorial

Firstly, The Linked list shall be introduced, then how priority queue in java is been used, Then after that, we shall carry on on the main task.  What is LinkedList? A linked list is a data structure in which each node(element) holds the reference to the next node. You don’t need to go through the struggle of searching the exact node in the link list, all you have to do is go through the previous node because it holds the reference to the next node, then you can easily access it.
You need to know that the Java LinkedList class uses a doubly linked list to store the elements. It provides a linked-list data structure. It inherits the AbstractList class and implements List and Deque interfaces.

Things to note in Java Linked list:

• Java LinkedList class maintains insertion order.
• Java LinkedList class can contain duplicate elements.
• Java LinkedList class is non-synchronized.
• Java LinkedList class can be used as a list, stack, or queue.

In the Java LinkedList class, manipulation is fast because no shifting needs to occur.

In the Java linked list, elements are linked using pointers. A node represents an element in a linked list which have some data and a pointer pointing to the next node. It can grow and shrink at runtime by allocating and deallocating memory. 

So there is no need to give the initial size of the linked list. Its structure looks like as shown in the image below.

Fig 1.0: Linked list.

Priority Queue

A priority queue is a Data Structure, a kind of queue in java. Which means it is an extension of the queue. Priority queue gives priority to elements stored in it. The Regular queue data structure is that the first item that goes in is definitely the first to get out (FIFO). 

The insert and remove operations are known as enqueue and dequeue. But, in the priority queue, it may not always be like that. It works based on priority depending on which item(s) in the data structure you give priority to. 

The priority queue supports only comparable elements, which means that the elements are either arranged in an ascending or descending order. 

Note that, In Priority Queue:

• Every element in it has some priority associated with it either higher or lower.
• An element with the higher priority will be deleted before the deletion of the lesser priority.
• If two elements in a priority queue have the same priority, they will be arranged using the FIFO principle.

Now, Let’s solve the task of finding the Union of Two Linked Lists Using Priority Queue in 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

public class PriorityQueue { Node head; class Node { int data; Node next; Node(int d) { data = d; next = null; } } void getUnion(Node hd1, Node hd2) { Node t1 = hd1, t2 = hd2; while (t1 != null) { insert(t1.data); t1 = t1.next; } while (t2 != null) { if (!isPresent(head, t2.data)) insert(t2.data); t2 = t2.next; } } void printList() { Node temp = head; while (temp != null) { System.out.print(temp.data + " "); temp = temp.next; } System.out.println(); } void insert(int new_data) { Node new_node = new Node(new_data); new_node.next = head; head = new_node; } boolean isPresent(Node head, int data) { Node t = head; while (t != null) { if (t.data == data) return true; t = t.next; } return false; } public static void main(String[] args) { PriorityQueue list1 = new PriorityQueue(); PriorityQueue list2 = new PriorityQueue(); PriorityQueue union = new PriorityQueue(); list1.insert(20); list1.insert(4); list1.insert(15); list1.insert(10); list2.insert(10); list2.insert(2); list2.insert(4); list2.insert(8); union.getUnion(list1.head, list2.head); System.out.println("First List is"); list1.printList(); System.out.println("Second List is"); list2.printList(); System.out.println("Union List is"); union.printList(); } }

Output:

First List is

10 15 4 20

Second List is

8 4 2 10

Union List is

2 8 20 4 15 10

EXPLANATION

Line 1 declares the class with the embedded class as well “Node”. The priority queue class has instance variables head of type Node. The Node class has instance variables, data of type int, and Node next. Followed by the constructor in lines 7 to 10. 

A void method was created “getUnion” which takes two parameters of type Nodes,hd1 and hd2, and are both assigned to Node t1 and t2 respectively. So while t1 is not null, insert is called to insert its data, and t1 is referred to its next. Same thing with t2 in line 21 but before it goes to insert its value, it ensures that the head and data of t2 is not present.

Insert method was created in line 39 which takes in a parameter of type int and Node is being instantiated in line 41. line 42 assigns head to the next of the node that was instantiated and that head points to new_node in line 43.

Method isPresent was created in line 45 with parameter head of type Node and data of type int. Node t variable holds the head. And while t is not null,

And if data in "t" is the same as the parameter data, then it should return true but if not, it proceeds to run the remaining lines of code as it assigns t.next to t and returns false in line 54.

The main method in line 56 and three instances were created from the class PriorityQueue, list1, list2, and union respectively from lines 58 to 60. And line 61 to line 68 inserts values. And the method "getUnion" was called to get the union between the two lists. List1 and 2 were printed separately and after that only the union values were printed.