java - 使用链表实现优先级队列

Question

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

节点类代码

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

}

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

Answer 1

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

因为你的列表是单链接的(只指向节点中的下一个元素)你需要做的就是:

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

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

3. 然后返回临时变量。