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;
}
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With