1

由于 LinkedList 在内存开销方面是一场噩梦，而且在迭代元素时速度也较慢，所以我希望有类似 int poiter 数据结构的东西。

所以我有一个整数列表，我通过在开头-中间插入元素来形成它。列表准备好后，我从左侧开始逐一迭代。那是我的问题约束。

4

4 回答 4

2

我会分析并尝试不同的数据结构。

话虽如此，为什么不尝试使用ArrayList; 迭代甚至插入速度很快，而在O(n)中，速度很快，因为在缓存中移动连续数据的速度非常快。（如果您在插入时还反转列表，它会更快！）

更新，因为我的程序员同事不明白我为什么推荐ArrayList这个特殊问题：

问题不在于插入元素。在这种情况下，链表直接获胜（O(1) 与数组列表的 O(n) 相对）。问题是要找到插入它们的地方。在这种情况下，LinkedList速度真的很慢。找到插入位置的开销很大，因为它不会在“好事情”中分配内存。很多缓存未命中！

OP 没有发布任何代码，所以我们只知道 OP 想要什么，但这里是对这两种情况的算法分析（其中C * 是常量）：

LinkedList, 对于要插入的每个元素：

  • 迭代O(C1 * n)
  • 插入O(1)

ArrayList, 对于要插入的每个元素：

  • 迭代O(C2 * n)
  • 插入O(C3 * n)

因此，这两种算法都在O(n)中，但仔细观察常量：C1真的很大（如上所述）。另一方面，C2和C3很小，因为在缓存中迭代和移动速度很快。

所以，如果你有足够的内存试试ArrayList！

于 2012-08-17T10:56:04.950 回答
2

LinkedList如果您经常使用，则确实具有糟糕的性能list.get(index);
使用 the ListIteratorinstead 以便每次您不会一遍又一遍地遍历列表。
而且，如果您需要在列表中间添加元素，它将比 an 具有更好的性能ArrayList O(1)（因为您不需要移动元素）

更新：
迭代列表的正确方法是使用迭代器（隐式或显式）。使用隐式迭代器的示例： 

for(E e:list){  
}

永远不要： 

for(int i = 0; list.size(); i++{  
    E e = list.get(i);  
}

如果列表是 a ，则LinkedList此操作与在循环的每次迭代中从头开始遍历列表O(N^2)一样。由于迭代器“记住”最后一个访问的元素并从那里开始，因此 将第一种形式与迭代器一起使用几乎与 an 相同list.get(i)
O(N)ArrayList

于 2012-08-17T10:59:14.200 回答
2

试试Gaplist，它为许多用例提供类似 ArrayList 的性能和内存占用。如果插入主要是顺序的（在任何索引处），则插入接近 O(1)。

于 2012-08-17T11:13:08.060 回答
0

第一步：插入元素LinkedList

第二步：复制元素以ArrayList进行迭代。

顺便说一句，“噩梦”有点夸张LinkedList:)

于 2012-08-17T11:00:57.667 回答