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

Question

I researched online that the inbuilt LinkedList is a Doubly LinkedList in C#. I also researched on the LinkedList.Remove(LinkedListNode) method. But I still couldn't find the answer to my question. Following is the code snippet:

    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;
        }
    }

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 and, the original LinkedList (pointed by animals.First), gets copied over to temp, at a new location on the Heap? Also, when we write animals.Remove(temp), the temp LinkListNode is destroyed. And, the corresponding value is removed from the animals LinkedList.

Following is the watch window before executing animals.Remove(temp) -

And, following is the Watch window AFTER executing animals.Remove(temp) -

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 (as compared to the original LinkedList), then how do we know that Removing temp from the original, animals LinkedList will remove the corresponding item from the animals LinkedList?

Following is the entire code:

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());
        }
    }
}

Any light on this is highly appreciated. Thanks!

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

No. All you have done is copy a reference LinkedListNode<string> temp = animals.First;

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

No. It's not being destroyed, however its linkages are being removed. It's still the same reference.

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

No. Once again it's not being destroyed. however its linkages are being removed.

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

No. It hasn't been created at a separate place on the heap, all you did is copy the reference.

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

We know, because it was the same object / same reference.

Here is an approximation of the code for Remove. As you can see there is no magic:

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++;          
}

---

Further Reading

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).