Circular linked list – An implementation using C#

In this post, I will explain about creating a circular doubly linked list using C#. .NET framework provides a doubly linked list implementation in System.Collections.Generic.LinkedList<T> class . But this class is not providing the behavior of a circular linked list and it is very tough to extend for supporting circular linked list requirements.

In a normal doubly linked list, each node will have a link to its previous and next nodes. In a circular doubly linked list, tail node’s next node will be head and head node’s previous node will be tail. Here is an image taken from wikipedia which visualizes circular linked list.

Circular linked list

Here is our requirements for the circular linked list

  1. Adding items to the list should be O(1).
  2. Provide similar interface like the standard LinkedList<T> class.
  3. Keep items in a type-safe way.
  4. Avoid using collections like List or array internally for keeping items.
  5. Should provide access to Head and Tail
  6. Option to enumerate all items
  7. Reverse enumeration
  8. Access items with an index.
  9. Maintain collection semantics.

Here is the class diagram.

Circular linked list class diagram

Circular linked list class diagram

Node<T> class

Every problem can be solved by adding another layer of indirection.

Node class is a layer of indirection added to hold the linked list value. It manages the next and previous items and provides an option to get the current value. This class is immutable. Here is Node class looks like,

/// <summary>
/// Represents a node
/// </summary>
/// <typeparam name="T"></typeparam>
[DebuggerDisplay("Value = {Value}")]
public sealed class Node<T>
{
    /// <summary>
    /// Gets the Value
    /// </summary>
    public T Value { get; private set; }

    /// <summary>
    /// Gets next node
    /// </summary>
    public Node<T> Next { get; internal set; }

    /// <summary>
    /// Gets previous node
    /// </summary>
    public Node<T> Previous { get; internal set; }

    /// <summary>
    /// Initializes a new <see cref="Node"/> instance
    /// </summary>
    /// <param name="item">Value to be assigned</param>
    internal Node(T item)
    {
        this.Value = item;
    }
}

CircularLinkedList<T> class

Keeping the requirements in mind, let us start writing the generic CircularLinkedList<T>. Some linked list implementations maintains only a link to the head node and when adding a new item to the list, each node in the list has to be traveled till tail node is found and this gives O(n) complexity for the algorithm.

Maintaining link to head and tail helps us to do insertions with a O(1) complexity. In such cases, list traversal is not required. All we need is to change the pointer in the tail node. Head and tail node are member variables of CircularLinkedList class.

public sealed class CircularLinkedList<T> 
{
    [DebuggerBrowsable(DebuggerBrowsableState.Never)]
    Node head = null;

    [DebuggerBrowsable(DebuggerBrowsableState.Never)]
    Node tail = null;
}

To add an item to the last, we need to create a new node from the supplied item. Set the new node’s next pointer pointing to the list’s head and previous pointing to the tail. Finally, tail will be replaced with the new node. Here is the AddLast() method implementation.

public void AddLast(T item)
{
    // if head is null, then this will be the first item
    if (head == null)
        this.AddFirstItem(item);
    else
    {
        Node<T> newNode = new Node<T>(item);
        tail.Next = newNode;
        newNode.Next = head;
        newNode.Previous = tail;
        tail = newNode;
        head.Previous = tail;
    }
    ++count;
}

void AddFirstItem(T item)
{
    head = new Node<T>(item);
    tail = head;
    head.Next = tail;
    head.Previous = tail;
}

We can easily add another method that will add item to the first position in the list. Implementation looks similar like AddLast(). Unlike AddLast(), head node’s previous pointer will be re-pointed to the new node. The new node’s previous and next pointer will be pointed to tail and head respectively. Finally head will be replaced with the new node.

public void AddFirst(T item)
{
    if (head == null)
        this.AddFirstItem(item);
    else
    {
        Node<T> newNode = new Node<T>(item);
        head.Previous = newNode;
        newNode.Previous = tail;
        newNode.Next = head;
        tail.Next = newNode;
        head = newNode;
    }
    ++count;
}

Finding an item from the list will have a O(n) complexity as it needs to traverse through all items in the list until we get a matching item. Here is a recursive implementation.

public Node<T> Find(T item)
{
    Node<T> node = FindNode(head, item);
    return node;
}

Node<T> FindNode(Node<T> node, T valueToCompare)
{
    Node<T> result = null;
    if (comparer.Equals(node.Value, valueToCompare))
        result = node;
    else if (result == null && node.Next != head)
        result = FindNode(node.Next, valueToCompare);
    return result;
}

Providing an iterator to iterate the items in the list will be useful. Since this is a circular linked list, a reverse iterator also makes sense. yield keyword makes iterator implementations almost trivial.

public IEnumerator<T> GetEnumerator()
{
    Node<T> current = head;
    if (current != null)
    {
        do
        {
            yield return current.Value;
            current = current.Next;
        } while (current != head);
    }
}

public IEnumerator<T> GetReverseEnumerator()
{
    Node<T> current = tail;
    if (current != null)
    {
        do
        {
            yield return current.Value;
            current = current.Previous;
        } while (current != tail);
    }
}

Removing items from list is also just re-pointing the previous and next pointers of the node’s previous.

public bool Remove(T item)
{
    // finding the first occurance of this item
    Node<T> nodeToRemove = this.Find(item);
    if (nodeToRemove != null)
        return this.RemoveNode(nodeToRemove);
    return false;
}

bool RemoveNode(Node<T> nodeToRemove)
{
    Node<T> previous = nodeToRemove.Previous;
    previous.Next = nodeToRemove.Next;
    nodeToRemove.Next.Previous = nodeToRemove.Previous;

    // if this is head, we need to update the head reference
    if (head == nodeToRemove)
        head = nodeToRemove.Next;
    else if (tail == nodeToRemove)
        tail = tail.Previous;

    --count;
    return true;
}

Finally, an indexer is provided so that list items can be accessed using an index. Like Find() method, this also has a O(n) complexity.

public Node<T> this[int index]
{
    get
    {
        if (index >= count || index < 0)
            throw new ArgumentOutOfRangeException("index");
        else
        {
            Node<T> node = this.head;
            for (int i = 0; i < index; i++)
                node = node.Next;
            return node;
        }
    }
}

To get a collection semantics and maintain similar interface like the standard LinkedList, we implement ICollection<T> and IEnumerable<T> interfaces.

public sealed class CircularLinkedList<T> : ICollection<T>, IEnumerable<T>
{
    // code
}

Test harness

Following code shows how this class can be used,

static void Main(string[] args)
{
    CircularLinkedList<int> list = new CircularLinkedList<int>();
    list.AddLast(1);
    list.AddLast(2);
    list.AddLast(3);
    Console.WriteLine("List count = {0}", list.Count);
    Console.WriteLine("Head  = {0}", list.Head.Value);
    Console.WriteLine("Tail  = {0}", list.Tail.Value);
    Console.WriteLine("Head's Previous  = {0}", list.Head.Previous.Value);
    Console.WriteLine("Tail's Next  = {0}", list.Tail.Next.Value);
    Console.WriteLine("************List Items***********");
    foreach (int i in list)
        Console.WriteLine(i);

    Console.WriteLine("************List Items in reverse***********");
    for (IEnumerator<int> r = list.GetReverseEnumerator(); r.MoveNext(); )
        Console.WriteLine(r.Current);

    Console.WriteLine("************Adding a new item at first***********");
    list.AddFirst(0);
    foreach (int i in list)
        Console.WriteLine(i);

    Console.WriteLine("************Adding item before***********");
    list.AddBefore(2,11);
    foreach (int i in list)
        Console.WriteLine(i);

    Console.WriteLine("************Adding item after***********");
    list.AddAfter(3, 4);
    foreach (int i in list)
        Console.WriteLine(i);

    Console.ReadKey();
}
circular linked list output

circular linked list output

Possible expansions

There are good and complex features that can be added to this list. Here are few that will be useful,

  1. Remove duplicate nodes.
  2. Move nodes around.
  3. Sorting.

Probably we will see these features in another post.

Complete source code for CircularLinkedList<T>

Here is the complete source-code for CircularLinkedList<T> (sorry for dumping the code. WordPress doesn’t allow zip files :( ).

/// <summary>
/// Represents a circular doubly linked list.
/// </summary>
/// <typeparam name="T">Specifies the element type of the linked list.</typeparam>
[DebuggerDisplay("Count = {Count}")]
public sealed class CircularLinkedList<T> : ICollection<T>, IEnumerable<T>
{
    [DebuggerBrowsable(DebuggerBrowsableState.Never)]
    Node<T> head = null;

    [DebuggerBrowsable(DebuggerBrowsableState.Never)]
    Node<T> tail = null;

    [DebuggerBrowsable(DebuggerBrowsableState.Never)]
    int count = 0;

    [DebuggerBrowsable(DebuggerBrowsableState.Never)]
    readonly IEqualityComparer<T> comparer;

    /// <summary>
    /// Initializes a new instance of <see cref="CircularLinkedList"/>
    /// </summary>
    public CircularLinkedList()
        : this(null, EqualityComparer<T>.Default)
    {
    }

    /// <summary>
    /// Initializes a new instance of <see cref="CircularLinkedList"/>
    /// </summary>
    /// <param name="collection">Collection of objects that will be added to linked list</param>
    public CircularLinkedList(IEnumerable<T> collection)
        : this(collection, EqualityComparer<T>.Default)
    {
    }

    /// <summary>
    /// Initializes a new instance of <see cref="CircularLinkedList"/>
    /// </summary>
    /// <param name="comparer">Comparer used for item comparison</param>
    /// <exception cref="ArgumentNullException">comparer is null</exception>
    public CircularLinkedList(IEqualityComparer<T> comparer)
        : this(null, comparer)
    {
    }

    /// <summary>
    /// Initializes a new instance of <see cref="CircularLinkedList"/>
    /// </summary>
    /// <param name="collection">Collection of objects that will be added to linked list</param>
    /// <param name="comparer">Comparer used for item comparison</param>
    public CircularLinkedList(IEnumerable<T> collection, IEqualityComparer<T> comparer)
    {
        if (comparer == null)
            throw new ArgumentNullException("comparer");
        this.comparer = comparer;
        if (collection != null)
        {
            foreach (T item in collection)
                this.AddLast(item);
        }
    }

    /// <summary>
    /// Gets Tail node. Returns NULL if no tail node found
    /// </summary>
    public Node<T> Tail { get { return tail; } }

    /// <summary>
    /// Gets the head node. Returns NULL if no node found
    /// </summary>
    public Node<T> Head { get { return head; } }

    /// <summary>
    /// Gets total number of items in the list
    /// </summary>
    public int Count { get { return count; } }

    /// <summary>
    /// Gets the item at the current index
    /// </summary>
    /// <param name="index">Zero-based index</param>
    /// <exception cref="ArgumentOutOfRangeException">index is out of range</exception>
    public Node<T> this[int index]
    {
        get
        {
            if (index >= count || index < 0)
                throw new ArgumentOutOfRangeException("index");
            else
            {
                Node<T> node = this.head;
                for (int i = 0; i < index; i++)
                    node = node.Next;
                return node;
            }
        }
    }

    /// <summary>
    /// Add a new item to the end of the list
    /// </summary>
    /// <param name="item">Item to be added</param>
    public void AddLast(T item)
    {
        // if head is null, then this will be the first item
        if (head == null)
            this.AddFirstItem(item);
        else
        {
            Node<T> newNode = new Node<T>(item);
            tail.Next = newNode;
            newNode.Next = head;
            newNode.Previous = tail;
            tail = newNode;
            head.Previous = tail;
        }
        ++count;
    }

    void AddFirstItem(T item)
    {
        head = new Node<T>(item);
        tail = head;
        head.Next = tail;
        head.Previous = tail;
    }

    /// <summary>
    /// Adds item to the last
    /// </summary>
    /// <param name="item">Item to be added</param>
    public void AddFirst(T item)
    {
        if (head == null)
            this.AddFirstItem(item);
        else
        {
            Node<T> newNode = new Node<T>(item);
            head.Previous = newNode;
            newNode.Previous = tail;
            newNode.Next = head;
            tail.Next = newNode;
            head = newNode;
        }
        ++count;
    }

    /// <summary>
    /// Adds the specified item after the specified existing node in the list.
    /// </summary>
    /// <param name="node">Existing node after which new item will be inserted</param>
    /// <param name="item">New item to be inserted</param>
    /// <exception cref="ArgumentNullException"><paramref name="node"/> is NULL</exception>
    /// <exception cref="InvalidOperationException"><paramref name="node"/> doesn't belongs to list</exception>
    public void AddAfter(Node<T> node, T item)
    {
        if (node == null)
            throw new ArgumentNullException("node");
        // ensuring the supplied node belongs to this list
        Node<T> temp = this.FindNode(head, node.Value);
        if (temp != node)
            throw new InvalidOperationException("Node doesn't belongs to this list");

        Node<T> newNode = new Node<T>(item);
        newNode.Next = node.Next;
        node.Next.Previous = newNode;
        newNode.Previous = node;
        node.Next = newNode;

        // if the node adding is tail node, then repointing tail node
        if (node == tail)
            tail = newNode;
        ++count;
    }

    /// <summary>
    /// Adds the new item after the specified existing item in the list.
    /// </summary>
    /// <param name="existingItem">Existing item after which new item will be added</param>
    /// <param name="newItem">New item to be added to the list</param>
    /// <exception cref="ArgumentException"><paramref name="existingItem"/> doesn't exist in the list</exception>
    public void AddAfter(T existingItem, T newItem)
    {
        // finding a node for the existing item
        Node<T> node = this.Find(existingItem);
        if (node == null)
            throw new ArgumentException("existingItem doesn't exist in the list");
        this.AddAfter(node, newItem);
    }

    /// <summary>
    /// Adds the specified item before the specified existing node in the list.
    /// </summary>
    /// <param name="node">Existing node before which new item will be inserted</param>
    /// <param name="item">New item to be inserted</param>
    /// <exception cref="ArgumentNullException"><paramref name="node"/> is NULL</exception>
    /// <exception cref="InvalidOperationException"><paramref name="node"/> doesn't belongs to list</exception>
    public void AddBefore(Node<T> node, T item)
    {
        if (node == null)
            throw new ArgumentNullException("node");
        // ensuring the supplied node belongs to this list
        Node<T> temp = this.FindNode(head, node.Value);
        if (temp != node)
            throw new InvalidOperationException("Node doesn't belongs to this list");

        Node<T> newNode = new Node<T>(item);
        node.Previous.Next = newNode;
        newNode.Previous = node.Previous;
        newNode.Next = node;
        node.Previous = newNode;

        // if the node adding is head node, then repointing head node
        if (node == head)
            head = newNode;
        ++count;
    }

    /// <summary>
    /// Adds the new item before the specified existing item in the list.
    /// </summary>
    /// <param name="existingItem">Existing item before which new item will be added</param>
    /// <param name="newItem">New item to be added to the list</param>
    /// <exception cref="ArgumentException"><paramref name="existingItem"/> doesn't exist in the list</exception>
    public void AddBefore(T existingItem, T newItem)
    {
        // finding a node for the existing item
        Node<T> node = this.Find(existingItem);
        if (node == null)
            throw new ArgumentException("existingItem doesn't exist in the list");
        this.AddBefore(node, newItem);
    }

    /// <summary>
    /// Finds the supplied item and returns a node which contains item. Returns NULL if item not found
    /// </summary>
    /// <param name="item">Item to search</param>
    /// <returns><see cref="Node&lt;T&gt;"/> instance or NULL</returns>
    public Node<T> Find(T item)
    {
        Node<T> node = FindNode(head, item);
        return node;
    }

    /// <summary>
    /// Removes the first occurance of the supplied item
    /// </summary>
    /// <param name="item">Item to be removed</param>
    /// <returns>TRUE if removed, else FALSE</returns>
    public bool Remove(T item)
    {
        // finding the first occurance of this item
        Node<T> nodeToRemove = this.Find(item);
        if (nodeToRemove != null)
            return this.RemoveNode(nodeToRemove);
        return false;
    }

    bool RemoveNode(Node<T> nodeToRemove)
    {
        Node<T> previous = nodeToRemove.Previous;
        previous.Next = nodeToRemove.Next;
        nodeToRemove.Next.Previous = nodeToRemove.Previous;

        // if this is head, we need to update the head reference
        if (head == nodeToRemove)
            head = nodeToRemove.Next;
        else if (tail == nodeToRemove)
            tail = tail.Previous;

        --count;
        return true;
    }

    /// <summary>
    /// Removes all occurances of the supplied item
    /// </summary>
    /// <param name="item">Item to be removed</param>
    public void RemoveAll(T item)
    {
        bool removed = false;
        do
        {
            removed = this.Remove(item);
        } while (removed);
    }

    /// <summary>
    /// Clears the list
    /// </summary>
    public void Clear()
    {
        head = null;
        tail = null;
        count = 0;
    }

    /// <summary>
    /// Removes head
    /// </summary>
    /// <returns>TRUE if successfully removed, else FALSE</returns>
    public bool RemoveHead()
    {
        return this.RemoveNode(head);
    }

    /// <summary>
    /// Removes tail
    /// </summary>
    /// <returns>TRUE if successfully removed, else FALSE</returns>
    public bool RemoveTail()
    {
        return this.RemoveNode(tail);
    }

    Node<T> FindNode(Node<T> node, T valueToCompare)
    {
        Node<T> result = null;
        if (comparer.Equals(node.Value, valueToCompare))
            result = node;
        else if (result == null && node.Next != head)
            result = FindNode(node.Next, valueToCompare);
        return result;
    }

    /// <summary>
    /// Gets a forward enumerator
    /// </summary>
    /// <returns></returns>
    public IEnumerator<T> GetEnumerator()
    {
        Node<T> current = head;
        if (current != null)
        {
            do
            {
                yield return current.Value;
                current = current.Next;
            } while (current != head);
        }
    }

    /// <summary>
    /// Gets a reverse enumerator
    /// </summary>
    /// <returns></returns>
    public IEnumerator<T> GetReverseEnumerator()
    {
        Node<T> current = tail;
        if (current != null)
        {
            do
            {
                yield return current.Value;
                current = current.Previous;
            } while (current != tail);
        }
    }

    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }

    /// <summary>
    /// Determines whether a value is in the list.
    /// </summary>
    /// <param name="item">Item to check</param>
    /// <returns>TRUE if item exist, else FALSE</returns>
    public bool Contains(T item)
    {
        return Find(item) != null;
    }

    public void CopyTo(T[] array, int arrayIndex)
    {
        if (array == null)
            throw new ArgumentNullException("array");
        if (arrayIndex < 0 || arrayIndex > array.Length)
            throw new ArgumentOutOfRangeException("arrayIndex");

        Node<T> node = this.head;
        do
        {
            array[arrayIndex++] = node.Value;
            node = node.Next;
        } while (node != head);
    }

    [DebuggerBrowsable(DebuggerBrowsableState.Never)]
    bool ICollection<T>.IsReadOnly
    {
        get { return false; }
    }

    void ICollection<T>.Add(T item)
    {
        this.AddLast(item);
    }
}

Happy programming!

About these ads

7 thoughts on “Circular linked list – An implementation using C#

  1. Thanks a lot. Very good code and I needed very fews modifications to fit with my code style. An hint: Node can have a List property pointing to the circular list it come from, like LinkedListNode. Oh, to be more consistent with .NET naming, Head and Tail properties could have been First and Last. I kept Head and Tail because, in fact, I prefer them too :)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s