Question

Implement a priority queue using a DoublyLinkedList where the node with the highest priority (key) is the right-most node.
The remove (de-queue) operation returns the node with the highest priority (key).
If displayForward() displays List (first-->last) : 10 30 40 55
remove() would return the node with key 55.
Demonstrate by inserting keys at random, displayForward(), call remove then displayForward() again.

You will then attach a modified DoublyLinkedList.java (to contain the new priorityInsert(long key) and priorityRemove() methods).

Use the provided PQDoublyLinkedTest.java to test your code.

I cant get PQDoublyLinkedTest to work with my code. I already got the rest of code working. Please comment if you want me to add the rest of the code.

PLEASE DO NOT MODIFY PQDoublyLinkedTest!!! its just for testing the code.

public class PQDoublyLinkedTest
{
public static void main(String[] args)
{ // make a new list
DoublyLinkedList theList = new DoublyLinkedList();

theList.priorityInsert(22); // insert at front
theList.priorityInsert(44);
theList.priorityInsert(66);

theList.priorityInsert(11); // insert at rear
theList.priorityInsert(33);
theList.priorityInsert(55);
  
theList.priorityInsert(10);
theList.priorityInsert(70);
theList.priorityInsert(30);

theList.displayForward(); // display list forward
Link2 removed = theList.priorityRemove();
System.out.print("priorityRemove() returned node with key: ");
removed.displayLink2();
  
} // end main()
} // end class PQDoublyLinkedTest

public class DoublyLinkedList
{
private Link first; // ref to first item
private Link last; // ref to last item
public DoublyLinkedList() // constructor
{
first = null; // no items on list yet
last = null;
}

public boolean isEmpty() // true if no links
{
return first == null;
}

public void insertFirst(long dd) // insert at front of list
{
Link newLink = new Link(dd); // make new link
if (isEmpty()) // if empty list,
last = newLink; // newLink <-- last
else
first.previous = newLink; // newLink <-- old first
newLink.next = first; // newLink --> old first
first = newLink; // first --> newLink
}

public void insertLast(long dd) // insert at end of list
{
Link newLink = new Link(dd); // make new link
if (isEmpty()) // if empty list,
first = newLink; // first --> newLink
else {
last.next = newLink; // old last --> newLink
newLink.previous = last; // old last <-- newLink
}
last = newLink; // newLink <-- last
}

public Link deleteFirst() // delete first link
{ // (assumes non-empty list)
Link temp = first;
if (first.next == null) // if only one item
last = null; // null <-- last
else
first.next.previous = null; // null <-- old next
first = first.next; // first --> old next
return temp;
}

public Link deleteLast() // delete last link
{ // (assumes non-empty list)
Link temp = last;
if (first.next == null) // if only one item
first = null; // first --> null
else
last.previous.next = null; // old previous --> null
last = last.previous; // old previous <-- last
return temp;
}
// insert dd just after key

public boolean insertAfter(long key, long dd)
{ // (assumes non-empty list)
Link current = first; // start at beginning
while (current.dData != key) // until match is found,
{
current = current.next; // move to next link
if (current == null)

return false; // didn't find it
}
Link newLink = new Link(dd); // make new link

if (current == last) // if last link,
{
newLink.next = null; // newLink --> null
last = newLink; // newLink <-- last
} else // not last link,

{
newLink.next = current.next; // newLink --> old next
// newLink <-- old next
current.next.previous = newLink;
}
newLink.previous = current; // old current <-- newLink
current.next = newLink; // old current --> newLink
return true; // found it, did insertion

}

public Link deleteKey(long key) // delete item w/ given key
{ // (assumes non-empty list)
Link current = first; // start at beginning
while (current.dData != key) // until match is found,
{
current = current.next; // move to next link
if (current == null)
return null; // didn't find it
}

if (current == first) // found it; first item?
first = current.next; // first --> old next
else
// not first
// old previous --> old next
current.previous.next = current.next;

if (current == last) // last item?
last = current.previous; // old previous <-- last
else
// not last
// old previous <-- old next
current.next.previous = current.previous;
return current; // return value
}

public void displayForward()
{
System.out.print("List (first-->last): ");
Link current = first; // start at beginning
while (current != null) // until end of list,
{
current.displayLink(); // display data
current = current.next; // move to next link
}
System.out.println("");
}

public void displayBackward()
{
System.out.print("List (last-->first): ");
Link current = last; // start at end
while (current != null) // until start of list,
{
current.displayLink(); // display data
current = current.previous; // move to previous link
}
System.out.println("");
}

public void insertSorted(long key)
{
// if list is empty or key is less than current first, inserting at
// first
if (isEmpty() || key < first.dData) {
insertFirst(key);
return; // exiting method
}
// taking a reference to first
Link current = first;
// looping as long as current.next is not null
while (current.next != null) {
// checking if key can be added between current and current.next
if (key >= current.dData && key <= current.next.dData) {
// adding between current and current.next and updating all
// links
Link lnk = new Link(key);
lnk.next = current.next;
current.next.previous = lnk;
current.next = lnk;
lnk.previous = current;
return; //exiting
}
//otherwise, advancing to next link
current = current.next;
}
//if the element is still not inserted, adding to the end
insertLast(key);
}
} // end class DoublyLinkedList

class Link
{
public long dData; // data item
public Link next; // next link in list
public Link previous; // previous link in list
public Link(long d) // constructor
{
dData = d;
}

public void displayLink() // display this link
{
System.out.print(dData + " ");
}
} // end class Link

Answer 1

public class test{
        public static void main(String[] args)
        { // make a new list
                DoublyLinkedList theList = new DoublyLinkedList();

                theList.priorityInsert(22); // insert at front
                theList.priorityInsert(44);
                theList.priorityInsert(66);

                theList.priorityInsert(11); // insert at rear
                theList.priorityInsert(33);
                theList.priorityInsert(55);
                
                theList.priorityInsert(10);
                theList.priorityInsert(70);
                theList.priorityInsert(30);

                theList.displayForward(); // display list forward
                Link removed = theList.priorityRemove();
                System.out.print("priorityRemove() returned node with key: ");
                removed.displayLink();
                
        } // end main()
} // end class test

class DoublyLinkedList {
        private Link first; // ref to first item
        private Link last; // ref to last item
        public DoublyLinkedList() // constructor
        {
                first = null; // no items on list yet
                last = null;
        }

        public boolean isEmpty() // true if no links
        {
                return first == null;
        }

        public void insertFirst(long dd) // insert at front of list
        {
                Link newLink = new Link(dd); // make new link
                if (isEmpty()) // if empty list,
                        last = newLink; // newLink <-- last
                else
                        first.previous = newLink; // newLink <-- old first
                        newLink.next = first; // newLink --> old first
                        first = newLink; // first --> newLink
        }

        public void insertLast(long dd) // insert at end of list
        {
                Link newLink = new Link(dd); // make new link
                if (isEmpty()) // if empty list,
                        first = newLink; // first --> newLink
                else {
                        last.next = newLink; // old last --> newLink
                        newLink.previous = last; // old last <-- newLink
                }
                last = newLink; // newLink <-- last
        }

        public Link deleteFirst() // delete first link
        { // (assumes non-empty list)
                Link temp = first;
                if (first.next == null) // if only one item
                        last = null; // null <-- last
                else
                        first.next.previous = null; // null <-- old next
                        first = first.next; // first --> old next
                return temp;
        }

        public Link deleteLast() // delete last link
        { // (assumes non-empty list)
                Link temp = last;
                if (first.next == null) // if only one item
                        first = null; // first --> null
                else
                        last.previous.next = null; // old previous --> null
                last = last.previous; // old previous <-- last
                return temp;
        }
        // insert dd just after key

        public boolean insertAfter(long key, long dd)
        { // (assumes non-empty list)
                Link current = first; // start at beginning
                while (current.dData != key) // until match is found,
                {
                        current = current.next; // move to next link
                        if (current == null)

                                return false; // didn't find it
                }
                Link newLink = new Link(dd); // make new link

                if (current == last) // if last link,
                {
                        newLink.next = null; // newLink --> null
                        last = newLink; // newLink <-- last
                } else // not last link,
                {
                        newLink.next = current.next; // newLink --> old next
                        // newLink <-- old next
                        current.next.previous = newLink;
                }
                newLink.previous = current; // old current <-- newLink
                current.next = newLink; // old current --> newLink
                return true; // found it, did insertion

        }

        public Link deleteKey(long key) // delete item w/ given key
        { // (assumes non-empty list)
                Link current = first; // start at beginning
                while (current.dData != key) // until match is found,
                {
                        current = current.next; // move to next link
                        if (current == null)
                                return null; // didn't find it
                }

                if (current == first) // found it; first item?
                        first = current.next; // first --> old next
                else
                // not first
                // old previous --> old next
                        current.previous.next = current.next;

                if (current == last) // last item?
                        last = current.previous; // old previous <-- last
                else
                // not last
                // old previous <-- old next
                        current.next.previous = current.previous;
                return current; // return value
        }

        public void displayForward()
        {
                System.out.print("List (first-->last): ");
                Link current = first; // start at beginning
                while (current != null) // until end of list,
                {
                        current.displayLink(); // display data
                        current = current.next; // move to next link
                }
                System.out.println("");
        }

        public void displayBackward()
        {
                System.out.print("List (last-->first): ");
                Link current = last; // start at end
                while (current != null) // until start of list,
                {
                        current.displayLink(); // display data
                        current = current.previous; // move to previous link
                }
                System.out.println("");
        }

        public void insertSorted(long key)
        {
                // if list is empty or key is less than current first, inserting at
                // first
                if (isEmpty() || key < first.dData) {
                        insertFirst(key);
                        return; // exiting method
                }
                // taking a reference to first
                Link current = first;
                // looping as long as current.next is not null
                while (current.next != null) {
                // checking if key can be added between current and current.next
                        if (key >= current.dData && key <= current.next.dData) {
                                // adding between current and current.next and updating all
                                // links
                                Link lnk = new Link(key);
                                lnk.next = current.next;
                                current.next.previous = lnk;
                                current.next = lnk;
                                lnk.previous = current;
                                return; //exiting
                        }
                //otherwise, advancing to next link
                        current = current.next;
                }
                //if the element is still not inserted, adding to the end
                insertLast(key);
        }

        void priorityInsert(long key)  
        {  
                // if list is empty or key is less than current first, inserting at
                // first
                if (isEmpty() || key < first.dData) {
                        insertFirst(key);
                        return; // exiting method
                }
                // taking a reference to first
                Link current = first;
                // looping as long as current.next is not null
                while (current.next != null) {
                // checking if key can be added between current and current.next
                        if (key >= current.dData && key <= current.next.dData) {
                                // adding between current and current.next and updating all
                                // links
                                Link lnk = new Link(key);
                                lnk.next = current.next;
                                current.next.previous = lnk;
                                current.next = lnk;
                                lnk.previous = current;
                                return; //exiting
                        }
                //otherwise, advancing to next link
                        current = current.next;
                }
                //if the element is still not inserted, adding to the end
                insertLast(key);
        }  
        public Link priorityRemove() // delete last link
        { // (assumes non-empty list)
                Link temp = last;
                if (first.next == null) // if only one item
                        first = null; // first --> null
                else
                        last.previous.next = null; // old previous --> null
                last = last.previous; // old previous <-- last
                return temp;
        }
} // end class DoublyLinkedList

class Link {
        public long dData; // data item
        public Link next; // next link in list
        public Link previous; // previous link in list
        public Link(long d) // constructor
        {
                dData = d;
        }

        public void displayLink() // display this link
        {
                System.out.print(dData + " ");
        }
} // end class Link