从带有约束的链表中删除一个元素

Question

这是一个相当简单的问题，但我很困惑:

给定一个单链表，写一个函数来删除一个给定的节点

1)它必须接受指向开始节点的指针作为第一个参数，要删除的节点作为第二个参数，即指向头节点的指针不是全局的。2)不应返回指向头节点的指针。3)不接受指针指向头节点的指针。

Java的解决方案如下:

void deleteNode(Node node, Node n) {
    if (node == n) {
        if (node.next == null) {
            System.out.println("There is only one node. The list "
                             + "can't be made empty ");
            return;
        }
        node.data = node.next.data;
        n = node.next;
        node.next = node.next.next;
        System.gc();
        return;
    }
    // When not first node, follow the normal deletion process
    // find the previous node
    Node prev = node;
    while (prev.next != null && prev.next != n) {
        prev = prev.next;
    }
    if (prev.next == null) {
        System.out.println("Given node is not present in Linked List");
        return;
    }
    prev.next = prev.next.next;
    System.gc();
    return;
}

我很困惑为什么在删除头节点时，我们没有修改头指针，而是复制字段(更改内容)，但在删除其他节点时，它只是prev.next = prev.next.next如果我们在删除头节点时只做head = head.next，它会工作吗?

谢谢!

Answer 1

代码复制数据而不是修改引用头部的变量的原因是列表的其他用户将有对头部节点的引用。更改局部变量不会对它们的引用产生影响，因此实际上并没有删除节点。将数据复制到头节点有效地删除了它。

所以，例如，如果你有这样的代码:

Node head = new Node("A");
Node tail = new Node("B");
head.next = tail;
deleteNode(head, head);

那么您会期望head.data为"B"，因为原始节点已被删除。如果您只执行node = node.next，那么head仍将指向原始删除的节点。

你发布的代码有很多问题，所以如果你想要改进的建议，请添加评论。这不是从链表中删除节点的典型算法。

你问的一个明显的问题是System.gc的使用。这是不必要的。很少有Java代码需要显式控制垃圾收集的情况。这不是其中之一。在这个问题的公认答案中有一个很好的解释。

你在评论中问为什么删除头部需要移动数据，而删除其他节点只需要在节点周围重定向。原因是您无法访问对头部的引用(如上面的答案所解释的)。您可以访问对其他节点的引用(即前一个节点的next)，因此可以直接更改它们，而不必复制数据。

作为参考，一个更标准的实现是让列表本身存储对头部的引用。这样就可以完全避免节点数据的复制。还请注意，由于节点类是私有的，因此它与值比较。

static class LinkedList<T> {
    private class Node {
        private final T value;
        private Node next = null;
        public Node(T value) {
            this.value = value;
        }
    }
    private Node head = null;
    public void add(T value) {
        Node node = new Node(value);
        node.next = head;
        head = node;
    }
    public void remove(T value) {
        while (head != null && head.value.equals(value))
            head = head.next;
        Node prev = head;
        while (prev != null && prev.next != null) {
            if (prev.next.value.equals(value))
                prev.next = prev.next.next;
            else
                prev = prev.next;
        }
    }
}

这避免了您提供的示例中的任意限制，例如，如果头是唯一的节点，则不能删除它。