LinkedList<T> 和 LinkedListNode<T> 在 C# 中究竟是如何实现的？ LinkedList<T>.Remove(LinkedListNode<T>) 究竟是如何工作的？

Question

网上查了一下，内置的LinkedList是C#中的双向链表。我还研究了 LinkedList.Remove(LinkedListNode) 方法。但我仍然找不到问题的答案。以下是代码片段：

    public string DequeueCat()
    {
        LinkedListNode<string> temp = animals.First;
        while (temp != null && temp.Value.Contains("Cat") == false)
        {
            temp = temp.Next;
        }
        if (temp!=null && temp.Value.Contains("Cat"))
        {
            animals.Remove(temp);
            return temp.Value;
        }
        else
        {
            Console.WriteLine("No more Cats available");
            return null;
        }
    }

变量animals的类型是LinkedList<string>。当我们用 animals.First 实例化一个新的 LinkedListNode<string> 时到底发生了什么？如LinkedListNode<string> temp = animals.First;。是否发生深度复制，并且原始 LinkedList（由 animals.First 指向）被复制到 temp，位于堆上的新位置？另外，当我们写 animals.Remove(temp) 时，temp LinkListNode 被销毁。并且，相应的值从 animals LinkedList 中删除。

以下是执行animals.Remove(temp)前的手表window -

并且，以下是执行 animals.Remove(temp) 后的手表 window -

我的问题是，为什么在执行animals.Remove(temp)之后temp被销毁了？此外，如果 temp 已在堆上的单独位置创建（与原始 LinkedList 相比），那么我们如何知道从原始 LinkedList 中删除 temp，animals LinkedList 将从中删除相应的项目 animals 链表？

完整代码如下：

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AnimalShelter
{
    class AnimalsShelter
    {
        //This class will have the following functions: 
        //Enqueue, DequeueAny, DeQueueDog, DeQueueCat
        //Implement queue using C# inbuilt linked list.
        LinkedList<string> animals = new LinkedList<string>();
        public void Enqueue(string animal)
        {
            animals.AddLast(animal);
        }

        public string DequeueAny()
        {
            LinkedListNode<string> firstAnimal = animals.First;
            if (firstAnimal != null)
            {
                animals.RemoveFirst();
                return firstAnimal.Value;
            }
            else
            {
                Console.WriteLine("No more animanls left in queue.");
                return null;
            }
        }

        public string DequeueDog()
        {
            LinkedListNode<string> temp = animals.First;
            while(temp!=null && temp.Value.Contains("Dog")==false)
            {
                temp = temp.Next;
            }
            if(temp!=null && temp.Value.Contains("Dog"))
            {
                animals.Remove(temp);
                return temp.Value;
            }
            else
            {
                Console.WriteLine("No more Dogs available");
                return null;
            }
        }

        public string DequeueCat()
        {
            LinkedListNode<string> temp = animals.First;
            while (temp != null && temp.Value.Contains("Cat") == false)
            {
                temp = temp.Next;
            }
            if (temp!=null && temp.Value.Contains("Cat"))
            {
                animals.Remove(temp);
                return temp.Value;
            }
            else
            {
                Console.WriteLine("No more Cats available");
                return null;
            }
        }
    }
    class Program
    {
        static void Main(string[] args)
        {
            AnimalsShelter shelter = new AnimalsShelter();
            shelter.Enqueue("Dog1");
            shelter.Enqueue("Dog2");
            shelter.Enqueue("Cat1");
            shelter.Enqueue("Dog3");
            shelter.Enqueue("Cat2");
            shelter.Enqueue("Cat3");
            Console.WriteLine(shelter.DequeueCat());
            Console.WriteLine(shelter.DequeueAny());
            Console.WriteLine(shelter.DequeueDog());
            Console.WriteLine(shelter.DequeueCat());
            Console.WriteLine(shelter.DequeueAny());
            Console.WriteLine(shelter.DequeueAny());
        }
    }
}

非常感谢任何有关此的信息。谢谢！

Answer 1

The variable animals is of type LinkedList<string>. What exactly happens when we instantiate a fresh LinkedListNode<string> with animals.First? Such as LinkedListNode<string> temp = animals.First;. Does a Deep Copy occur

没有。您所做的只是复制一个参考 LinkedListNode<string> temp = animals.First;

Also, when we write animals.Remove(temp), the temp LinkListNode is destroyed.

没有。它没有被摧毁，但是它的联系正在被删除。还是一样的参考。

My question is that, why is temp destroyed, after executing animals.Remove(temp)?

没有。再一次，它没有被摧毁。但是它的链接正在被删除。

Also, if temp has been created at a separate place on the Heap

没有。它没有在堆上的单独位置创建，您所做的只是复制引用。

then how do we know that Removing temp from the original, animals LinkedList will remove the corresponding item from the animals LinkedList

我们知道，因为它是相同的对象/相同的引用。

这是 Remove 的近似代码。如您所见，没有魔法：

internal void InternalRemoveNode(LinkedListNode<T> node) 
{

     ...

     if ( node.next == node)
            head  = null;      
     else 
     {
         node.next.prev = node.prev;
         node.prev.next = node.next;
         if ( head == node) 
             head = node.next;
     }
     node.Invalidate();  
     count--;
     version++;          
}

进一步阅读

Reference types (C# Reference)

There are two kinds of types in C#: reference types and value types. Variables of reference types store references to their data (objects), while variables of value types directly contain their data. With reference types, two variables can reference the same object; therefore, operations on one variable can affect the object referenced by the other variable. With value types, each variable has its own copy of the data, and it is not possible for operations on one variable to affect the other (except in the case of in, ref and out parameter variables; see in, ref and out parameter modifier).

LinkedList<T> 和 LinkedListNode<T> 在 C# 中究竟是如何实现的？ LinkedList<T>.Remove(LinkedListNode<T>) 究竟是如何工作的？

How exactly is LinkedList<T> and LinkedListNode<T> implemented in C#? And how exactly does LinkedList<T>.Remove(LinkedListNode<T>) work?

c#

deep-copy

doubly-linked-list