单链表和双链表之间是否存在性能差异？

我们的作业任务要求我们证明Java LinkedList实现是双向链接的，而不是单链接的。然而，列表操作（例如添加元素，删除元素和查看元素）在两种实现中似乎都具有相同的复杂性，所以似乎没有办法使用性能参数来演示Java的双向链接特性LinkedList。任何人都知道更好的方式来说明两者之间的区别？单链表和双链表之间是否存在性能差异？

来源

2011-02-24 Anshu Chimala

最终证明是阅读源代码。但我怀疑这就是这项任务所要求的:-) – 2011-02-24 01:11:44

@Stephen +1 - 有时候强力方法是最好的！在uni，我帮助我的室友用他的加密作业。问题是这是一个3字的Ceaser密码。我说：“'那里'这个词有什么可能呢？而且只有17k的可能性......”他的教授没有留下深刻的印象，但是自从他证明他是如何做到的，他不得不信任他。他的代码也比大多数短得多！ – corsiKa 2011-02-24 01:15:31

看看向前或向后的迭代，删除“before-last”元素，等等。

来源

2011-02-24 01:08:38

我们结束了查找前一个元素。这很好。谢谢！ – 2011-02-24 01:33:15

考虑以下节点，单和双。

class SingleLinkedNode E data; SingleLinkedNode next; }

class DoubleLinkedNode E data; DoubleLinkedNode prev; DoubleLinkedNode next; }

如果我们想从DoubleLinkedList中移除（假设我们已经找到了这个非常不同的节点），我们需要做什么？

使节点在删除之前指向一个点。
将节点删除后的一点指向之前的节点。

如果我们想从SingleLinkedList中删除（假设我们已经找到了这个非常不同的节点），我们需要做什么？

使删除的点之前的节点成为之后的点。

你会认为这意味着它在单个链接列表中的速度比双倍更快。

但是，如果我们没有引用前面的节点，我们该如何删除节点？我们只有对下一个的参考。我们不必为了找到prev而在列表上进行其他搜索吗？：-O

来源

2011-02-24 01:13:13 corsiKa

*“我们不需要在列表上完成其他搜索，只是为了找到prev吗？”*。其实没有。单一链接列表的体面实现不会那样做。 – 2011-02-24 01:32:25

@Stephen节点单链表如何在节点之前引用节点？ – corsiKa 2011-02-24 01:38:41

当您遍历列表以查找节点时，还保留对前一个节点的引用;即你刚刚打过的那个。所以你有这样的东西：Node tmp = head，prev; while（node.data！= findItem）{prev = tmp; tmp = tmp.next; }现在在循环之后（如果列表中的项）tmp是要删除的节点并且prev是节点之前，因此prev.next = tmp.next;它消失了！ ;-) – 2011-02-24 02:02:29

这是一个非常简单的证明 - 你看看源代码，并看到每个节点都有一个.previous指针:) http://www.docjar.com/html/api/java/util/LinkedList.java.html

来源

2011-02-24 01:13:28

Java的List接口没有一个方法，它允许你删除项目而不搜索链接列表。它有remove（int index），它必须扫描列表以查找索引条目，并且它还具有remove（Object o），它也必须扫描列表。由于链表实现可以在扫描时保存必要的上一条目条目上下文，因此remove对于单链和双链链表具有相当的复杂性。这个状态也可以保存在一个迭代器中，所以Iterator.remove（）不会改变它。所以我不认为你可以从删除性能中看出来。

我的猜测是，对此的“正确”答案是在搜索第一个或最后一个对象时创建多个不同大小和时间的列表，并查找.indexOf（）和.lastIndexOf（）的性能。假定实现是双向链接的，并从列表开始处搜索.indexOf（）并从结尾搜索。lastIndexOf（），性能将取决于长度或长度无关。

来源

2011-02-24 05:21:46

单链表和双链表之间是否存在性能差异？

回答

相关问题