双向链表删除运行 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 个元素）。

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

Doubly linked list remove item at index that runs O(n)?

java

data-structures

linked-list

doubly-linked-list