java - 理解链表

Question

我无法理解类(class)中的链接列表。我似乎遇到的最大问题是数据的存储方式。我看到代码主要是 add(x) 在列表中添加一个新节点，但它似乎没有意义。

添加代码。

boolean add(T x) {
  Node u = new Node();
  u.x = x;
  if (n == 0) {
    head = u;
  } else {
    tail.next = u;
  }
  tail = u;
  n++;
  return true;
}

这直接来 self 正在学习的类(class)的教科书。我上网查找更多资源，并在 GITHUB 上从一本更详细的教科书 Source 中找到了这段代码。 。代码太长，无法直接粘贴。

总的来说，我看到名为“Head”、“Tail”和“u”的类存储诸如[Head]->[u]->[Tail]之类的信息。此外，当我阅读 add 方法时，我将存储的信息可视化为 [Head]->[u]->[u]->[u]->[Tail]。

每个节点如何知道要查看哪个“u”节点。每个都引用 u 节点。要么u 每次都被覆盖，要么获取u 信息将返回所有u 的值。 node.next 如何区分每个 u 节点？不应该是代码而不是:

add(x) {
  Node u = new Node();
  u.x = x;
}

更像是:

add(x,y) {
  Node y = new Node();
  u.x = x;
}

因此每个节点都有不同的名称链接到[Head]->[a]->[b]->[c]->[Tail]

Answer 1

变量名称本身并不像您认为的那样重要。 u 只是指向 Node 的一个实例。

假设您要创建一个整数链接列表:

您执行add(1)。此时，n=0。 在add方法中，初始化了一个新节点。我们将其称为u。现在，我们将值设置为1。到目前为止，我们已经创建了一个Node，其值等于1。

由于n=0，我们的head现在也将引用此节点。我们递增 n++ 来跟踪列表的当前长度。我们还使 tail 引用新添加的节点，因为我们总是添加到列表的末尾。

现在，您执行add(2)。此时，n=0。在add方法中，初始化了一个新节点。我们将其称为u。现在，我们将值设置为1。我们不需要更新头，因为 1 是列表的第一个节点。

但是，我们需要将 2 添加到列表末尾。这意味着 tail 必须引用新创建的值为 2 的 Node。那么，我们该怎么做呢？好吧，到目前为止，tail 一直引用值为 1 的节点。因此，我们只需更新该节点的 next 以指向 u 所指向的同一节点(因为这是我们要添加到列表末尾的新创建的节点)。

最后，我们将增加 n 并将 tail 设置为指向我们刚刚添加的节点。