双向链表删除运行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时终止。但是通过执行index，当i处于index - 1时我们将达到trav = trav.next。

示例：假设尺寸= 10，索引=2。从头开始

[i = 0，移至位置1。i++

i = 1，移至位置2 i++

i = 2，移至位置3 i++

[i = 3，打破循环

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