C# singly linked list implementation

Question

While trying to understand how a singly list can be implemented in C#, I came across the link below :

Creating a very simple linked list.

However, as I am new to C#, I got confused by the syntax that is listed in the initial section of the discussion above. A class named Node is being declared and there is another statement within the class declared as "public Node next". Is this statement called a constructor? Please help.

public class Node {
    public Node next;
    public Object data;
 }

Answer 1

In a simple singly-linked list implementation the Node type contains a reference to the next item in the list, which is what the next field in the Node type you posted does. This reference is used to allow iteration of the list.

The enclosing LinkedList class (or whatever you wish to call it) will contain a single Node reference to the first item in the list. Starting from that first node you can then step through the list by getting the next field. When next is null then you have reached the end of the list.

Take this code for example:

public class LinkedList
{
    public class Node
    {
        // link to next Node in list
        public Node next = null;
        // value of this Node
        public object data;
    }

    private Node root = null;

    public Node First { get { return root; } }

    public Node Last 
    {
        get
        {
            Node curr = root;
            if (curr == null)
                return null;
            while (curr.next != null)
                curr = curr.next;
            return curr;
        }
    }
}

The First property simply returns the root node, which is the first node in the list. The Last property starts at the root node and steps through the list until it finds a node whose next property is null, indicating the end of the list.

This makes it simple to append items to the list:

public void Append(object value)
{
    Node n = new Node { data = value };
    if (root == null)
        root = n;
    else
        Last.next = n;
}

To delete a node you have to find the node that precedes it in the list, then update the next link from that node to point to the node following the one to be deleted:

public void Delete(Node n)
{
    if (root == node) 
    {
        root = n.next;
        n.next = null;
    }
    else
    {
        Node curr = root;
        while (curr.next != null)
        {
            if (curr.next == n)
            {
                curr.next = n.next;
                n.next = null;
                break;
            }
            curr = curr.next;
        }
    }
}

There are a few other operations you can perform, like inserting values at positions in the list, swapping nodes, etc. Inserting after a node is fast, before is slow since you have to locate the prior node. If you really want fast 'insert-before' you need to use a doubly-linked list where the Node type has both next and previous links.

---

To expand on your question in the comment...

In C# there are two basic classifications that all types fall into: value types and reference types. The names reflect the way they are passed between blocks of code: value types are passed by value (value is copied to a new variable), while reference types are passed by reference (a reference/pointer is copied to a new variable). The difference there is that changes to a value type parameter will have no effect on the caller's copy of the value, while changes to a reference type parameter will be reflected in the caller's copy of the reference.

The same is true of assigning values and references to variables. In the following, the value of a is not changed when b is changed:

int a = 0;
int b = a;
b = 1;

That's fairly intuitive. What might trip you up is that in C# a struct is also a value type:

public struct test
{
    public string value;
}

static void Main()
{
    test a;
    a.value = "a";
    test b = a;
    b.value = "b";

    Console.WriteLine("{0} {1}", a.value, b.value);
}

The above will give the output a b because when you assigned a to b a copy was made. But if we change the struct for a class:

public class test
{
    public string value;
}

static void Main()
{
    test a = new test(); // Note the 'new' keyword to create a reference type instance
    a.value = "a";
    test b = a;
    b.value = "b";
    Console.WriteLine("{0} {1}", a.value, b.value);
}

Because the variable b is a reference to the same object as the one variable a references, the output here will be b b. The two variables reference the same object.

If you've come from C/C++ or some other similar language, you can think of reference type variables as being pointers. It's not quite the same, and C# does actually have pointers (they're hidden from normal managed code), but it's close enough. Until you point it to an instance of the type it is not fully usable. Just like a char* in C/C++ isn't particularly useful until you point it somewhere.

Joseph Alhabari (has written a great article about value and reference types: C# Concepts: Value vs Reference Types. It is well worth a read, as is much of what he writes. I would also highly recommend you consider getting one of his C# Nutshell books.