Getting garbage values while implementing linked list using structs in C# (unsafe construct)

Question

I was trying to verify a behavior reported by one of my friends, so I implemented Singly linked list in C# using struct. Since I had to use pointers so I used unsafe construct provided by C#. I also set the property to Allow unsafe code in build tab of project properties to make the code compilable.

Here is my complete code implementation:

public unsafe struct NodeList
{
    public Node* head;
    public Node* current;

    public  void AddNode(int d)
    {
        Node n = new Node();
        n.data = d;
        n.link = null;
        if (head == null)
        {
            head = current = &n;
        }
        else
        {
            (*current).link = &n;
            current = &n;
        }
        Console.WriteLine(head->data);
    }

    public void TraverseNodes()
    {
        Node* temp = head;
        while(temp != null)
        {
             Console.WriteLine(temp -> data);
             temp= temp -> link;                
        }
    }
}

public unsafe struct Node
{
    public int data;
    public Node* link;
}

class Program
{
    private static void UnsafeDSImplementation()
    {
        var myLinkedList = new NodeList();
        myLinkedList.AddNode(2);
        myLinkedList.AddNode(4);
        myLinkedList.TraverseNodes();
    }

    static void Main(string[] args)
    {
        UnsafeDSImplementation();
    }
}

Errant observations:

1. Every time I go inside AddNode method and try to print node data value then for the first time I get 2 and second time I get 4. I'm wondering how come head is changing when I assign it only once while adding first node.
2. While traversing all the nodes - I get value of data for first node as 2243610 (this keeps changing on every run so it is garbage) and System.NullRefernceException exception for second node iteration. Both nodes should print data correctly.

Now the behavior I'm getting may be due a mistake I've made in code or may be it is obvious as I'm using pointers from managed world. I need your help to figure this out.

Answer 1

Allocate memory using native Marshal.AllocHGlobal (which is like malloc in C)

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

namespace Linked_List
{

public unsafe class NodeList
{
    public static Node * head ;

    public void AddNode(int d)
    {

        Node* newNode = (Node*)Marshal.AllocHGlobal(sizeof(Node)).ToPointer();
        newNode->data = d;
        newNode->link = null;

        Node* temp;
        if (head == null)
        {
            head = newNode;
        }
        else
        {
            temp = head;
            head = newNode;
            newNode->link = temp;

        }
        Console.WriteLine(head->data);
    }

    public void TraverseNodes()
    {
        Node* temp = head;
        while (temp != null)
        {
            Console.WriteLine(temp->data);
            temp = temp->link;
        }
    }
}

public unsafe struct Node
{
    public int data;
    public Node* link;
}


unsafe class  Program
{
    private  static void UnsafeDSImplementation()
    {
        var myLinkedList = new NodeList();
        myLinkedList.AddNode(2);
        myLinkedList.AddNode(4);
        myLinkedList.TraverseNodes();
    }


    static void Main(string[] args)
    {
        UnsafeDSImplementation();
    }
 }
}

Note: You also need to free memory using Marshal.FreeHGlobal