在我的一次面试中，我被问到了这个问题。
是否有一种数据结构具备以下两个功能：
1. 像ArrayList一样具有常数时间访问（随机访问）的能力。
2. 具有可变大小的能力，就像LinkedList一样。
如果没有这样的数据结构，请自己创建一个。
4个回答
6
我认为你想要的答案是“哈希表”（请参阅Wikipedia中的“哈希表”），因为你曾经评论说你正在寻找超出
ArrayList 之外的另一个答案（对于Java，请参阅：哈希表）。
但请注意，它可以是近似常数时间，具体取决于哈希算法和数据集，因为可能会发生冲突，导致（短暂的）二次线性搜索。 Javadoc非常好地解释了Java实现中如何处理这个问题。- Brian Roach
3
@Zack - 当然。我已经进行了编辑，以更清晰地描述通用数据结构，然后给出了Java实现示例。 - Brian Roach
我明白 :-). 当我看到“Hashtable”时，本能地会提到HashMap。 - Zach L
3
除了像Brian Roach所说的HashTable之外，面试官可能还在暗示LinkedHashMap或LinkedHashSet，它们提供了一些基本操作的恒定时间性能，并保持插入顺序，因为它将HashTable与双向链表结合起来。
换句话说，如果您循环遍历键，则将元素放入LinkedHashMap中的顺序将是检索它们的相同顺序。
使用Set的一个缺点是不能有重复项，而Map也不能有重复的键。解决方法是使用List的Set，或者使用类似Google的Multimap的东西。
但正如其他人所说，ArrayList已经满足了这两个要求。它是一个没有可变大小的数组。
此外，LinkedList相比ArrayList的主要优势是在列表的开头和结尾都可以实现常数时间插入/删除，而ArrayList的性能为O(n)。两者都可以提供可变大小。
换句话说，如果您循环遍历键，则将元素放入LinkedHashMap中的顺序将是检索它们的相同顺序。
使用Set的一个缺点是不能有重复项，而Map也不能有重复的键。解决方法是使用List的Set，或者使用类似Google的Multimap的东西。
但正如其他人所说，ArrayList已经满足了这两个要求。它是一个没有可变大小的数组。
此外，LinkedList相比ArrayList的主要优势是在列表的开头和结尾都可以实现常数时间插入/删除，而ArrayList的性能为O(n)。两者都可以提供可变大小。
- Zach L
1
你听说过deque吗？它是一种“双端队列”。在许多实现中，它对于除了头部或尾部之外的任何位置的插入和删除都不会有效地改变大小，但它提供了你所需的两个属性：
- 随着元素的添加，只偶尔进行最小限度的重新分配
- 常数时间访问，因为deque通常存储为数组的数组
你在问题中提到了Java，我必须指出，在Java中，Deque接口并没有提供随机访问。即使ArrayDeque具体类也没有提供它。这是一个不幸的选择，为了更抽象化，并尽可能少地对接口施加要求。
无论如何，在Java之外，你会发现deque实现确实满足你所请求的属性。
- seh
1
任何使用双向链表的实现都将具有O(n)的随机访问，除了头部或尾部，这正是Java实现所提供的。 - Brian Roach
0
为什么不在插入LinkedList元素时将所有元素插入一个哈希表中，并在常数时间内从哈希表中读取呢？
- AKS
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接