data-structures - 链表的应用

Question

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

希望得到类似于这个关于优先级队列的问题的答案:Priority Queue applications

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

还有Exception的例子具有 InnerExeption 的类

那里还有什么？

Answer 1

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

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

一种应用是在初始化期间将所有对象预分配到池中(即链表)；所以每当我们需要一个新对象时，我们可以删除列表的头部。

另一个应用程序正在订单处理中；每个 Order 对象都实现了一个链表入口接口(interface)(具有前一个和下一个引用)，因此当我们收到客户的订单时，我们可以从池中移除一个 Order 对象并将其放入“待处理”列表中。由于每个 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 并将接口(interface)方法委托(delegate)给 MultiListEntry 对象的内部引用。