java - ArrayList 或 Linked List - 如果要执行插入/删除和查找操作，则使用哪个集合

Question

众所周知，链表是为了快速插入删除Array List 用于快速查找

我要求 List 中保存 10000 条记录。我会使用哪个集合。可以对该列表执行查找和插入/删除操作。

我使用哪个集合以及为什么？或者我会使用自己创建的 Collection 吗？

Answer 1

插入

链表

先插入 - O(1)

最后插入 - O(1)

Insert anywhere - O(n) - 这是因为需要通过索引找到插入的位置。

数组列表

先插入 - O(n)

最后插入 - O(1)

在任何地方插入 - O(n)

---

所以 LinkedList 和 ArrayList 在任何地方插入都是相同的 O(n)。

删除

链表

先删除 - O(1)

最后删除 - O(1)

删除任何地方 - O(n) - 同样是因为需要通过索引找到要删除的位置。

数组列表

先删除 - O(n)

最后删除 - O(1)

删除任何地方 - O(n)

所以 LinkedList 和 ArrayList 在任何地方都具有相同的 O(n) 删除。

---

如您所见，两者在任何位置的插入和删除都是相同的。如果您总是执行插入最后一个操作，那么 ArrayList 适合使用，因为如果您知道索引，那么查找 LinkedList 的时间复杂度为 O(1) 和 O(n)。我认为你需要找到更适合使用的黄金中间。

此外，如果您不关心无重复，您可以使用 HashSet。它基于哈希表，并为插入和删除、查找提供合适的性能(O(1)，O(log(n) 在许多情况下)。

哈希集jdoc

This class offers constant time performance for the basic operations (add, remove, contains and size), assuming the hash function disperses the elements >properly among the buckets.