java—somone能解释双链表中删除函数的遍历是如何工作的吗?

vjhs03f7  于 2021-06-27  发布在  Java
关注(0)|答案(2)|浏览(312)
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);
  }

解释如何通过遍历来删除双链表。我不懂for循环

oiopk7p5

oiopk7p51#

举个例子,假设我们有这些元素链接列表:

[1,5,9,11,3] 
indexes-> 0 1 2 3  4
size -> 5

现在假设您要删除最后一个元素,它的索引为4,所以我们称之为removeat(4)。为了从一开始就不遍历所有linkedlist,我们检查索引是否大于size/2。4<2 ? 假的。意思是我们从尾巴开始。node trav基本上是遍历linkedlist的指针。当到达特定索引时,只需调用remove方法并传递当前节点。移除(trav)。

klsxnrf1

klsxnrf12#

此函数唯一做的事情是在列表中查找指定的元素。实际的删除由最后一个调用中的另一个方法完成( remove(trav) ).
第一个 if 只检查列表中是否存在指定的索引。
之后,它遍历列表,直到找到指定的元素。它使用一个临时节点 trav . 迭代很简单:获取第一个对象->如果未达到索引,则获取下一个元素->获取下一个元素等等。
但有一个转折点:如果索引位于列表的后半部分,它将从列表的末尾向后迭代。这是一个小的性能优化,因为它最多只有1/2次迭代。

相关问题