Implementing a Double Linked List in C# - part II

In the previous post we've discussed the domain and the requirements of an implementation of a double linked list. It is now time descend the ladder of abstraction to the level where we can construct an usable artifact.

We'll start by analyzing the domain description and requirements, as we try to synthesize some sort of blueprint for the implementation. Right from the beginning we discover our two main entities: the list, and the nodes. It's pretty obvious we'll have different classes for each of them. Let's begin with the nodes.

The node has two major concerns: it has to hold data, and it has to retain references to it's left and right neighbors. As we've decided that any data can be stored into our list, and presuming the users of the list are kind enough to group multiple fields of data into types, we can make our nodes generic. Anything else is not important at this time.

On the other hand, the list has a bit more concerns. First of all, it has to hold some reference to the data. This is done by the means of the two sentinels. When a list is created, the sentinels hold a reference with each other. As nodes are inserted the references are changed, in such a way as to form a chain o references starting form the left sentinel, and ending with the right sentinel.

The list also has to know the number of nodes stored in the list (excluding the sentinels). We have to do this, without counting the nodes every time this value will be needed. This implies that we must control the process of altering the structure of the list in order to keep an updated count of its elements.

The main source of errors, as far as we are concerned at the moment, are boundary crossings. This can be easily solved by checking the value of received indexes, and throwing the appropriate exceptions.

As we have decided that the list must behave as a collection, it is time to decide on an interface that we'll implement, in order to provide the users of the list with a familiar experience. Searching the MSDN documentation, the IList<T> springs into attention, as it covers most of our needs. Actually, all the necessary functionality of the list will come from implementing this interface. Any other added functionality will only have the purpose of easing the use of the list.

At this moment we can start sketching the implementation of the list. Take note that the comments and documentation were removed for the sake of brevity.

The Node class is short and self explanatory:
public class Node<T>
{
public T Data;
public Node<T> Previous;
public Node<T> Next;
}

Next we start constructing the list:

public class DoubleLinkedList<T> : IList<T>
{
private int count;
private readonly Node<T> leftSentinel;
private readonly Node<T> rightSentinel;

The sentinels and node count will be initialized in the constructor. Remember that the list starts with the two sentinels referencing each other:

public DoubleLinkedList()
{
leftSentinel = new Node<T>();

rightSentinel = new Node<T>();

leftSentinel.Next = rightSentinel;
rightSentinel.Previous = leftSentinel;

count = 0;
}

The insert algorithm works in the following steps:

• Check boundaries.
  
• Search the n'th node. If there are no nodes, or the specified index is next to the last existing node, return the right sentinel.
  
• Insert the new value into a new node between the node found above, and its left neighbor.
  
• Increment the node count.
  

We will separate the last two steps of the algorithm into a helper method, AddBefore, as we will use them in another insert method, which will add an item directly at the end of the list.

private void AddBefore(Node <T> node, T item)
{
Node<T> newNode = new
Node<T>();
newNode.Next = node;
newNode.Previous = newNode.Previous;
newNode.Data = item;
node.Previous.Next = newNode;
node.Previous = newNode;
count++;
}

The search method can be reused in some other cases(item retrieval and removal), so we'll move the boundary check inside it:

private Node<T> Find(int index)
{
if (index < 0 || index >= count)
{
throw new ArgumentOutOfRangeException("index");
}

Node<T> currentNode = rightSentinel.Next;

while (index > 0)
{
currentNode = currentNode.Next;
index--;
}

return currentNode;
}

Now we can finish the implementation of the two insert methods:

public void Insert(int index, T item)
{
Node<T> nextNode = index == count ?
rightSentinel : Find(index);
AddBefore(nextNode, item);
}

public void Add(T item)
{
AddBefore(rightSentinel, item);
}

Unfortunately, it seems that the posts in this series are getting longer than expected, so I'll have continue the implementation on the next episode.

P.S.: As I've mentioned in the first post, additional requirements will be specified en route:

• thread safety;

• serialization;

• performance;

• implement the filter, map and reduce algorithms.