4

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

希望得到与有关优先级队列的问题类似的答案：Priority Queue applications

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

还有一个Exception类的例子InnerExeption

那里还有什么？

4

3 回答 3

4

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

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

  • 一种应用是在初始化期间将所有对象预分配到池中（即链表）；所以每当我们需要一个新对象时，我们可以删除列表的头部。
  • 另一个应用程序正在订单处理中；每个 Order 对象都实现了一个链表入口接口（具有前一个和下一个引用），因此当我们收到客户的订单时，我们可以从池中移除一个 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 并将接口方法委托给 MultiListEntry 对象的内部引用。

于 2013-09-14T14:08:48.173 回答
0

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

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

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

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

于 2013-09-14T13:30:40.943 回答
0

java中的hashmaps使用链接列表表示。当多个键在同一个地方散列时会导致冲突，此时键像链接列表一样被链接。

于 2017-08-21T10:44:18.793 回答