Doubly-Linked List Implementation

• Download source files - 51 Kb

Introduction

I was writing some code in C# the other day and I realized I needed a linked list to make something I was doing easier. I wanted a list that would collapse around a removed object, and that was not be backed by an array. I naturally went to the .NET Framework and the System.Collections namespace to look at the .NET linked list that I just assumed would be there. To my surprise there was not one. I could not believe it. I then searched MSDN looking for one to see if it was placed in another namespace. It was not; it just did not exist in the .NET Framework. Finally, I searched the internet and still could not find one implemented in C#.

That inspired me to write my own linked list. Not just a standard linked list, but a doubly-linked list. A list where each element has a reference to the next element and the previous element. A standard linked list would just have a reference to the next element. With doubly-linked list, the list can easily be traversed forward and backwards and delete an element in constant time.

Break It Down

My doubly-linked list, which we will call just LinkedList from now on, starts by implementing the following interfaces.

• IList (which is a ICollection and IEnumerable)
• ICloneable

Then under this public facade we have a lot of very important private members that do the bulk of the work.

• class Node
• class LinkedListEnumerator

• FindNodeAt(int)
• Remove(Node)

• Node headerNode
• int modifications

Some Details

The Node class is a very simple class, yet it is a very key part of the LinkedList. It wraps an object and keeps a reference to the next node and the previous node. The Node class is hidden from the user of the LinkedList, so that it works like any other collection in the .NET Framework.

The headerNode member variable of type Node has an important role as the starting point in the list. This Node contains a null reference and can never be accessed by the user or removed. It is not considered in the count of total objects in the list. This Node is important in a doubly-linked list, as it is technically the beginning and ending of the list.

The FindNodeAt(int index) method contains the search algorithm for accessing the list by index. At the moment it divides the list in half and searches from the beginning or the end depending on which is closest to the requested index. This method is used by all the other methods directly or indirectly that require access to an object by index. This helps to make the searches much faster. There is potential for improvement for large lists by further dividing before searching, however, at a cost for small lists. Right now this seems like the best compromise for most usages. The current algorithm used to find a Node is below.

    Node node = headerNode;

    if (index < (count / 2))
    {
      for (int i = 0; i <= index; i++)
        node = node.NextNode;
    }
    else
    {
      for (int i = count; i > index; i--)
        node = node.PreviousNode;
    }

The Remove(Node value) is important because it adjusts the remaining Nodes by compressing the list. This is done simply by taking the Node that needs to be removed and changing its previous Node's next Node reference to its next Node, and changing its next Node's previous Node reference to its previous Node then leaving itself for the garbage collector. This may be easier to understand by viewing the algorithm used in this method below.

    if (value != headerNode)
    {
      value.PreviousNode.NextNode = value.NextNode;
      value.NextNode.PreviousNode = value.PreviousNode;

      count--;
      modifications++;
    }

The modifications member variable of type int is incremented every time there is a modification to the structure of the list. The variable is then used by the LinkedListEnumerator to guard against concurrent modifications to the list while enumerating.

The LinkedList class is not thread safe by design. If thread safety is required, the class can be extended to provide it.

The LinkedListEnumerator class is fail-fast. This means it uses the modifications variable it is passed when it is created to know if any modifications have been made while enumerating. The check is made in its MoveNext() method before it increments to the next value. If a modification has been detected then it will throw a SystemException that can then be caught and handled accordingly. Below is the source for LinkedListEnumerator class.

private class LinkedListEnumerator : IEnumerator
{
  private LinkedList  linkedList;
  private int         validModificationCount;
  private Node        currentNode;
  
  public LinkedListEnumerator(LinkedList linkedList)
  {
    this.linkedList         = linkedList;
    validModificationCount  = linkedList.modifications;
    currentNode             = linkedList.headerNode;
  }
  
  public object Current
  {
    get
    {
      return currentNode.CurrentNode;
    }
  }
  
  public void Reset()
  {
    currentNode = linkedList.headerNode;
  }

  public bool MoveNext()
  {
    bool moveSuccessful = false;

    if (validModificationCount != linkedList.modifications)
      throw new SystemException(
          "A concurrent modification occured to the LinkedList " + 
          "while accessing it through it's enumerator.");

    currentNode = currentNode.NextNode;

    if (currentNode != linkedList.headerNode)
      moveSuccessful = true;

    return moveSuccessful;
  }
}

The LinkedList(ICollection) constructor and the AddAll(ICollection) and InsertAll(int, ICollection) are there for convenience to the user of the list. This constructor calls AddAll(ICollection) which in turn calls InsertAll(int, ICollection). Below is the the code for this method.

public virtual void InsertAll(int index, ICollection collection)
{
  if (collection != null)
  {
    if (0 < collection.Count)
    {
      modifications++;

      Node startingNode = (index == count ? 
                  headerNode : FindNodeAt(index));
      Node previousNode = startingNode.PreviousNode;

      foreach (object obj in collection)
      {
        Node node             = new Node(obj, 
                  startingNode, previousNode);
        previousNode.NextNode = node;
        previousNode          = node;
      }

      startingNode.PreviousNode = previousNode;

      count += collection.Count;            
    }
    else
      throw new ArgumentOutOfRangeException("index", 
                   index, "less than zero");
  }
  else
    throw new ArgumentNullException("collection");
}

The LinkedList provides two methods for cloning. The first is the ICloneable interface Clone() method. It provides a shallow copy of the LinkedList. The second is Clone(bool attemptDeepCopy). It attempts to make a deep copy of the list if passed true, if false it will make a shallow copy. If an object in the list is not an ICloneable then it will throw a SystemException. The returned attempted deep copied list is not guaranteed to be a true deep copy. It defers the cloning to the objects own Clone() method. Here is the source for these two methods.

public virtual object Clone()
{
  LinkedList listClone = new LinkedList();

  for (Node node = headerNode.NextNode; node != headerNode; 
          node = node.NextNode)
    listClone.Add(node.CurrentNode);

  return listClone;
}

public virtual LinkedList Clone(bool attemptDeepCopy)
{
  LinkedList listClone;

  if (attemptDeepCopy)
  {
    listClone = new LinkedList();

    object currentObject;

    for (Node node = headerNode.NextNode; node != headerNode; 
           node = node.NextNode)
    {
      currentObject = node.CurrentNode;

      if (currentObject == null)
        listClone.Add(null);
      else if (currentObject is ICloneable)
        listClone.Add(((ICloneable)currentObject).Clone());
      else
        throw new SystemException("The object of type [" + 
                     currentObject.GetType() + 
                     "] in the list is not an ICloneable, cannot attempt " + 
                     "a deep copy.");
    } 
  }
  else
    listClone = (LinkedList)this.Clone();

  return listClone;
}

Conclusion

I believe this is a great class to learn how to implement your own custom collection. It is also very useful as it is, and ready to be included in your next project. The rest of the class is fairly straight-forward for a list collection. The class is fairly well commented using XML comment tags. Experienced and intermediate developers should have no trouble following the class.

This LinkedList is part of a set of .NET utilities I am developing, and have released as an open source project under the GNU General Public License (GPL). My complete project can be found at Source Forge.