我正在用Java实现一个自定义的泛型单向链表，用来按特定优先级对元素进行排序（一个自定义的优先级任务队列）。虽然实现对小数据集工作正常，但处理较大数据集时性能会急剧下降，因为每次插入都需要线性扫描以找到正确的位置。我尝试添加一个 tail 指针，但它只优化了最后端的插入，对中间的优先级元素并没有明显提升。

示例：

public class PriorityQueueList<T extends Comparable<T>> {
    private Node<T> head;

    private static class Node<T> {
        T data;
        Node<T> next;
        Node(T data) { this.data = data; }
    }

    // Linear insertion sorting elements on the fly
    public void insertWithPriority(T data) {
        Node<T> newNode = new Node<>(data);
        if (head == null || data.compareTo(head.data) < 0) {
            newNode.next = head;
            head = newNode;
            return;
        }

        Node<T> current = head;
        while (current.next != null && current.next.data.compareTo(data) < 0) {
            current = current.next;
        }
        newNode.next = current.next;
        current.next = newNode;
    }
}

观察到的行为： 在对自定义列表进行基准测试、注入元素时，执行时间呈现二次方增长 ($O(N^2)$)。随着数据集规模增大，执行时间的实际文本输出如下：

Successfully inserted 10,000 elements. Time taken: 45 ms

Successfully inserted 30,000 elements. Time taken: 382 ms

Successfully inserted 50,000 elements. Time taken: 1,120 ms

Successfully inserted 80,000 elements. Time taken: 2,945 ms

Successfully inserted 100,000 elements. Time taken: 4,712 ms

Benchmark finished. Total time for 100k elements: 4.71 seconds.```

解决方案

你的 insertWithPriority 与列表大小成线性关系，因为你需要遍历列表。因此，插入 N 个元素的时间复杂度可预期为二次方级别，这正是你所测量到的。

要优化这段代码，必须把 insertWithPriority 的复杂度降下来。遍历整条列表并非可选项。那么应该怎么做呢？

你想通过把新元素插入到正确的位置来维持一个有序列表。如果使用链表，插入本身是 O(1)，但你只能通过 O(N) 迭代来找到正确的位置（迭代1）。如果使用基于数组的列表，你可以 O(logN) 通过二分查找找到插入元素的正确下标，但实际的插入是 O(N)，因此也行不通。这些简单的数据结构都无法提供一个次线性时间的 insert 操作。

有多种基于树的数据结构可以在保持有序的同时实现 O(logN) 插入。一个简单的二叉树浮现脑海，尽管在实践和理论上都不是一个好的数据结构。B-树、红黑树和跳表是对二叉树思想的一些改进。若你想维持有序列表，必须使用其中之一。使用其中之一，你将在基准测试中获得 O(NlogN) 的运行时间。

但实现一个 优先队列 的真正诀窍在于理解你并不需要始终维护一个完全排序的列表。队列除了 insert 之外，只需要支持以下操作即可：

head - 获取第一个元素
pop - 移除第一个元素

这三种操作在被称为 "Heap"（堆）或 "Priority Queue"（优先队列）的数据结构上都是次线性的。head 是 O(1)，pop 和 insert 是 O(logN)。因此在你的基准测试中你将观察到 O(NlogN)。关于这个数据结构在其他地方已有深入讲解，这里只给出要点：所谓“堆”是一棵树，满足父节点的值始终小于子节点的值。若遵循这一点，你就能得到这三种操作的简洁实现。此外，还有一个把整棵树实现在数组上的巧妙技巧。这个技巧不会带来理论上的大O增益，但会带来实践上的收益。还有一些堆的高级版本，可以把 insert 向下推动到 O(1)，参见https://en.wikipedia.org/w/index.php?title=Priority_queue&section=8#Summary_of_running_times。

1链表在垃圾回收和CPU缓存方面也非常不友好。这也是它们在实际开发中总是比较慢的原因，人们常常一概不推荐使用它们，但这与算法复杂度的讨论无关。