luni, 3 decembrie 2007

Implementing a Double Linked List in C# - part III

Welcome to the third part of the series on implementing a double linked list. It is now time to finalize the basic functions of the list, as well as some extra helper functions. The latter have the purpose of easing the use of the list for its users.

In this episode we'll cover the following:

  • Delegate some of the concerns of the list to its nodes;
  • Implement the IEnumerable interface, and the associate iterator;
  • Add a bit of "closure" to our list.
  • Removing items from the list


The main difference between our implementation of the doubly linked list and the one provided by the .Net framework, is in the accessibility of data. While the .Net framework version exposes the data through the nodes containing it, we, on the other hand, expose it directly. This might be a shortcoming in terms of flexibility for navigating locally in the list. But the benefits come in form of structural integrity of the list, while permitting low level alteration of the structure of the list, and a better user experience in terms of accessing the data. What I mean by keeping control over the structural integrity of the list is that the consumer of the list can't make modifications that could break the chain of references or desynchronize the count of nodes, but the list can make modifications at that level internally. Of course these low level operations are also available to the inheritors of the list.

Revisiting the Node Class

Until now we've managed to ignore the Node class, but she "feels" that and tells us: "Listen, I'm pretty good at holding hands (references) with my left and right neighbors, so let me add new neighbor nodes as well as remove myself from the list". So we delegate to the Node class the concern of "keeping up references" during the operation of the list.

Adding a neighbor to the left of a node, means that we have to change:

  • the reference of the original left node to its right node, to the new node;
  • the reference to the original left node, to the new node;
  • the reference of the new node's left node, to the original left node;
  • the reference of the new node's right node to the current node.

    public Node<T> EnchainBefore(T item)


         Node<T> node = new Node<T>();

         node.Data = item;

         node.Previous = Previous;

         node.Next = this;

         Previous.Next = node;

         Previous = node;

         return node;


Removing the current node means we have to make its two neighbors reference each other:

public void RemoveFromChain()


     Previous.Next = Next;

     Next.Previous = Previous;


Implementing the IEnumberable Interface

The interesting part is not implementing the IEnumerable interface, but the IEnumerator. The twist is that the enumerator must "enumerate" through the list in two directions: forward as well as backward. Essentially the iterator will follow the chain of references starting with the left sentinel and ending with the right sentinel for forward enumerating. The iterator will go the other way around for backward iteration. This logic is embodied into the MoveNext method:

public bool MoveNext()


     if (forwardDirection)


          current = current.Next;

          return current != rightSentinel;


     current = current.Previous;

     return current != leftSentinel;


The rest of the code is just plumbing and we shall not go over it.

A Little Bit of Closure

We need a way of applying some function to the list of nodes. The process must be controled by the function, meaning that the function can dictate when to stop the process.

Introducing the predicate. The predicate is a delegate with one generic parameter, which returns a boolean value. We could have built our own delegate, and in one way it would have been better, because we are abusing the purpose of the predicate as intended by its creators. But why reinvent the wheel when it's already there.

So let's define the Apply method, which applies a predicate received as parameter to each node, as long as the predicate evaluates to (returns) true and there are still items in the list:

Public virtual void Apply(Predicate<T> predicate)


     Node<T> node = leftSentinel.Next;

     while (node != rightSentinel && predicate(node.Data))

          node = node.Next;


Removing items from the list can be easily implemented by using the Apply method. What I intend to do is iterate through the list as long as the current node does not contain the value we are trying to remove, and when we find it we'll ask the containing node to remove itself from the list and stop the iteration:

Apply(delegate(Node<T> node)


     if (item.Equals(node.Data))




          return false;


     return true;


Another method that coud use the help of the predicate is the Add method. This way we could make the items beig added to the list obey certain rules:

public virtual void Add(T item, Predicate<T> check)


     Node<T> node = leftSentinel.Next;

     while (node != rightSentinel && !check(node.Data))

          node = node.Next;

     AddBefore(node, item);


Now we have to tools to implement an ordered list:

public class SortedList : DoubleLinkedList<int>


     public override void Add(int item)


          Add(item, delegate (int data)


               return data < item;




That's all for this episode. Remember you can find the source code here.

Stumble Upon Toolbar

sâmbătă, 1 decembrie 2007

Creating a Double Linked List in C# - Intermezzo

Day by day I am amazed by Google's other services, besides web searching. One of the useful collaboration services offered by Google is Google Code. It is a free service for project hosting, which provides SVN version control.

You can now find the source code for the double linked list series at this location.
Stumble Upon Toolbar

joi, 29 noiembrie 2007

Headache Installing Visual Studio 2008

Last night I've tried to install Visual Studio ‚Orcas' RTM, but the setup kept crashing at the fisrt step of the installation (installation of the 3.5 framework). Digging into the setup log files I've traced the problem to the installation of the 3.0 framework SP1. After some trials and misses (I've even uninstalled the MacAfee antivirus), I've downloaded the framework 3.5 setup redistributable (the full install package). The setup went flawlessly, and after it ended I was able to install the new Visual Studio.

I hope this information will help someone in need.

Stumble Upon Toolbar

miercuri, 28 noiembrie 2007

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
newNode.Next = node;
newNode.Previous = newNode.Previous;
newNode.Data = item;
node.Previous.Next = newNode;
node.Previous = newNode;

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;

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.

Stumble Upon Toolbar

marți, 27 noiembrie 2007

First post: Implementing a Double Linked List in C# - part I

Hello World!

The first blog post is dedicated to a basic, but important data structure: the double linked list. It is intended to be an academic exercise, rather than a practical one.

Acknowledgement: I'm not a native English speaker, and despite Word's spell & grammar checker, please indulge my language faults. Still, constructive criticism is appreciated!

I've separated the plan of this project into 3 parts: the description of the domain of the problem at hand, definition of the requirements and, finally, the design. The article will be separated into two parts, leaving the design into the second part. A third, bonus, part might be included into the series.

First let's describe the DOMAIN of the problem

Wikipedia comes to our help with a definition of a double linked list (approx.): the (double) linked list is a data structure. It consists of a sequence of nodes, each containing arbitrary data fields and two references, to the next and previous nodes.

Some implementations provide two special nodes, called sentinels. These nodes are placed at the beginning and end of the list, and do not contain any data. Their purpose is to provide a uniform way of treating the insertion and removal of standard nodes.

The main purpose of the linked lists is to be a base for other data structures, like stacks and queues. The main benefit over conventional arrays is that they support the insertion and removal of elements, without creating a new instance of the structure. The advantage of the double linked list over other linked lists is that they can be traversed backwards as well as forwards.

In the .Net world, support for sequential data structures, besides arrays, is provided through collections. Collections are defined by a set of interfaces, which provide a uniform set of patterns for manipulating collections, and the concrete implementations of several types of collections: lists, dictionaries, hash tables and so on.

Another feature of the .Net framework, available from the v2.0 version, is generics. They enable the user to generalize the definition of types, by leaving a part of the implementation of the type to be provided when the type will be consumed. This will enable the list to contain any type of data, as long as it is of the same type (of course, a collection of object objects will hold any data, but that's not the point).

REQUIREMENTS prescription

The requirements for our double linked list represent what is expected from it. They fall into two categories, what is expected from a double linked list, and what is expected from a collection. The two categories are overlapping. The list of requirements is by no means exhaustive, and might be improved in the course of the implementation.

A double linked list should:
  • Provide storage for data into nodes.
  • Permit the insertion of new node(s) when the list is empty as well as when the list has existing items.
  • Permit the removal of a specified item.
  • Return the number of existing nodes.
  • Return a specific node.
  • Provide a consistent mechanism for dealing with errors.
  • Provide the next and previous nodes for a given node.

A collection should:

  • Provide for data into items.
  • Permit the addition of new item(s).
  • Permit the removal of item(s).
  • Iterate over its values.
  • Permit the retrieval of a specified item.
  • Permit the alteration of the order of its item (ex. Sorting).

This ends the first two parts of our plan. Next time we will see how we can get from a list o requirements to an usable artifact.

Stumble Upon Toolbar