各种数据结构的时间复杂度是多少？

阵 列

• 设置，在特定索引处检查元素：O（1）
• 搜索：如果数组未排序，则为 O（n）;如果数组已排序并使用二进制搜索等内容，则为 O（log n），
• 正如Aivean所指出的，Arrays上没有可用的操作。我们可以通过将元素设置为某个特定值（例如-1，0等）来象征性地删除元素，具体取决于我们的要求Delete
• 同样，对于数组基本上如开头所述InsertSet

数组列表：

• 地址： 摊销 O（1）
• 移除：O（n）
• 包含：O（n）
• 尺寸： O（1）

链表：

• 插入：O（1），如果在头部完成，如果在其他任何地方完成，则为O（n），因为我们必须通过线性遍历链接列表来达到该位置。
• 删除：O（1），如果在头部完成，O（n）如果在其他任何地方，因为我们必须通过线性遍历链接列表来达到该位置。
• 搜索： O（n）

双链表：

• 插入：O（1），如果在头部或尾部完成，则为O（n），如果在其他任何地方，因为我们必须通过线性遍历链接列表来达到该位置。
• 删除：O（1），如果在头部或尾部完成，则为O（n），如果在其他任何地方，因为我们必须通过线性遍历链接列表来达到该位置。
• 搜索： O（n）

叠：

• 推： O（1）
• 流行： O（1）
• 顶部： O（1）
• 搜索（类似于查找，作为特殊操作）：O（n）（我猜是这样）

Queue/Deque/Circular Queue：

• 插入件： O（1）
• 移除： O（1）
• 尺寸： O（1）

二叉搜索树：

• 插入、删除和搜索：平均情况：O（log n），最坏情况：O（n）

红黑树：

• 插入、删除和搜索：平均情况：O（对数 n），最坏情况：O（对数 n）

堆/优先级队列（最小值/最大值）：

• 查找最小值/查找最大值：O（1）
• 插入： O（对数 n）
• 删除最小值/删除最大值：O（log n）
• 提取最小值/提取最大值：O（对数 n）
• 查找，删除（如果提供）：O（n），我们将不得不扫描所有元素，因为它们不像BST那样排序

HashMap/Hashtable/HashSet：

• 插入/删除：O（1） 摊销
• 调整大小/哈希：O（n）
• 包含：O（1）

Baeldung指出了ArrayList，LinkedList和CopyOnWriteArrayList的一些时间复杂性：https://www.baeldung.com/java-collections-complexity，对于Map实现，这里：https://www.baeldung.com/java-hashmap

他还添加了基准，以突出实现之间的差异。