Use linked list to implement priority queue
I have implemented a priority queue using a linked list. In this priority queue, the smallest int has the highest, and therefore, calling remove will remove the smallest method.
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 + " ");
}
}
Link List Code
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(" ");
}
}
Priority queue code
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 works fine for now, but I'm not sure if my remove method on the link list class is the best way to remove items. So I'm looking for suggestions.
source to share
remove()
should remove the first item from the list, right? Why are you doing something for this?
Since your list is singly linked (only pointing to the following elements in Node), all you have to do is:
-
Store
first
in a temporary variable (if it's! = Null) -
Then update
first
to point to the second item in the list (first.next
if! = Null) -
Then return the temporary variable.
source to share
This can be implemented with a single pointer to the first node and maintaining order while keeping the smallest element at 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 + "]";
}
}
}
source to share