理解线性链表

Question

我在理解线性链表数据结构时遇到一些问题。这就是我定义列表元素的方式：

class Node{
    Object data;
    Node link;

    public Node(Object pData, Node pLink){
        this.data = pData;
        this.link = pLink;
    }
}

为了简单起见，我们说列表是链接的节点，因此我们不需要定义类列表（递归原理）。

我的问题是，我真的很困惑如何理解节点是如何连接的，更准确地说是连接节点时节点的顺序。

Node n1 = new Node(new Integer(2), null);
Node n2 = new Node(new Integer(1), n1);

什么是链接？它是上一个元素还是下一个元素？还有其他建议可以帮助我理解这个数据结构吗？

Answer 1

也许这张图可以帮助你理解。

（请注意，箭头是引用，而不是 Java 的指针）

“列表”将是对第一个的引用节点。

Answer 2

link 是对列表中下一个节点的引用。

因此，您将从列表中的第一个节点 n1 开始，您可以直接引用该节点。要获取列表中的第二个节点，您需要引用n1.link。

要迭代列表，您必须有一些起点，例如 n1，然后重复引用 link：

Node n = n1;
while (n != null) {
    println(n.data);
    n = n.link;
}

Answer 3

在单链表中，它是“下一个”。

它看起来像 Java，即使您没有这样标记它。如果这是真的，请考虑使用泛型：

public class Node<T>
{
    T value;
    Node<T> next;
}

Answer 4

我有两个建议。

首先，关于“这是上一个元素还是下一个元素”：这取决于您的数据结构。通常它是下一个元素。

其次，我建议使用指针或引用。 （并且您的 C++ 语法不正确：this 是一个指针，并且 new 运算符也返回一个指针。但不确定您是否使用 C++，因为您没有指定一种语言。）

例如：

class Node {
    Object data;
public:
    Node *next;

    Node (Object pData, Node *pLink) {
        this->data = pData;
        this->next = pLink;
    }
}

这将是一个更有效的结构。然后你可以这样做：

Node *n3 = new Node(new Integer(2), null);
Node *n2 = new Node(new Integer(1), n1);
Node *n1 = new Node(new Integer(3), n2);

或者简单地

Node *n1 = new Node(new Integer(3), new Node(new Integer(1), new Node(new Integer(2), NULL)));

然后你可以按如下方式迭代列表：

for (Node *current = n1; current != NULL; current = current->next)
{
    // do something with the current element
}

我希望这有帮助！

---

如果你使用现代语言，C++ 的 stl 中已经有预制的链表结构，.NET 中的 System.Collections.Generic 中已经有预制的链表结构，我确信也有一个 Java 对应的结构。