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
}
