Linked List Design
<p>The other day in a local .NET group I attend the following question came up: "Is it a valid interview question to ask about Linked Lists when hiring someone for a .NET development position?"</p>

<p>Not having a computer science degree and being a self taught developer my response was that I did not feel it was appropriate as I in 5 years of developing with .NET had never been exposed to linked lists and did not hear any compelling reason for a use for one.</p>

<p>However the person commented that it is a very common interview question so I decided when I left that I would do some reasearch on linked lists and see what I might be missing.</p>

<p>I have read a number of posts on stack overflow and various google searches and decided the best way to learn about them was to write my own .NET classes to see how they worked from the inside out.</p>

<p>Here is my class structure</p>

<p>Single Linked List</p>

<p>Constructor  </p>

<pre><code>public SingleLinkedList(object value);

// Public Properties  
public bool IsTail;
public bool IsHead;
public object Value;
public int Index;
public int Count;

// private fields not exposed to a property  
private SingleNode firstNode;  
private SingleNode lastNode;  
private SingleNode currentNode;  
</code></pre>

<p>Methods  </p>

<pre><code>public void MoveToFirst();
public void MoveToLast();
public void Next();
public void MoveTo(int index);
public void Add(object value);
public void InsertAt(int index, object value);
public void Remove(object value);
public void RemoveAt(int index);
</code></pre>

<p>Questions I have:</p>

<p>What are typical methods you would expect in a linked list?</p>

<p>What is typical behaviour when adding new records? For example if I have 4 nodes and I am currently positioned in the second node and perform Add() should it be added after or before the current node? Or should it be added to the end of the list?</p>

<p>Some of the designs I have seen explaining things seem to expose outside of the LinkedList class the Node object. In my design you simply add, get, remove values and know nothing about any node object. </p>

<p>Should the Head and Tail be placeholder objects that are only used to define the head/tail of the list?</p>

<p>I require my Linked List be instantiated with a value which creates the first node of the list which is essentially the head and tail of the list. Would you change that ?</p>

<p>What should the rules be when it comes to removing nodes. Should someone be able to remove all nodes? </p>

<p>Here is my Double Linked List</p>

<p>Constructor  </p>

<pre><code>public DoubleLinkedList(object value);
</code></pre>

<p>Properties  </p>

<pre><code>public bool IsHead;
public bool IsTail;
public object Value;
public int Index;
public int Count;
</code></pre>

<p>Private fields not exposed via property  </p>

<pre><code>private DoubleNode currentNode;
</code></pre>

<p>Methods  </p>

<pre><code>public void AddFirst(object value);
public void AddLast(object value);
public void AddBefore(object existingValue, object value);
public void AddAfter(object existingValue, object value);
public void Add(int index, object value);
public void Add(object value);
public void Remove(int index);
public void Next();
public void Previous();
public void MoveTo(int index);
</code></pre>
