java - 单链表迭代复杂度

Question

首先，我对单向链表的基本理解是每个节点只指向下一个后续节点，所以我的问题可能源于我对这种链表的定义不正确。

给定列表设置，到达节点 n 需要遍历它之前的 n-1 个节点，因此搜索和访问的时间复杂度为 O(n)。现在，显然节点插入和删除需要 O(1)，但除非他们谈论的是第一项插入，否则实际上在节点之间插入项目将是 O(n) + O(1) n 和 n+1。

现在，索引列表也有 O(n) 的复杂性，但显然构建这样的索引是不受欢迎的，我不明白为什么。难道我们不能构建一个单链表索引，它允许我们真正的 O(1) 插入和删除，而不必在列表上执行 O(n) 迭代以到达我们的特定节点？它甚至不需要是所有节点的索引，我们可以让它指向子索引，即对于 1000 个项目的列表，第一个索引将指向 1-100、101-200 之间的项目的 10 个不同索引等. 然后这些索引可以指向更小的索引，即 10。通过这种方式到达节点 543 可能只需要 3+(索引遍历)迭代，而不是像典型的单链表那样需要 543。

我想，我想问的是为什么通常应该避免这种索引？

Answer 1

您正在描述一个 skip-list .

跳过列表的搜索、插入、删除时间复杂度为 O(logN)，因为您描述的这个“更小的子索引”- 您的子索引数量为对数(如果您的列表有100 个元素？您需要多少个这样的级别？1,000,000 个元素需要多少？和 10^30？)。
请注意，跳过列表通常保持排序，但如果您愿意，您也可以不排序(实际上是按索引排序)。