StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>In a simple singly-linked list implementation the <code>Node</code> type contains a reference to the next item in the list, which is what the <code>next</code> field in the <code>Node</code> type you posted does. This reference is used to allow iteration of the list.</p> <p>The enclosing <code>LinkedList</code> class (or whatever you wish to call it) will contain a single <code>Node</code> reference to the first item in the list. Starting from that first node you can then step through the list by getting the <code>next</code> field. When <code>next</code> is null then you have reached the end of the list.</p> <p>Take this code for example:</p> <pre><code>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; } } } </code></pre> <p>The <code>First</code> property simply returns the root node, which is the first node in the list. The <code>Last</code> property starts at the root node and steps through the list until it finds a node whose <code>next</code> property is null, indicating the end of the list.</p> <p>This makes it simple to append items to the list:</p> <pre><code>public void Append(object value) { Node n = new Node { data = value }; if (root == null) root = n; else Last.next = n; } </code></pre> <p>To delete a node you have to find the node that precedes it in the list, then update the <code>next</code> link from <em>that</em> node to point to the node following the one to be deleted:</p> <pre><code>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; } } } </code></pre> <p>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 <code>Node</code> type has both <code>next</code> and <code>previous</code> links.</p> <hr> <p>To expand on your question in the comment...</p> <p>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.</p> <p>The same is true of assigning values and references to variables. In the following, the value of <code>a</code> is not changed when <code>b</code> is changed:</p> <pre><code>int a = 0; int b = a; b = 1; </code></pre> <p>That's fairly intuitive. What might trip you up is that in C# a <code>struct</code> is also a value type:</p> <pre><code>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); } </code></pre> <p>The above will give the output <code>a b</code> because when you assigned <code>a</code> to <code>b</code> a copy was made. But if we change the struct for a class:</p> <pre><code>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); } </code></pre> <p>Because the variable <code>b</code> is a reference to the <em>same</em> object as the one variable <code>a</code> references, the output here will be <code>b b</code>. The two variables reference the same <em>object</em>.</p> <p>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 <em>instance</em> of the type it is not fully usable. Just like a <code>char*</code> in C/C++ isn't particularly useful until you point it somewhere.</p> <p>Joseph Alhabari (has written a great article about value and reference types: <a href="http://www.albahari.com/valuevsreftypes.aspx"><em>C# Concepts: Value vs Reference Types</em></a>. It is well worth a read, as is much of what he writes. I would also highly recommend you consider getting one of his <a href="http://www.albahari.com/nutshell/"><strong>C# Nutshell</strong></a> books.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload