Fluent ChainLinkList with a Custom Linked List

• Download source - 11.68 KB

Introduction

In software engineering, a Fluent Interface, first coined by Eric Evans and Martin Fowler, is a way of implementing an object oriented API in a way that aims to provide for more readable code. In other words, a developer would write the code in such a way that it conveys the purpose of the code in its syntax itself.  

I've decided to demonstrate this paradigm using a custom linked list which I call a ChainLink. The ChainLink object is actually a full implementation of a linked list data structure with added functionality like BubbleSort and Reverse. I could have used the default LinkList data structure provided by Microsoft, however I thought it would be more fun to create my own.  Plus the LinkList provided by Microsoft does not have BubbleSort or Reverse functions.

Using the Code

Here we go. Let’s get to the code! Here is the code for the generic ChainLinkList data structure:

 [Serializable]
 public class ChainLinkList<T> : ICloneable, IEnumerable<T> where T : IComparable<T>
 {
    #region Public Properties
  
    public int Count
    {
        get;
        private set;
    }
  
    public ChainListNode<T> Head
    {
        get;
        private set;
    }
  
    public ChainListNode<T> Tail
    {
        get;
        private set;
    }
  
    #endregion
  
    #region Enumerators
  
    public IEnumerator<T> GetEnumerator()
    {
        ChainListNode<T> current = Head;
  
        while (current != null)
        {
            yield return current.Value;
            current = current.Next;
        }
    }
  
    IEnumerator IEnumerable.GetEnumerator()
    {
        return this.GetEnumerator();
    }
  
    #endregion
  
    public ChainListNode<T> this[int index]
    {
        get
        {
            ChainListNode<T> current = Head;
  
            if (index > Count - 1)
            {
                throw new IndexOutOfRangeException();
            }
  
            for (int i = 0; i < index; i++)
            {
                current = current.Next;
            }
  
            return current;
        }
    }
  
    public ChainListNode<T> AddItem(ChainListNode<T> node)
    {
        if (node == null)
        {
            throw new ArgumentNullException();
        }
  
        node.Container = this;
  
        if (Head == null)
        {
            Head = node;
            Tail = node;
        }
        else
        {
            Tail.Next = node;
            Tail = node;
        }
  
        Count++;
  
        return node;
    }
  
    public ChainListNode<T> AddItem(T value)
    {
        ChainListNode<T> node = new ChainListNode<T>(value);
  
        node.Container = this;
  
        if (Head == null)
        {
            Head = node;
            Tail = node;
        }
        else
        {
            Tail.Next = node;
            Tail = node;
        }
  
        Count++;
  
        return node;
    }
  
    public ChainListNode<T> Find(T value)
    {
        var current = Head;
  
        while (current != null && current.Value.CompareTo(value) != 0)
        {
            current = current.Next;
        }
  
        return current;
    }
  
    public void AddItemAtHead(ChainListNode<T> node)
    {
        if (node == null)
        {
            throw new ArgumentNullException();
        }
  
        node.Container = this;
  
        if (Head == null)
        {
            Head = node;
            Tail = node;
        }
        else
        {
            node.Next = Head;
            Head = node;
        }
  
        Count++;
    }
  
    public void HookOnBack(ChainLinkList<T> toAdd)
    {
        if (toAdd == null)
        {
            throw new ArgumentNullException();
        }
  
        Count = toAdd.Count;
  
        if (Head == null)
        {
            Head = toAdd.Head;
            Tail = toAdd.Tail;
        }
        else
        {
            Tail.Next = toAdd.Head;
            Tail = toAdd.Tail;
        }
    }
  
    public void HookInFront(ChainLinkList<T> toAdd)
    {
        if (toAdd == null)
        {
            throw new ArgumentNullException();
        }
  
        if (Head == null)
        {
            HookOnBack(toAdd);
        }
        else
        {
            ChainListNode<T> temp = Head;
  
            Head = toAdd.Head;
            toAdd.Tail.Next = temp;
  
            Count = toAdd.Count;
        }
    }
  
    // <summary>
    // In-place Bubble Sort: Performance O(n2).  Not bad for a small list.
    // </summary>
    public void BubbleSort()
    {
        ChainListNode<T> first = Head;
  
        while (first != null)
        {
            ChainListNode<T> second = first.Next;
  
            while (second != null)
            {
                if (first.Value.CompareTo(second.Value) > 0)
                {
                    T temp = first.Value;
  
                    first.Value = second.Value;
                    second.Value = temp;
                }
  
                second = second.Next;
            }
  
            first = first.Next;
        }
    }
  
    public void Reverse()
    {
        ChainListNode<T> r = null;
        ChainListNode<T> y = Head;
  
        Head = Tail;
  
        while (y != null)
        {
            ChainListNode<T> temp = y.Next;
            y.Next = r;
            r = y;
            y = temp;
        }
  
        Tail = y;
    }
  
    public ChainListNode<T> AddAfter(ChainListNode<T> node, ChainListNode<T> toAdd)
    {
        ChainListNode<T> current = Head;
  
        while (current != null)
        {
            if (current == node)
            {
                toAdd.Next = current.Next;
                current.Next = toAdd;
                toAdd.Container = this;
  
                if (toAdd.Next == null)
                {
                    Tail = toAdd;
                }
  
                Count++;
                return toAdd;
            }
  
            current = current.Next;
        }
  
        return null;
    }
   
   public bool Contains(T value)
    {
        ChainListNode<T> current = Head;
  
        while (current != null)
        {
            if (current.Value.Equals(value))
            {
                return true;
            }
  
            current = current.Next;
        }

        return false;
    }

    public void Clear()
    {
        Head = null;
        Tail = null;

        Count = 0;
    }

    #region ICloneable

    public object Clone()
    {
        ChainLinkList<T> copy = new ChainLinkList<T>();
        copy.HookOnBack(this);

        return copy;
    }

    #endregion
}

And here is the code for the ChainListNode<T> class:

[Serializable]
 public class ChainListNode<T> : IEnumerable<T> where T : IComparable<T>
 {
   public ChainListNode()
   {
       Container = new ChainLinkList<T>();
       Container.AddItem(this);
   }

   public ChainLinkList<T> Container
   {
       get;
       internal set;
   }

   public ChainListNode(T value)
   {
       this.Value = value;

       Container = new ChainLinkList<T>();
       Container.AddItem(this);
   }

   public ChainListNode<T> Next
   {
       get;
       set;
   }

   public T Value
   {
       get;
       set;
   }

   public ChainListNode<T> AddAfter(ChainListNode<T> toAdd)
   {
       return Container.AddAfter(this, toAdd);
   }

   public ChainListNode<T> AddAfter(T toAdd)
   {
       return Container.AddAfter(this, new ChainListNode<T>(toAdd));
   }

   public override string ToString()
   {
       return Value.ToString();
   }

   #region Enumerators

   public IEnumerator<T> GetEnumerator()
   {
       return Container.GetEnumerator();
   }

   IEnumerator IEnumerable.GetEnumerator()
   {
       return this.GetEnumerator();
   }

   #endregion
}

Fluent Interface Programming

Notice that the ChainListNode has a reference to its container (which is a ChainLinkList). We'll see what this means soon!

Now for the ‘fluent’ part of this article. Suppose I want to create a simple linked list with one item. I would use the following code:

ChainLinkList<int> chainLink = new ChainLinkList<int>();
ChainListNode<int> one = new ChainListNode<int>(1);
chainLink.AddItem(one);

What if I wanted to add more nodes? Should I always need a reference to the chainlink object in order to add more nodes? Since this is a chain, can't I just add a node to the last link on the chain? Sure I can! Examine the following code snippet:

//Chain Linking
one.AddAfter(2).AddAfter(3).AddAfter(4).AddAfter(5).AddAfter(6);
chainLink.AddItem(7);
chainLink.AddItem(3);
chainLink.AddItem(4).AddAfter(20);

When you iterate over the chain, your output will be:

1 2 3 4 5 6 7 3 4 20 

And the code is written in such a way that I can see the chain of nodes directly in the code. This is one of the main points of fluent interfaces.

Do I even need an initial ChainLinkList object to create a chain you ask? No, of course not! Don't be ridiculous! Please examine the following code:

ChainLinkList<int> chainLink1 =
   new ChainListNode<int>(4).AddAfter(5).AddAfter(6).Container;
ChainLinkList<int> chainLink2 =
   new ChainListNode<int>(1).AddAfter(2).AddAfter(3).Container;

Now for the fun part. You're probably wondering what is he up to now! And you will not be disappointed. Please examine the following code:

foreach (int value in new ChainListNode<int>(1).AddAfter(2).AddAfter(3))
{
    Console.Write(value + " ");
}

And there you have it. A ChainLinkList design with the ‘fluent interface’ paradigm. You can also reverse the chain and sort the chain using BubbleSort.

In the sample code, there is a QuickSort method. I implemented it just for fun. You should not use the QuickSort method. QuickSort works best with arrays. The only reason I implemented it was to have fun with the chain, nothing else. Its performance is much worse than the general performance for QuickSort. You are warned.

Please tell me what you think.

History

• 5^th March, 2010: Initial post