有人能解释一下双链表中删除函数的遍历是如何工作的吗

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);
}

解释一下这个遍历是如何去除一个双链表的。我不理解for loop

Answer 1

此函数唯一要做的就是在列表中查找指定的元素。实际的移除是由最后一个调用(remove(trav)(中的另一个方法完成的。

第一个if只是检查指定的索引是否存在于列表中。

之后，它遍历列表，直到找到指定的元素。它使用一个临时节点trav。迭代很简单：获取第一个对象->如果未达到索引，则获取下一个元素->获取下一个元素等

不过有一个转折点：如果索引在列表的后半部分，它会从列表的末尾向后迭代。这是一个小的性能优化，因为它在最大下只有大小/2次迭代

Answer 2

让我们举一个例子，假设我们有以下元素LinkedList:

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

现在假设您想要移除最后一个元素，它的索引为4，所以我们调用removeAt(4(。为了不从一开始遍历所有LinkedList，我们检查索引是否大于size/2。4<2.false。意味着我们从尾部开始。节点trav基本上是一个遍历LinkedList的指针。当您到达该特定索引时，只需调用remove方法并传递当前节点。移除(trav(。