Java 使用链表实现优先队列

Use a linked list to implement a Priority Queue

提问by user1010101

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.

我已经使用链表实现了一个优先级队列。在这个优先级队列中，最小的 int 值具有最高的值，因此通过调用 remove 方法将删除最小的方法。

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.

目前它工作正常，但是我不确定链接列表类中的 remove 方法是否是删除元素的最佳方法。所以我正在寻找建议。

采纳答案by Xabster

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

remove()应该从列表中删除第一个元素，对吗？你为什么要为此循环任何东西？

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

由于您的列表是单链接的（仅指向节点中的下一个元素），您需要做的就是：

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

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

3. Then return the temporary variable.

1. 将 存储first在一个临时变量中（如果它是 != null）

2. 然后更新first为指向列表中的第二项（first.next如果 != null）

3. 然后返回临时变量。

回答by vijaysdey88

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 + "]";
       }
    }
}