Custom Doubly Linked List in C#

Of course you can use the generic LinkedList(T) class instead of this custom implementation for a specific project of mine and I thought I would like to blog it for future references.

The custom IDoubleLinkedNode<T> Interface:

/// <summary>
/// Node interface to support the DoubleLinkedList class
/// </summary>
/// <typeparam name="T"></typeparam>
public interface IDoubleLinkedNode<T>
    : IComparable<T>, IEquatable<T>
{
    T Next { get; set; }
    T Previous { get; set; }
}

The custom DoubleLinkedList<T> class:

/// <summary>
/// Custom doubly linked list.
/// This is created to replace the Generic LinkedList(T) so that
/// the target object implements the node interface
/// (Next, Previous etc...) IDoubleLinkedNode
/// instead of being wrapped in a LinkedListNode object.
/// This also supports a custom implementation of Merged Sort 
/// Algorithm for sorting the list
/// which is unavailable in the Generic LinkedList(T), 
/// in that case, will have to be extended.
/// </summary>
/// <typeparam name="T">IDoubleLinkedNode type</typeparam>
public class DoubleLinkedList<T> : ICollection<T> 
   where T : IDoubleLinkedNode<T>
{
    // Holds the first item.
    private T head;
    // Holds the last item to allow us add fast.
    private T tail;
    private int count;
 
    #region Sort
    /// <summary>
    /// Sort the linked list using merge sort based 
    /// on the IComparable implementation
    /// </summary>
    public void Sort()
    {
        head = Merge_Sort(head);
    }
 
    #region Private Merge Sort
    /// <summary>
    /// Initiate a merge sort on the doublylinkedlist node item
    /// Based on the IComparable ordering rule
    /// </summary>
    /// <param name="first"></param>
    /// <returns></returns>
    private T Merge_Sort(T first)
    {
        // If node is empty or single, then we don't need to sort
        if (first == null || first.Next == null)
            return first;
 
        // Get the next item
        T second = Split(first);
 
        first = Merge_Sort(first);
        second = Merge_Sort(second);
 
        return Merge(first, second);
    }
 
    /// <summary>
    /// Split the Linked Node into 2 parts, mainly
    /// alternating through the pointers into 2 seperate
    /// link nodes.  Eg. 1 -> 2 -> 3 -> 4 -> 5 will be splitted
    /// into 1 -> 3 -> 5 and 2 -> 4 respectively
    /// </summary>
    /// <param name="item"></param>
    /// <returns></returns>
    private T Split(T item)
    {
        // If it is the last item, we will return nothing
        if (item == null || item.Next == null)
            return default(T);
 
        // Assign alternate items to the second item
        T second = item.Next;
 
        // Assign alternate items pointers to the current item
        item.Next = second.Next;
 
        // Continue assigning the alternate pointers
        second.Next = Split(second.Next);
 
        // Return the second concatenated list
        return second;
    }
 
    /// <summary>
    /// Perform merge of the first and second item based on the 
    /// </summary>
    /// <param name="first"></param>
    /// <param name="second"></param>
    /// <returns></returns>
    private T Merge(T first, T second)
    {
        if (first == null)
            return second;
 
        if (second == null)
            return first;
 
        // If both are not null, we will run the comparer
        // If first is less than second
        if (first.CompareTo(second) < 0)
        {
            first.Next = Merge(first.Next, second);
            first.Next.Previous = first;
            first.Previous = default(T);
 
            return first;
        }
        else
        {
            second.Next = Merge(first, second.Next);
            second.Next.Previous = second;
            second.Previous = default(T);
 
            return second;
        }
    }
    #endregion
    #endregion
 
    #region [] accessor
    /// <summary>
    /// This is for convenience
    /// </summary>
    /// <param name="index"></param>
    /// <returns></returns>
    public T this[int index]
    {
        get
        {
            // Throw an exception if the index is not valid.
            if (index < 0)
                throw new ArgumentOutOfRangeException();
            // Get the first item.
            var item = head;
 
            // Loop until we reach the item we want.
            for (int i = 0; i < index; i++)
            {
                // If there is no next item throw an exception.
                if (item.Next == null)
                    throw new ArgumentOutOfRangeException();
 
                // Go to the next item.
                item = item.Next;
            }
 
            // Return the value of the item.
            return item;
        }
    }
    #endregion
 
    #region ICollection<T> Members
 
    public void Add(T value)
    {
        if (value == null)
            throw new ArgumentNullException("value");
 
        var item = value;
 
        // Check if we need to update the first and last
        // fields.
        if (head == null)
            head = item;
        if (tail != null)
        {
            tail.Next = item;
            item.Previous = tail;
        }
 
        tail = item;
        count++;
    }
 
    public void Clear()
    {
        head = default(T);
        tail = default(T);
        count = 0;
    }
 
    public bool Contains(T value)
    {
        var item = head;
 
        // Loop until we reach the end of the list.
        while (item != null)
        {
            // Check if we match.
            if (item.Equals(value))
                return true;
 
            // Otherwise go on.
            item = item.Next;
        }
        return false;
    }
 
    public void CopyTo(T[] array, int arrayIndex)
    {
        throw new NotImplementedException();
    }
 
    public int Count
    {
        get { return count; }
    }
 
    public bool IsReadOnly
    {
        get { return false; }
    }
 
    public bool Remove(T value)
    {
        if (head == null)
            return false;
 
        // Get the first item.
        var item = head;
 
        // Check if the first item matches.
        if (item.Equals(value))
        {
            // If so move the next item to the first one.
            head = item.Next;
            head.Previous = default(T);
            count--;
 
            // If first is null the list has been cleared.
            // Last is also to set null.
            if (head == null)
                tail = default(T);
 
            return true;
        }
        else
        {
            // Loop until we reach the end.
            while (item.Next != null)
            {
                // Check the values.
                if (item.Next.Equals(value))
                {
                    // If we match store the one after the next
                    // as the next one.
                    item.Next = item.Next.Next;
                    // If this is not the last item, 
                    // then we set the previous value
                    if (item.Next != null)
                        item.Next.Previous = item;
                    count--;
 
                    // If the next item is null, set this item
                    // as the last one.
                    if (item.Next == null)
                        tail = item;
                    return true;
                }
 
                // Move to the next item.
                item = item.Next;
            }
        }
 
        return false;
    }
 
    #endregion
 
    #region IEnumerable<T> Members
 
    public IEnumerator<T> GetEnumerator()
    {
        // Get the first item.
        var item = head;
 
        // Loop until we reach the end.
        while (item != null)
        {
            // Return the item.
            yield return item;
 
            // Move to the next one.
            item = item.Next;
        }
    }
 
    #endregion
 
    #region IEnumerable Members
 
    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
 
    #endregion
}