單鏈表和雙鏈表之間是否存在性能差異？

我們的作業任務要求我們證明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

單鏈表和雙鏈表之間是否存在性能差異？

回答

相關問題