Singly linked list in C#

Today I had a fun of writing a singly linked list in C#. About 15 years ago I written the same class in C++, see An STL-like C++ list class. This list could be used in some special cases, for example, in custom hash table implementation.  Below I provided the source code:

public class SingleLink<T>
{
    public SingleLink(T item)
    {
        Item = item;
    }
    
    public SingleLink<T> Next { get; set; }

    public T Item { get; set; }
}

public struct SingleList<T>
{
    SingleLink<T> Head; //initially it is null

    public SingleLink<T> First
    {
        get
        {
            return Head;
        }
    }

    static public void AddAfter(SingleLink<T> prev, T item)
    {
        AddAfter(prev, new SingleLink<T>(item));
    }

    static public void AddAfter(SingleLink<T> prev, SingleLink<T> link)
    {
        link.Next = prev.Next;

        prev.Next = link;
    }

    public void AddFirst(T item)
    {
        AddFirst(new SingleLink<T>(item));
    }

    public void AddFirst(SingleLink<T> link)
    {
        link.Next = Head;

        Head = link;
    }

    static public void RemoveAfter(SingleLink<T> prev)
    {
        prev.Next = prev.Next.Next;
    }

    /// <summary>
    /// This method should be called only if the first element exists.
    /// </summary>
    public void RemoveFirst()
    {
        Head = Head.Next;
    }

    public int Count
    {
        get
        {
            int count = 0;
            
            for (SingleLink<T> cur = Head; cur != null; cur = cur.Next)
            {
                ++count;
            }

            return count;
        }
    }
}

I had a great time while enjoying how unit tests work:

[TestMethod]
public void SingleListTest()
{
    SingleList<int> list = new SingleList<int>();

    Assert.AreEqual(0, list.Count);

    var link1 = new SingleLink<int>(1);

    list.AddFirst(link1);

    Assert.AreEqual(1, list.Count);
    Assert.AreEqual(link1, list.First);

    var link2 = new SingleLink<int>(2);

    SingleList<int>.AddAfter(link1, link2);

    Assert.AreEqual(2, list.Count);

    var link3 = new SingleLink<int>(2);

    SingleList<int>.AddAfter(link2, link3);

    Assert.AreEqual(3, list.Count);

    list.RemoveFirst();

    Assert.AreEqual(2, list.Count);
    Assert.AreEqual(link2, list.First);

    SingleList<int>.RemoveAfter(link2);

    Assert.AreEqual(1, list.Count);

    list.RemoveFirst();

    Assert.AreEqual(0, list.Count);
}

Leave a Reply

Your email address will not be published. Required fields are marked *