將現有元素添加到LinkedList之後的性能

假設我們有一個包含幾百個元素的java.util.LinkedList。一種可能性插入現有的元件之後的新的元素Eķ將是：將現有元素添加到LinkedList之後的性能

list.add(list.indexOf(K) + 1, E);

據我明白這種方法具有O（K 2 ）行爲，其中k表示元件K的位置第一個indexOf（）遍歷列表，直到它找到K，然後add必須再次執行相同的工作，直到它到達位置k + 1。但是必須修改的條目可以在第一步之後輕鬆確定。我認爲用O（k）行爲創建一個方法addAfter（K，E）並不是那麼多工作。

除了切換到java.util.ArrayList之外，有沒有一種方法可以改善像這樣的場景中的性能？

預先感謝您。

來源

2011-04-02 aka

你的錯誤與你的假設，它是O（K^2），它只是O（2K）這是O（K）（Btw這裏一定不是K =元素索引，但列表大小，但這並不重要的問題）。但是你說得對，它需要兩倍的時間，而且是不合適的。我能想到的唯一方法是使用ListIterator並找到/插入自己（這是爲了完成這種操作）。

來源

2011-04-02 12:18:58 flolo

據我所知，這個方法有一個O（k2）的行爲，其中k表示元素K的位置。首先indexOf（）遍歷列表直到它找到K，然後add必須做同樣的工作再次，直到它到達位置k + 1

實際上，的list.add(list.indexOf(K) + 1, E)成本O(k)如果list是LinkedList。

的list.indexOf(K)呼叫涉及k鏈接遍歷和k比較。
list.add(k + 1, E)調用涉及k + 1鏈接遍歷。

將它們加起來 - 3 k + 1操作;即O(k)。

然而，你是對的。可以使用addAfter或addBefore方法創建替代版本的LinkedList。這些方法也將是O(k)，但它們應該更快。不幸的是，LinkedList沒有以允許您簡單添加這些方法（並且以最佳方式實現它們）的方式實現。 LinkedList的內部被聲明爲私有，所以你需要重新開始。

而上ArrayList捎帶list.add(list.indexOf(K) + 1, E)將O(N)其中N是列表的長度。 indexOf步驟需要k比較，並且add步驟涉及移動N - k元素。 Ergo N操作和O(N)

來源

2011-04-02 12:18:16

當然，你說得對。我的錯。仍然可以減少鏈接遍歷的數量嗎？ – aka 2011-04-02 12:21:35

這個代碼示例是使ķ操作：

LinkedList<Integer> list = new LinkedList<Integer>(); 
    for(int i=0;i<100;i++){ 
     list.add(i); 
    } 

    Integer insert = 1001; 
    Integer before = 50; 
    for (ListIterator<Integer> iterator = list.listIterator(); iterator.hasNext();) { 
     Integer next = iterator.next(); 
     if(next.equals(before)){ 
      iterator.add(insert); 
      break; 
     } 
    }

來源

2011-04-02 12:48:48 ilalex

將現有元素添加到LinkedList之後的性能

回答

相關問題