java - LinkedList - 试图理解实现

Question

我正在学习解决复杂的算法。为此，我遇到了 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;
        }
   }
}

Answer 1

好吧，这里有两种情况需要考虑:首先，当节点是列表中的第一个时。然后头部移动到下一个节点，第一个节点不再是列表的一部分。

在第二种情况下，我们只是逐个节点地遍历整个列表。如果我们到达其下一个节点需要删除的节点(由 if 语句检查)，它将更改为将删除节点之后的节点作为下一个节点(if 语句中的第一行)。这将从列表中删除该节点。这里的 head 保持不变，因为改变它会删除应该删除的节点之前的所有元素(如果它被更改为删除节点之后的节点)。

当要删除节点b时，节点a所要做的就是指向b之后的节点( c)。这是列表的样子:

... a -> b -> c -> ...  // before deletion
... a -> c -> ...       // after deletion, now a points to c

要获得更好可视化的解释，您可以查看 here .一般案例部分是描述第二种情况的地方。移除的处置没有在植入中明确完成，因为它是由垃圾收集器执行的。