Home C++ .NET Web Links About Create

Implementing a C# Collection

While I have previously posted an implementation of a C# doubly-linked list, I found that class to be a little too lengthy to serve as an effective tutorial for how to implement a C# collection. When I set out to create a simpler class to use in this article I decided to make a singly-linked list instead.

What I ended up with was only slightly simpler, since I wanted the collection to be complete. This class should still be simple enough to follow for intermediate-level developers.

.NET Collections

Collection classes in the .NET Framework typically implement the ICollection interface. This interface specifies methods for getting the size of a collection, creating enumerators on a collection, and managing synchronized access to a collection.

The ICollection interface is derived from IEnumerable, so by properly implementing the GetEnumerator method a collection can be used with the C# foreach iteration statement.

The Singly-Linked List

The singly-linked list collection in this article implements all the ICollection methods, plus four additional methods: AddFront, RemoveFront, AddBack, and RemoveBack. It contains two internal classes that implement the list node and the linked-list enumerator. To show how the class works and how it implements the ICollection interface, I've broken the class into small chunks and explained a few lines at a time. Most of the comments have been removed since the code is being explained in detail.

If you'd like to get the whole class as a text file, you can download it here.

The Code

This implementation provides support for serialization, comparison, and cloning, but it does not address thread safety. It implements only the most basic features of a linked list. I'll leave a more complete implementation for another day, or perhaps as an exercise for the reader.

The Linked List Implementation

The class begins with the implementation of the linked list, and the definition of the public interface. 

using System;
using System.Collections;

[Serializable]
public class SinglyLinkedList : ICollection, ICloneable
{

The [Serializable] attribute indicates that instances of the class may be persisted, or written to some form of external storage, and then re-created from the persistent form. The class itself is declared as implementing the ICollection and ICloneable interfaces.

Because the SinglyLinkedList class derives from the ICollection and ICloneable interfaces, it guarantees that it will implement all the methods and properties specified by these interfaces. 

    private Node head = new Node();

    [NonSerialized] private bool isEnumerating = false;

    private int count = 0;

An empty head node is created for each new instance of the class. This node will always contain a reference to the first node in the list, or to itself when the list is empty.

The isEnumerating flag is set to false by default, and is set to true whenever an enumerator is created for the collection. The enumerator looks at this flag to determine if the underlying collection has changed; true indicates that the collection is stable and false indicates that the enumerator is invalid. The addition and removal methods in the collection will always reset this flag to false.

This particular list implementation maintains the count of items in the list as items are added and removed. 

    public SinglyLinkedList()
    {
    }

    public SinglyLinkedList(ICollection collection)
    {
        foreach (object o in collection)
        {
            this.AddBack(o);
        }
    }

The first constructor creates an empty list, which means that the count is zero and the head node refers to itself. The second constructor accepts a collection of objects which it uses to populate a new list. 

    public void AddFront(object item)
    {
        // Invalidate any active enumerators
        isEnumerating = false;

        // Insert a new node after the head
        head.Next = new Node(head.Next);

        // Set the value of the new node.
        head.Next.Value = item;

        ++count;
    }

This method inserts a node at the front of a list. The parameter to the Node constructor is the node that will be referenced as the next in the chain. After inserting a new node at the front of the list, the count is updated so that it remains in sync with the total number of nodes in the list.

Notice that the first thing this method does is invalidate any existing enumerators by clearing the isEnumerating flag. Later you'll see how the enumerators check this flag. 

    public object RemoveFront()
    {
        // Invalidate any active enumerators
        isEnumerating = false;

        // Point the head's next reference to the node after the 
        // node being removed, effectively unlinking the node from 
        // the chain.
        object o = head.Next.Value;
        head.Next = head.Next.Next;

        --count;

        return o; 
    }

This is essentially the reverse of the AddFront method. The first node in the chain is unlinked by making the head pointer reference the second node. The count is decremented and the value that was stored in the node is returned. 

    public void AddBack(object item)
    {
        // Invalidate any active enumerators
        isEnumerating = false;

        // Insert a new node after the head.
        head.Next = new Node(head.Next);

        // Store the value in the head.
        head.Value = item;

        // Move the head reference forward, which makes the 
        // old head the new tail of the chain. 
        head = head.Next;
        head.Value = null;

        ++count;
    }

The AddBack method stores the new value in the head node and creates a new node after that which becomes the head node. This makes adding an element to the end of the list a constant-time operation. Otherwise, this method is the same as AddFront. 

    public object RemoveBack()
    {
        // Invalidate any active enumerators
        isEnumerating = false;

        // Move the head pointer to the last node in the list, 
        // then call RemoveFront to remove the node that 
        // used to be the head node.

        Node removeNode = head;

        // Find the tail of the list.
        while (head.Next != removeNode)
        {
            head = head.Next;
        }

        return this.RemoveFront();
    }

Removing a node from the end of the list is an O(n) operation, which means that the time it takes to perform this operation is proportional to the number of items in the list. The head node is moved to reference the tail, effectively removing the tail node. RemoveFront is called to remove the old head node from the list. 

    public static SinglyLinkedList operator+(
        SinglyLinkedList lhs, 
        object rhs
        )
    {
        lhs.AddBack(rhs);
        return lhs;
    }

    public static bool operator==(
        SinglyLinkedList lhs, 
        SinglyLinkedList rhs
        )
    {
        return lhs.Equals(rhs);
    }

    public static bool operator!=(
        SinglyLinkedList lhs, 
        SinglyLinkedList rhs
        )
    {
        return !lhs.Equals(rhs);
    }

These overloaded operators simplify the use of the class in C# source (or obfuscate it, depending on your opinion of overloaded operators in general). The operator+ allows for the addition of new objects to the end of the list. The operator== and operator!= overloads call the overridden Equals method, which is discussed later.

The ICollection Implementation

Now that the data structure code is written, it's time to expose it as a collection to .NET languages. This involves implementing the methods in the ICollection interface. 

    public virtual void CopyTo(Array array , int index)
    {
        if (object.ReferenceEquals(array, null))
        {
            throw new ArgumentNullException(
                "Null array reference", 
                "array"
                );
        }

        if (index < 0)
        {
            throw new ArgumentOutOfRangeException(
                "Index is out of range", 
                "index"
                );
        }

        if (array.Rank > 1)
        {
            throw new ArgumentException(
                "Array is multi-dimensional", 
                "array"
                );
        }

        foreach (object o in this)
        {
            array.SetValue(o, index);
            index++;
        }
    }

The CopyTo method copies items from the current collection into the specified array instance, starting at the specified index. The three if statements at the top test the validity of the parameters and returns the documented exceptions for each exception condition. The array parameter must not be null, the index parameter must be a valid index, and the array must be one-dimensional. 

    public virtual int Count
    {
        get { return this.count; }
    }

The Count property returns the number of items in the collection. As mentioned previously, this particular list implementation maintains the count as items are added or removed. Another option would be to count the number of items when the Count property is requested and return the count. This would become slower as the list grew, but some collection implementations require this behavior. 

    public virtual bool IsSynchronized
    {
        get { return false; }
    }

    public virtual object SyncRoot
    {
        get { return this; }
    }

IsSynchronized returns a flag indicating if the collection is synchronized for thread safety. By default most collections are not thread safe in order to improve performance. The implementation may provide a wrapper class to synchronize access to the collection, in which case the IsSynchronized method would be overridden to return true.

The SyncRoot property returns a reference to an object that clients of the collection can use to synchronize access to the collection. This implementation returns a reference to the collection instance.

The IEnumerable Implementation

It's the implemenation of the IEnumerable interface that allows the 

    public virtual IEnumerator GetEnumerator()
    {
        // Flag the collection as being in an enumeration state. As 
        // long as this flag is true, the enumeration is valid. If 
        // any nodes are added or removed, existing enumerators are 
        // no longer valid.
        isEnumerating = true;
        return new Enumerator(this);
    }

Some prose.

The ICloneable Implementation

Some prose. 

    public virtual object Clone()
    {
        return new SinglyLinkedList(this);
    }

Some prose.

System.Object Overrides

Some prose. 

    public override bool Equals(object compare)
    {
        // If compare is another reference to this, they're the same.
        if (base.Equals(compare))
        {
            return true;
        }
        else
        {
            SinglyLinkedList compareList = compare as SinglyLinkedList;

            // If compare is of type LinkedList, and it has the same 
            // number of elements as this object, continue test.
            if (   !(object.ReferenceEquals(compareList, null)) 
                && this.Count == compareList.Count)
            {
                IEnumerator thisEnum = this.GetEnumerator();
                IEnumerator compareEnum = compareList.GetEnumerator();

                // Compare each element in compare to each element 
                // in this list. If an element does not match, these 
                // lists are not equal.
                while (thisEnum.MoveNext() && compareEnum.MoveNext())
                {
                    if (!thisEnum.Current.Equals(compareEnum.Current))
                    {
                        return false;
                    }
                }
            }
        }

        return false;
    }

Some prose. 

    public override int GetHashCode()
    {
        int hashCode = 0;

        foreach (object o in this)
        {
            hashCode ^= o.GetHashCode();
        }

        return hashCode;
    }

Some prose.

The Node Class

Some prose. 

    [Serializable]
    internal class Node
    {

Some prose. 

        private object nodeValue;
        private Node next;

Some prose. 

        public object Value
        {
            get { return this.nodeValue; }
            set { this.nodeValue = value; }
        }

        public Node Next
        {
            get { return this.next; }
            set { this.next = value; }
        }

Some prose. 

        public Node() 
        {
            this.next = this;
        }

Some prose. 

        public Node(Node next) 
        {
            this.next = next;
        }
    }

Some prose.

The IEnumerator Implementation

Some prose. 

    internal class Enumerator : IEnumerator
    {
        private SinglyLinkedList list;
        private Node current;
        private bool isValid;

Some prose. 

        public Enumerator(SinglyLinkedList list)
        {
            this.list = list;
            this.current = list.head;
            this.isValid = true;
        }

Some prose. 

        private void CheckValid()
        {
            if (!isValid || !list.isEnumerating)
            {
                throw new InvalidOperationException();
            }
        }

Some prose. 

        /***************************************************************
        The following methods are implementations of the IEnumerator 
        interface.
        ***************************************************************/

        public virtual bool MoveNext()
        {
            // Throw exception if the enumerator is not valid.
            CheckValid();

            // Advance to the next node in the list.
            current = current.Next;

            // If the current node is the head of the list, then 
            // the entire list has been traversed.
            if (object.ReferenceEquals(current, list.head))
            {
                // Consequently, the enumerator is no longer valid.
                isValid = false;
            }

            // Returns true if the current node reference was 
            // successfully advanced; false if the enumerator is 
            // no longer valid.
            return isValid;
        }

Some prose. 

        public virtual void Reset()
        {
            // The enumerator may only be reset if the underlying 
            // collection has not been modified.
            if (!list.isEnumerating)
            {
                throw new InvalidOperationException();
            }

            // Move the current node reference back to the 
            // head of the list.
            current = list.head;

            // Once reset, the enumerator is valid again.
            isValid = true;
        }

Some prose. 

        public object Current
        {
            get 
            { 
                // Throw exception if the enumerator is not valid.
                CheckValid();
                return current.Value; 
            }
        }
    }
}

Some prose.