巨人的遍歷LinkedList的

對於我需要寫一個方法，一個項目，時間充滿了用500萬個隨機整數一個的ListIterator，然後用鏈表的get（index）方法在LinkedList的穿越。巨人的遍歷LinkedList的

我沒有問題與listIterator遍歷它，並在75毫秒左右完成。但是，在嘗試500萬整數的get方法遍歷之後，我在1.5小時左右停止了運行。

我使用的getTraverse方法是類似下面的示例代碼（但是礦用類中的其他方法進行分組，並不含一成不變的，而是以同樣的方式）。

public static long getTraverse(LinkedList<Integer> list) { 
    long start = System.currentTimeMillis(); 
    for (int i = 0; i < linkedList.size(); i++) { 
     linkedList.get(i); 
    } 
    long stop = System.currentTimeMillis(); 
    return stop - start; 
}

這工作完全正常的尺寸50，500，5000，50000的整數LinkedLists，並花了相當長一段時間，但完成500000

我的教授往往是有說明書，非常非常曖昧遇到問題時無助。所以，我不知道我的代碼是否被破壞，或者他是否被指針中的Integers所帶走。任何輸入讚賞。

來源

2017-02-17 Cole Dooley

在我的數據結構類中，我們不得不等待24小時以上才能完成對大小數組的排序。（這也是O（n^2）算法），所以聽起來很正常。 – 4castle

你的導師試圖教你的一個教訓是，LinkedList對於大量數值非常緩慢。沒有隨機訪問方法。爲了得到（n）它必須從第一個元素開始並迭代到n。 –

好吧，只要確保那麼！我認爲這需要很長時間，但我認爲我必須做些什麼錯等待幾個小時。我上一個項目花了30分鐘跑完。這就說得通了！ –

想一想LinkedList是如何實現的 - 作爲一個節點鏈 - 並且您將看到，要訪問特定節點，您必須從頭開始並遍歷該節點。

你在一個LinkedListň次調用.get()，直到它到達該索引這就需要遍歷列表。這意味着你的方法需要O（n^2）（或二次）時間，因爲每個元素都必須遍歷列表的一部分。正如Elliott Frisch所說，我懷疑你正在發現你的教師想要你發現的東西 - 即使原則上他們做了同樣的事情，不同的算法可能會有極大不同的運行時間。

來源

2017-02-17 01:26:08 dimo414

啊，是的，我絕對發現了！我想我是不耐煩的，因爲執行時間似乎過度。在學習Big-O之後，我想我可以預測可怕的長運行時間。現在就讓它運行。 –

@ColeDooley這是一個需要思考的後續問題。 LinkedList包含獲取（n）的優化，即如果n更接近列表的末尾，則遍歷從結尾開始並向後繼續。這是一個很棒的優化，因爲平均而言，它將搜索時間縮短了一半！解釋這對Big-O分析有什麼影響。 –

甲LinkedList被用於插入，這是一個固定的時間操作優化。

搜索一個LinkedList需要你的每一個元素遍歷找到你想要的。您提供了get方法的索引，但在它的覆蓋範圍內，它將該列表遍歷到該索引。

如果你添加一些打印語句，你可能會看到第一個X元素檢索非常快，並隨着時間的推移，你的索引元素進一步下跌的列表減慢。

的ArrayList（由數組支持）被用於檢索優化，可以索引在恆定的時間所需的元件。嘗試更改您的代碼以使用ArrayList並查看運行多快的get。

來源

2017-02-17 01:23:00 Matt

太棒了！我會嘗試在ArrayList上實現它。我認爲get遍歷會很慢，但並沒有預料到究竟有多慢。我甚至添加了一個提示，以完全跳過get遍歷，同時測試它的挫敗感哈哈。 –

巨人的遍歷LinkedList的

回答

相關問題