LinkedList 如何跟踪所有节点 - C#？

Question

我一直在努力尝试开发自己的单向链表，我无法理解如何在链表的末尾插入一个节点？

代码如下：

class LinkedList
{
    private Node head;

    public void AddLast(int value)
    {
        if (head == null)
        {
            head = new Node();

            head.value = value;
            head.next = null;
        }
        else
        {
            Node temp = new Node();
            temp.value = value;

            Node current = head;

            while (current.next != null)
            {
                current = current.next;
            }

            current.next = temp;
        }
    }

    public void PrintAll() 
    {
        Node current = head;

        while (current != null)
        {
            Console.WriteLine(current.value);
            current = current.next;
        }

    }
}

这里是主要方法

    static void Main(string[] args)
    {
        LinkedList list = new LinkedList();
        list.AddLast(3);
        list.AddLast(5);
        list.AddLast(4);
    }

1) 我完全理解了第一部分 list.AddLast(3)。由于 head 为 null，我们创建一个新的节点 head 并为其赋值。

2) 当调用list.AddLast(5)时，head不再为null，因此我们创建了一个新的临时节点，并为其赋值。现在我们创建一个新的节点 current 来保存 Head 的值，需要注意的是 Head.Next 是空的。

现在我们遍历 current 并将我们的临时节点放置到 current.Next。

3) 现在，在调用 list.AddLast(5) 时，当前是否应该再次被 Head 的内容覆盖？这是 Head.Value = 3 和 Head.Next = Null.

所以 current.Value = 3 和 Current.Next = Null 不应该吗？如果不是，那为什么呢？

Answer 1

有大量 linked 列表的实现。然而，对于一个简单的单链表，我们可以这样想

如果我没理解错的话，这是你不理解的部分

// All this part of the method does is add the new value to the end of the list

// create node
Node temp = new Node();
// assign its value
temp.value = value;

// now we want to start with the head and follow 
// the chain until we find the last node
Node current = head;
// has it got a next element
while (current.next != null)
{
    // if so change current to next and look again
    current = current.next;
}

// yay no more nexts, lets add temp here
current.next = temp;

// you have effectively added your new element to the end of the list

说另一种常见的实现方式是将 Last/Current 节点保存在 class 中（就像您对 head 所做的那样）。

在这种情况下，我们可以引用 Node 并添加到它的下一个并更新 [=58= 中的 Last 引用，而不是遍历链].然而，当我们必须删除最后一项时，我们不仅要记住 class 中的 null Last，还要记住 null 它的父 Next 引用.

唯一的方法是再次迭代链。

为了更容易，我们可以实现一个双重 linked 列表，这样更容易找到它的父级

更新

what I don't understand is that why isn't the link to next nodes lost when current who holds that info is updated every time with content of Head.

在上面，把current当成一个临时变量，它在生活中唯一的工作就像链中下一个link的临时标记，

当我们调用这个

current = current.next;

它所做的一切都是为了抓住 current.next 中的内容，并再次为循环条件保留它。我们可以在不破坏 current.next

中的内容的情况下调用它

最后一次，当我们在 current.next 中一无所获时即当循环检查 current.next== null 我们可以安全地将我们的临时节点放入其中时 current.next = temp; <== 反正它是空的

Answer 2

Node current = head;

上面的语句执行时，current只是暂时赋值了head的引用，没有赋值。所以current在那一刻只指向head。如果在此语句之后执行，current.value 将为您提供 head 的值。

while (current.next != null)
{
    current = current.next;
}

现在，当上面的 while 循环执行时，它遍历链表并将当前节点带到链表中的最后一个节点，该节点将具有 current.next = null.

current.next = temp;

当上述语句执行时，新节点被添加到链表的最后一个。

Answer 3

您创建了 LinkedList 的新实例。

list.AddLast(3); --> head是null，你新建一个Node赋值给head.

list.AddLast(5); --> 创建一个新的 Node temp 并将 5 赋给值。请记住 head 的 value = 3 而 next 是 null。创建了一个名为 current 的新变量，它指向 head。然后 while 遍历树，如果 current 的 next 不为空，则将 current 的 next 重新分配给那个 node。在这种情况下，while 循环不是运行因为 head 的 next 是空的，所以它所做的只是将 head.next 分配给你的 current节点。此时我们有head.value = 3、head.next = new Node(5, null);

list.AddLast(4); --> 与上面相同，但 while 循环现在运行s。一路遍历找到一个没有next值的Node赋值给4。此时我们有 head.value = 3, head.next = new Node(5, new Node(4, null))

LinkedList 如何跟踪所有节点 - C#？

How a LinkedList Keeps Track of All Nodes - C#?

.net

c#

linked-list

data-structures

singly-linked-list