将现有元素添加到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之后的性能

回答

相关问题