链表的应用

Question

有哪些

应用链表的好例子？我知道将队列和堆栈实现为链表是个好主意，但是是否有一个实用而直接的例子来说明链表解决专门利用快速插入时间的问题？不仅仅是基于链表的其他数据结构。

希望得到与有关优先级队列的类似问题的答案：优先级队列应用程序

我自己找到了一个：使用哈希表和链表实现的 LRU（最近最少使用的）缓存。

还有一个例子是Exception类有一个InnerExeption

还有什么？

Answer 1

我在美国的一个"大型股票市场"担任开发人员。使我们以非常快的速度运行的部分原因是，我们在初始化后（在市场上一天开始之前）不进行任何堆分配/取消分配。这种技术并非交易所所独有，在大多数实时系统中也很常见。

首先，对我们来说，链表比基于数组的列表更受欢迎，因为它们在列表增长或收缩时不需要堆分配。我们在交易所的多个应用程序中使用链表。

• 一个应用程序是在初始化期间将所有对象预先分配到池（链表）中;因此，每当我们需要一个新对象时，我们都可以删除列表的头部。
• 另一个应用程序是订单处理;每个订单对象都实现了一个链表条目接口（具有上一个和下一个引用），因此当我们收到来自客户的订单时，我们可以从池中删除一个订单对象并将其放入"处理"列表中。由于每个 Order 对象都实现了链表条目，因此在列表中的任意点添加就像填充上一个和下一个引用一样简单。

我头顶上的例子：

Interface IMultiListEntry {
    public IMultiListEntry getPrev(MultiList list);
    public void setPrev(MultiList list, IMultiListEntry entry);
    public IMultiListEntry getNext(MultiList list);
    public void setNext(MultiList list, IMultiListEntry entry);
}
Class MultiListEntry implements IMultiListEntry {
    private MultiListEntry[] prev = new MultiListEntry[MultiList.MAX_LISTS];
    private MultiListEntry[] next = new MultiListEntry[MultiList.MAX_LISTS];
    public MultiListEntry getPrev(MultiList list) {
        return prev[list.number];
    }
    public void setPrev(MultiList list, IMultiListEntry entry) {
        prev[list.number] = entry;
    }
    public IMultiListEntry getNext(MultiList list) {
        return next[list.number];
    }
    public void setNext(MultiList list, IMultiListEntry entry) {
        next[list.number] = entry;
    }
}
Class MultiList {
    private static int MAX_LISTS = 3;
    private static int LISTS = 0;
    public final int number = LISTS++;
    private IMultiListEntry head = null;
    private IMultiListEntry tail = null;
    public IMultiListEntry getHead() {
        return head;
    }
    public void add(IMultiListEntry entry) {
        if (head==null) {
            head = entry;
        } else {
            entry.setPrevious(this, tail);
            tail.setNext(this, entry);
        }
        tail = entry;
    }
    public IMultiListEntry getPrev(IMultiListEntry entry) {
        return entry.getPrev(this);
    }
    public IMultiListEntry getNext(IMultiListEntry entry) {
        return entry.getNext(this);
    }
}

现在您所要做的就是扩展 MultiListEntry 或实现 IMultiListEntry，并将接口方法委托给对 MultiListEntry 对象的内部引用。

Answer 2

答案可能是无限多的，"好例子"是一个主观术语，所以你的问题的答案是非常值得商榷的。当然有例子。您只需要考虑快速插入的可能需求。

例如，您有一个任务列表，您必须解决所有任务。当您浏览列表时，当任务解决时，您意识到必须紧急解决新任务，因此您将任务插入刚刚解决的任务之后。它不是队列，因为将来可能需要该列表进行审核，因此您需要保持列表完整，在这种情况下不允许使用pop方法。

再举一个例子：你有一组按字母顺序排序的名称。假设您可以以某种方式快速确定下一个指向存储特定名称的对象的对象。如果要快速删除名称，只需转到要删除的对象的上一项即可。删除速度也比堆栈或队列更快。

最后，想象一组非常大的项目，即使在插入或删除后也需要存储。在这种情况下，只搜索要删除的项目或项目在应插入项目的位置之前，然后执行操作比复制整个大集合要快得多。

Answer 3

Java中的哈希映射使用链接列表表示。当多个键在同一位置哈希时，它会导致冲突，此时键像链接列表一样链接。