Use a linked list to implement a Priority Queue

Question

I have implemented a priority queue using a linked list. In this priority queue the smallest int value has the highest value and therefore by calling the remove method the smallest method will be removed.

Code for Node Class

public class Node {

    public int iData;
    public Node next;

    public Node(int x) {
        iData = x;
    }

    public void displayNode() {
        System.out.println(iData + " ");
    }

}

Code for Link List

public class LinkList {

    private Node first;

    public LinkList() {
        first = null;
    }

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

    public void insert(int x) {
        Node newNode = new Node(x);
        Node previous = null;
        Node current = first;

        while (current != null && x < current.iData) {
            previous = current;
            current = current.next;
        }

        if (previous == null) {
            newNode.next = first;
            first = newNode;
        }

        else {
            previous.next = newNode;
            newNode.next = current;
        }
    }

    public Node remove() {
        Node previous = null;
        Node current = first;
        Node temp = current;

        while (current.next != null) {
            previous = current;
            current = current.next;
        }

        previous.next = null;

        return temp;
    }

    public void display() {
        Node current = first;

        while (current != null) {
            current.displayNode();
            current = current.next;
        }

        System.out.println(" ");
    }

}

Code for Priority Queue

public class PriorityQ {

    private LinkList list;

    public PriorityQ() {
        list = new LinkList();
    }

    public void insert(int x) {
        list.insert(x);
    }

    public void remove() {
        list.remove();

    }

    public void displayList() {
        System.out.println("Largest Value to Smallest");
        list.display();
    }

}

It is working fine at the moment, however i am not sure if my remove method in the link list class is the best way to go about removing elements. So i am looking for suggestions.

Answer 1

This can be implemented by having single pointer to first node and maintaining order by storing the smallest element to the first node.

public class LinkedListBasedOrderedMinPQ<T extends Comparable<T>> implements PriorityQueue<T> {
    private Node<T> head;
    private int size;

    //Maintains an ordered linked list with the min element as the head 
    @Override
    public void insert(T item) {
       Node<T> node = head;
       head = insert(node, item);
    }

    private Node<T> insert(Node<T> node, T item) {
       Node<T> newNode =  createNewNode(item);
       if(null == node) {
        return newNode;
       }

       if(node.data.compareTo(item) > 0) {
          newNode.next = node;
          node = newNode;
       } else {
          node.next = insert(node.next, item);
       }
       return node;
    }

    private Node<T> createNewNode(T item) {
       size++;
       return new Node<T>(item);
    }

    @Override
    public T remove() {
       if(null == head) {
           return null;
       }
       T data = head.data;
       head = head.next;
       size--;
       return data;
    }

    @Override
    public int size() {
       return size;
    }

    private static class Node<T> {
       private final T data;
       private Node<T> next;

       public Node(T data) {
          this.data = data;
       }

       @Override
       public String toString() {
           return "Node [data=" + data + ", next=" + next + "]";
       }
    }
}

Answer 2

remove() is supposed to remove the first element from the list, right? Why do you loop anything for that?

Since your list is singly-linked (only pointing to next elements in the Node) all you need to do is:

1. Store the first in a temporary variable (if it's != null)

2. Then update first to be pointing to the 2nd item in the list (first.next if != null)

3. Then return the temporary variable.