Bar*_*234 2 java algorithm list time-complexity
首先,我对单链表的基本理解是每个节点只指向下一个后续节点,所以我的问题可能源于我对这种列表的定义不正确.
给定列表设置,到达节点n将需要迭代前面的n-1个节点,因此搜索和访问将是O(n).现在,显然节点插入和删除需要O(1),但除非他们正在谈论第一个项目插入,那么实际上你将在节点n和n +之间插入项目为O(n)+ O(1)1.
现在,索引列表也会有O(n)的复杂性,但显然构建这样的索引是不受欢迎的,我无法理解为什么.我们不能建立一个单链表索引,它允许我们真正的O(1)插入和删除,而不必在列表上执行O(n)迭代来到我们的特定节点？它甚至不需要是所有节点的索引,我们可以指向子索引,即对于1000个项目的列表,第一个索引将指向10个不同的索引,用于1-100,101-200之间的项目等然后这些索引可以指向更小的索引.这样,到达节点543可能只需要3次(索引遍历)迭代,而不是像典型的单链表那样需要543次迭代.
我想,我要问的是为什么通常应该避免这种索引？