双向链表删除运行 O(n) 的索引处的项目?

Question

有人可以向我解释遍历如何发生的部分，是否有其他更好的删除方法？谢谢。

public T removeAt(int index) {
// Make sure the index provided is valid
if (index < 0 || index >= size) {
throw new IllegalArgumentException();
}
int i;
Node<T> trav;
// Search from the front of the list
if (index < size / 2) {
for (i = 0, trav = head; i != index; i++) {
trav = trav.next;
}
// Search from the back of the list
} else
for (i = size - 1, trav = tail; i != index; i--) {
trav = trav.prev;
}
return remove(trav);
}

Answer 1

目标是在链表中找到索引并删除该索引处的元素。与数组不同，链表在 O(1( 中不提供随机访问，因此此操作始终为 O(n(。但是我们能做得更好吗？

我们知道链表的大小(列表中的元素数量(和我们要删除的索引。使用这些，我们可以将遍历减少到一半 -n/2。

我们检查要删除的元素index属于列表的前半部分还是后半部分。这是通过检查index < size / 2完成的。如果是在前半部分，我们从头部开始遍历并向前移动，直到到达要删除的元素。

如果元素位于列表的后半部分，我们从末尾开始并向后遍历，直到到达要删除的元素。

---

for (i = 0, trav = head; i != index; i++) {
trav = trav.next;
}

trav = head- 将 head 分配给局部变量trav。这里i从 0 开始，一直持续到¹index。现在，我们调用执行删除的例程remove(未显示在代码中(。它的工作将是删除trav指向的元素

从末端遍历的逻辑也是类似的。

for (i = size - 1, trav = tail; i != index; i--) {
trav = trav.prev;
}

---

¹看起来我们似乎在要删除的元素之前停止。仔细观察，我们可以发现循环在i = index时终止。但是当i处于index - 1时，我们会通过执行trav = trav.next来达到index.

示例：假设大小 = 10，索引 = 2。从头部开始

i = 0，移至索引 1 -i++

i = 1，移至索引 2 -i++

i = 2，打破循环

现在，我们指向索引 2(第 3 个元素(处的元素。