理解链表

Question

我无法理解我课程中的 linked 列表。我似乎遇到的最大问题是数据的存储方式。我看代码主要是 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;
}

这直接来自我正在学习的课程的教科书。我上网查找更多资源，并在 GITHUB 上从更详细的教科书 Source 上找到了这段代码。代码太长，直接粘贴即可。

总的来说，我看到类名为 'Head' 'Tail' 和 'u' 存储信息，如 [Head]->[u]->[Tail]。此外，当我阅读添加方法时，我将存储的信息可视化为 [Head]->[u]->[u]->[u]->[Tail].

每个节点如何知道要查看哪个 'u' 节点。每个都引用 u 节点。 u 每次都被覆盖，或者获取 u 信息将 return 所有 u 的值。 node.next 如何区分每个 u 节点？代码不应该是：

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

更像：

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

所以每个节点都有不同的名称 link 到 [Head]->[a]->[b]->[c]->[Tail]

Answer 1

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

假设您要创建一个整数链表：

你做到了 add(1)。此时，n=0。在add方法中，初始化了一个新节点。我们只是将其称为 u。现在，我们将值设置为 1。到现在为止，我们已经创建了一个Node，它的值等于1.

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

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

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

为了结束，我们将递增 n 并将我们的 tail 设置为指向我们刚刚添加的节点。

Answer 2

因此，您想将一个节点添加到链表中。

这将创建节点 u，其中包含相应的信息 x。

Node u = new Node();
u.x = x;

现在，有 2 个选项：

A - 这是您要添加到链表中的第一个节点

B - 列表中已有节点，您正在添加另一个节点。

这里是if进入的地方。

if (n == 0) {
  head = u;
} else {
  tail.next = u;
}

A - 如果 n（列表中节点的计数器）等于 0，则它为空。所以，节点 u 是它的头部。

B - 否则，您将在它的实际 tail 之后添加一个新节点，因此您添加对实际 tail 的引用，说明该节点将是下一个节点。

最后，你必须说你要添加的节点是链表的新 tail（如果它是空的，那么 u 将是 head 并且tail同时）。您还需要增加节点的计数器 n.

tail = u;
n++;

Answer 3

来自 java.util.LinkedList 的节点 class 描述如下：

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;
    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

节点包含下一个和上一个节点，因此每个节点都知道其上一个和下一个节点。

理解链表

understanding linked lists

java

linked-list

singly-linked-list

doubly-linked-list