从约束链表中删除元素

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代码需要显式控制垃圾收集的情况很少见。这不是其中之一。在this question的接受答案中有一个很好的解释。

您在评论中询问了为什么删除头需要移动数据，而删除其他节点时只需要在节点周围进行重定向。原因是因为您无法访问头部的引用（如上面的答案中所述）。您可以访问对其他节点的引用（即前节点的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; 
     } 
    } 
} 

这就避免了在你不能够删除的头，如果它是唯一的节点提供了这样的例子中，任意限制。