How to implement priority queue with unordered linkedlist

Question

I have the idea to implement priority queue with unordered linkedlist.

    public class UnorderedLinkedListMaxPQ<Key extends Comparable<Key>> {
    private Node first;
    private int n;                                        //number of elements
    private class Node{
        Key key;                                          //elements
       Node next;   
    }

    public boolean isEmpty()               {return first==null;}
    public int size()                      {return n;}
    public void insert(Key key){
        Node oldfirst=first;
        first=new Node();
        first.key=key;
        first.next=oldfirst;
        n++;
    }

    public Key delMax(){
        Node node=first;
        if(node==null) {return null;}
        Key max=node.key;
        while(node.next!=null){
            Key data=node.next.key;
            if(data.compareTo(max)>0){
                max=data;
            }
            node=node.next;
        }
         first=first.next;
          n--;
        return max;
    }

    //Test Routine
    public static void main(String[] args) {
        UnorderedLInkedListMaxPQ<String> pq=new UnorderedLInkedListMaxPQ<String>();
        pq.insert("this");
        pq.insert("is");
        pq.insert("a");
        pq.insert("test");

        for(int j=0;j<pq.n;j++){
            StdOut.print(pq.delMax());
            StdOut.println();

        }
    }
}

I search the max element in the linkedlist,then return the maxest element. But when I test,the output is this this which I suppose is this test is a.

There is something wrong with my implements?Any suggestions?

Answer 1

Performance wise,this is not the best approach to implement a priority queue. I would recommend to keep an ordered list while inserting. By doing that way,you just have to delete the first to retrieve the max and not scan through the entire linked list.

But in case you want to stick with the current approach, modify the delMax() as follows:

public Key delMax(){

    if(first==null) 
        return null;
    else if(n==1)
        return first.key;
    Node max=first,maxPrev=null,curr = max.next,prev = first;
    while(curr!=null){
        Key currMax = max.key;
        Key nextKey = curr.key;
        if(nextKey.compareTo(currMax)>0){
            max = curr;
            maxPrev = prev;
        }
        prev = curr;
        curr = curr.next;
    }
    if(maxPrev!=null)
        maxPrev.next=max.next;
    else
        first = max.next;
    n--;
    return max.key;
}

Also modify the following:

int k = pq.n;
for(int j=0;j<k;j++){
    StdOut.print(pq.delMax());
    StdOut.println();
}

This should return your desired output of this test is a