java - 在概念上理解这个链表代码有困难

Question

我无法理解为什么下面的函数 delete() 用于删除链表中的节点。我删减了其余代码，使它们更易于阅读。

所以，我知道我们有一个节点 first，其中有一堆节点链接到 first。我也了解到，在delete()函数中，我们需要新建一个节点n来遍历链表。这是我的挂断电话:

如果我们创建一个新节点n，并设置n = first，我们就创建了一个新节点，节点构造函数定义了n 也将有一个新节点 n.next。那么，我们不是已经创建了一个全新的列表，与以 first 开头的列表分开吗？当 delete() 函数到达它设置 n.next = n.next.next 的位置时，这不是删除整个单独列表中的节点吗？ n 个节点？这如何删除与 first 链接的节点？从概念上讲，这是我的挂断。

我们实际上如何删除列表中以 first 开头的节点？

编辑:我想也许我回答了我自己的问题，但我希望有人可以验证。这是否有效，因为 first 和 n 节点实际上只是对在 Add 中创建的 New Node() 对象的引用()函数？当我学习编程时，它是用 C++ 编写的，所以我习惯于看到指针，这段代码没有多大意义；但据我了解，Java 没有明确的指针……所以我对所有这些都是正确的吗？

public class LinkedList {
    static class Node {
        public Node() { }
        public double item;
        public Node next;
    }

    int N;
    Node first;

    public LinkedList () {
        first = null;
        N = 0;

    public void delete (int k) {
        if (k == 0) {
            first = first.next;
            N--;
        }

        else {
            Node n = first;
            for (int i = 0; i < k-1; i++) {
                n = n.next;
            }
            n.next = n.next.next;
            N--;
        }
    }

    public void add (double item) {
        Node newfirst = new Node ();
        newfirst.item = item;
        newfirst.next = first;
        first = newfirst;
        N++;
    }

    private static void testDelete () {
        MyLinked b = new MyLinked ();
        b.add (1);
        print ("singleton", b);
        b.delete (0);
        print ("deleted", b);
        for (double i = 1; i < 13; i++) {
            b.add (i);
        }
        print ("bigger list", b);
        b.delete (0);
        print ("deleted at beginning", b);
        b.delete (10);
        print ("deleted at end", b);
        b.delete (4);
        print ("deleted in middle", b);
    }

    public static void main (String args[]) {    
        testDelete();
    }

}

Answer 1

这是因为每个链表节点只包含对您的对象的引用和对下一个节点的引用。要删除一个节点，您只需让前一个节点指向它后面的节点即可。

即。初始列表:

linkedList
  ↓
node0 -> node1 -> node2 -> node3

1) 如果您随后要删除 node1，则它看起来像这样

linkedList
  ↓
node0 ----------> node2 -> node3
         node1 ----↑

node0 将不再指向 node1，因此如果您尝试从 node0 迭代，您将转到 node2 下一步。但是，node1 仍会“指向”node2(当然，直到它被垃圾收集为止)。

2) 如果您改为删除 node0，它看起来像这样:

       linkedList
           ↓
node0 -> node1 -> node2 -> node3

您只需将 LinkedList 的 first 字段移动到指向 node1 等，如果您要执行 linkedList。首先 您将访问node1。 node0 然而最终会被垃圾收集，因为没有任何东西引用它(除非你在其他地方这样做)。

请记住，这些情况适用于单链接链表。如果您有一个双向链接的 LinkedList，那么分离和重新附加会变得有点复杂。

--

我认为您对“删除”的作用有误解。在 Java 中，用户不会手动管理内存，所以你不会调用 malloc 或 delete、destroy 等，你只需删除所有对对象的引用，它们最终将被 JVM 收集为垃圾。

在上面的代码中，我们只是从数据结构的角度来讨论从LinkedList中“删除”一个Node。