我正在学习解决复杂的算法。为此,我遇到了 LinkedList 的实现。我试图理解上述解决方案。在 appendToTail 中,我不理解 while 循环和 while 循环之后的行。在 deleteNode 中,我看不到节点被删除的位置。
class Node {
Node next = null;
int data;
public Node(int d) {
data = d;
}
void appendToTail(int d) {
Node end = new Node(d);
Node n = this;
while (n.next != null) {
n = n.next;
}
n.next = end;
}
Node deleteNode(Node head, int d) {
Node n = head;
if (n.data == d) {
return head.next; /* moved head */
}
while (n.next != null) {
if (n.next.data == d) {
n.next = n.next.next;
return head; /* head didn’t change */
}
n = n.next;
}
}
}
最佳答案
好吧,这里有两种情况需要考虑:首先,当节点是列表中的第一个时。然后头部移动到下一个节点,第一个节点不再是列表的一部分。
在第二种情况下,我们只是逐个节点地遍历整个列表。如果我们到达其下一个节点需要删除的节点(由 if 语句检查),它将更改为将删除节点之后的节点作为下一个节点(if 语句中的第一行)。这将从列表中删除该节点。这里的 head 保持不变,因为改变它会删除应该删除的节点之前的所有元素(如果它被更改为删除节点之后的节点)。
当要删除节点b
时,节点a
所要做的就是指向b
之后的节点( c
)。这是列表的样子:
... a -> b -> c -> ... // before deletion
... a -> c -> ... // after deletion, now a points to c
要获得更好可视化的解释,您可以查看 here .一般案例部分是描述第二种情况的地方。移除的处置没有在植入中明确完成,因为它是由垃圾收集器执行的。
关于java - LinkedList - 试图理解实现,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/37866642/