java LinkedList试图理解实现

Question

我正在学习解决复杂的算法。为此，我遇到了LinkedList的实现。我试图理解上述解决方案。在附录中，我不理解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语句中的第一行）。这将从列表中删除节点。在这里，头部保持不变，因为更改它将删除应该删除的节点之前的所有元素（如果它更改为删除节点之后的节点）

当节点b应该被删除时，节点a所要做的就是指向b（c）之后的节点。下面是列表的外观：

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

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

Answer 2

LinkedLists有几个实现。有些只在列表的head中保留一个pointer。其他人跟踪尾部以在O(1)中完成对尾部的附加

此实现不维护尾部指针，因此必须从头部开始遍历列表

1  > 2  > null
^
head

所以this指的是列表的头。while循环在列表中移动，直到到达末尾或（直到n中的下一个节点指针等于null）

在上面的示例中，循环将在此处终止

n  n.next
2   null

然后循环将退出并设置：

n.next = end

新列表如下所示：

1  > 2  > 3
^
head