由于 LinkedList 在内存开销方面是一场噩梦，而且在迭代元素时速度也较慢，所以我想要类似 int poiter 数据结构。
所以我有一个整数列表，我通过在开头-中间插入元素来构成它。列表准备就绪后，我从左侧开始逐个迭代。这是我的问题约束。
最佳答案
我会剖析并尝试不同的数据结构。
话虽这么说，为什么不尝试使用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!
关于Java:替代 LinkedList 或 int 指针数据结构，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/12004360/