使用链表实现优先队列

Question

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

节点类的代码：

```html

节点类代码

```

public class Node {

    public int iData;
    public Node next;

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

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

}

链表代码

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(" ");
    }

}

优先队列的代码

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();
    }

}

目前情况良好，但我不确定链表类中的删除方法是否是最佳方法。因此，我正在寻求建议。

- user1010101

Answer 1

remove()应该是从列表中删除第一个元素，对吧？那你为什么需要循环呢？

由于你的列表是单向链表（只指向节点中的下一项），你只需要做以下三件事：

1.将first存储在一个临时变量中（如果它不等于 null） 2.然后更新first指向列表中的第二个项目(first.next如果不等于null) 3.最后返回临时变量。

- Xabster

---

remove应该删除具有最高优先级的元素，在我的情况下，这恰好是最小的整数值。在我的情况下，最高整数值存储为第一个元素。现在我想起来了...我是否应该将最低整数值存储为优先队列中的第一个元素，这样我就可以获得O(1)的删除操作。 - user1010101

Answer 2

这可以通过将单个指针指向第一个节点，并通过将最小元素存储到第一个节点来维护顺序来实现。

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

- vijaysdey88