Question

Write in Java (Not Javascript)

Provide an implementation of priority queue using double-ended doubly linked lists. Recall that double-ended means keeping first and last references and doubly linked feature allows us to go backwards, using a prev reference at each Link. Also, note that the greater the number, the lower the priority. For instance, 2 is of higher priority compared to 5.

Specifically, write a class LinkedListPriorityQ which implements the priority queue methods:

• boolean isEmpty()
• void enqueue(int item)
• int dequeue()
• int peek()

You need an implementation for the underlying linked list class. For this part, you can use any relevant code from lecture slides.

Your file to be submitted to Gradescope should be named LinkedListPriorityQ.java. and here is the skeleton:

class Link

{

    public int data; // assuming integer data

    public Link next; // reference to the next Link

    public Link prev; // reference to the previous Link

    //--------------------------------------------------------------

    // Constructor

    public Link(int data)

    {

        this.data=data;

        next=null;

        prev=null;

    }

}

class LinkedList

{

   

    /* you should implement this linked list class(can take parts of code from lecture slides) and be careful what type of linked list is suitable to be used for priority Queue */

}

public class LinkedListPriorityQ {

   //implement priority queue using the linked list class

}

Answer 1

public int data;
public Node next;
public Node prev;

public Node(int data) {
this.data = data;
next = null;
prev = null;
}
}

class LinkedList {
public Node head;

public LinkedList(int data) {
Node a = new Node(data);
head = a;
}

public void traversal() {
Node temp = head; //temporary pointer to point to head

while(temp != null) { //iterating over linked list
System.out.print(temp.data+"\t");
temp = temp.next;
}

System.out.println("");
}

//new node before head
public void insertAtFront(Node n) {
n.next = head;
head.prev = n;
head = n;
}

//insert new node at last
public void insertAtTail(Node n) {
Node temp = head;

while(temp.next != null) {
temp = temp.next;
}

temp.next = n;
n.prev = temp;
}

//function to insert a node after a node
public void insertAfter(Node n, Node a) {
n.next = a.next;
a.next.prev = n;
a.next = n;
n.prev = a;
}

//function to delete
public void del(Node a) {
if(a.prev != null) { //node is not head
a.prev.next = a.next;
}
else { //node a is head
head = a.next;
}

if(a.next != null) {
a.next.prev = a.prev;
}
}
}
class LinkedListPriorityQ
{
private Node head;
private Node tail;
static class Node{
//data
int i;
// next node in the list
Node next;
// previous node in the list
Node prev;
Node(int i){
this.i = i;
}
public void displayData(){
System.out.print(i + " ");
}
}
// constructor
public LinkedListDeque(){
this.head = null;
this.tail = null;
}

public boolean isEmpty(){
return head == null;
}
}