The Queue<T> class (and Stack<T> too) of the .NET Framework from Microsoft is implemented using an array. While this is a perfectly good approach, I think that a Linked List based implementation could be desired in some situations (specifically when the size of the queue is not fixed).

Since the implementation alone would be rather simple for a post, I’ll show you how to implement Unit Testing with the class using Nunit. Although this is a rather simple class to test I think it will show the basic concepts behind unit testing. First of all let’s begin with the interface of the class. We will call it LinkedListQueue<T>. We basically need the typical operations of a queue.

The interface (without the implementation) is going to be something similar to this:

using System;
public class LinkedListQueue
{

    #region LinkedListQueue Members

    public T Dequeue()
    {
        throw new System.NotImplementedException();
    }

    public void Enqueue(T item)
    {
        throw new System.NotImplementedException();
    }

    public T Peek()
    {
        throw new System.NotImplementedException();
    }

    public void Clear()
    {
        throw new System.NotImplementedException();
    }

    public int Count
    {
        get { throw new System.NotImplementedException(); }
    }

    #endregion
}

The thing about unit testing is to first write the different tests so we know what we want to test and then we have to write the code so the tests are passed. Following this convention, now is the time to write some tests using Nunit. To do so, we have to create a new project of type Class Library in Visual Studio (we could have the tests on the same code but it’s better to have it separately so we don’t bloat the real production code). For more information about how to install and set up Nunit I suggest you visit the site for more information. I called the project LinkedListQueueTest

Once we have the code, we can start writing tests in a special class which will have this modifier:

[TestFixture]
public class LinkedListQueueTest
{}

Inside this class we have to write one method for each test we want to perform. It’s usually a good practice to have one test per method on the class you’re testing. In our case, we will begin testing the Enqueue method. To mark a method as a test, we have to add a modifier to it like this:

[Test]
public void Dequeue()
{}

And in the body of the method, we have to perform the test we need. Usually the tests have a structure: creating an object on which to test, executing the method, and confirm that the result is the same as we expected. Let’s do a simple code for our test:

[Test]
public void Dequeue()
{
    LinkedListQueue queue = new LinkedListQueue();
    //We enqueue some items to test
    queue.Enqueue(1);
    queue.Enqueue(2);
    queue.Enqueue(3);
    queue.Enqueue(4);
    queue.Enqueue(5);
    //For each number enqueued we check that is removed properly and in the
    //queue order (FIFO)
    Assert.AreEqual(queue.Dequeue(), 1);
    Assert.AreEqual(queue.Count, 4);
    Assert.AreEqual(queue.Dequeue(), 2);
    Assert.AreEqual(queue.Count, 3);
    Assert.AreEqual(queue.Dequeue(), 3);
    Assert.AreEqual(queue.Count, 2);
    Assert.AreEqual(queue.Dequeue(), 4);
    Assert.AreEqual(queue.Count, 1);
    Assert.AreEqual(queue.Dequeue(), 5);
    Assert.AreEqual(queue.Count, 0);
    Assert.Throws(
        delegate
        {
            queue.Dequeue();
        }
    );
}

I suggest you read the Nunit documentation to see the different assertions you have available.

Now that we wrote our first test, we should start thinking and writing the rest of the tests. To simplify the post, here’s a full class showing some tests that you may have wanted to perform:

using System;
using System.Collections.Generic;
using System.Text;
using NUnit.Framework;

namespace ThinkInGeek.Collections.Generic.Testing
{
    [TestFixture]
    public class LinkedListQueueTest
    {
        [Test]
        public void Dequeue()
        {
            LinkedListQueue queue = new LinkedListQueue();
            //We enqueue some items to test
            queue.Enqueue(1);
            queue.Enqueue(2);
            queue.Enqueue(3);
            queue.Enqueue(4);
            queue.Enqueue(5);
            //For each number enqueued we check that is removed properly and in the
            //queue order (FIFO)
            Assert.AreEqual(queue.Dequeue(), 1);
            Assert.AreEqual(queue.Count, 4);
            Assert.AreEqual(queue.Dequeue(), 2);
            Assert.AreEqual(queue.Count, 3);
            Assert.AreEqual(queue.Dequeue(), 3);
            Assert.AreEqual(queue.Count, 2);
            Assert.AreEqual(queue.Dequeue(), 4);
            Assert.AreEqual(queue.Count, 1);
            Assert.AreEqual(queue.Dequeue(), 5);
            Assert.AreEqual(queue.Count, 0);
            Assert.Throws(
                delegate
                {
                    queue.Dequeue();
                }
            );
        }

        [Test]
        public void Enqueue()
        {
            LinkedListQueue queue = new LinkedListQueue();
            //We enqueue some items to test and check that the items are inserted correctly
            queue.Enqueue(1);
            Assert.AreEqual(queue.Count, 1);
            queue.Enqueue(2);
            Assert.AreEqual(queue.Count, 2);
            queue.Enqueue(3);
            Assert.AreEqual(queue.Count, 3);
            queue.Enqueue(4);
            Assert.AreEqual(queue.Count, 4);
            queue.Enqueue(5);
            Assert.AreEqual(queue.Count, 5);
        }

        [Test]
        public void Peek()
        {
            LinkedListQueue queue = new LinkedListQueue();
            //We enqueue some items to test
            queue.Enqueue(1);
            queue.Enqueue(2);
            queue.Enqueue(3);
            queue.Enqueue(4);
            queue.Enqueue(5);
            //We check that after a peeking we have the correct value but the item
            //is not deleted
            Assert.AreEqual(queue.Peek(), 1);
            Assert.AreEqual(queue.Count, 5);
            queue.Dequeue();
            Assert.AreEqual(queue.Peek(), 2);
            Assert.AreEqual(queue.Count, 4);
            queue.Dequeue();
            Assert.AreEqual(queue.Peek(), 3);
            Assert.AreEqual(queue.Count, 3);
            queue.Dequeue();
            Assert.AreEqual(queue.Peek(), 4);
            Assert.AreEqual(queue.Count, 2);
            queue.Dequeue();
            Assert.AreEqual(queue.Peek(), 5);
            Assert.AreEqual(queue.Count, 1);
            queue.Dequeue();
            Assert.Throws(
                delegate
                {
                    queue.Peek();
                }
            );
        }

        [Test]
        public void Clear()
        {
            LinkedListQueue queue = new LinkedListQueue();
            queue.Enqueue(1);
            queue.Enqueue(2);
            queue.Enqueue(3);
            queue.Enqueue(4);
            queue.Enqueue(5);
            queue.Clear();
            Assert.AreEqual(queue.Count, 0);
        }
    }
}

To see how our test behave, we have to open the resulting LinkedListQueueTest.dll in the Nunit tester program. As we have written no real code on the queue class, it’s obvious that our tests will fail. So let’s get our hands dirty and start programming our queue.

I will not go into the details because a linked list based queue is really easy to implement, so here’s the final code of the class:

using System;

namespace ThinkInGeek.Collections.Generic
{
    public class LinkedListQueue
    {
        #region Node inner class

        public class Node
        {
            public K Element { get; set; }
            public Node NextElement { get; set; }
        }

        #endregion

        #region Private members

        private int m_count = 0;
        private Node m_head = null;
        private Node m_tail = null;

        #endregion

        public T Dequeue()
        {
            if (m_head == null)
            {
                throw new InvalidOperationException();
            }
            //We have to return the item on the head and update the new head
            T currentItem = m_head.Element;
            m_head = m_head.NextElement;
            m_count--;
            return currentItem;
        }

        public void Enqueue(T item)
        {
            //We need to add the item and update the tail
            Node newNode = new Node();
            newNode.Element = item;
            if (m_tail != null)
            {
                m_tail.NextElement = newNode;
            }
            m_tail = newNode;
            if (m_head == null)
            {
                m_head = newNode;
            }
            m_count++;
        }

        public T Peek()
        {
            if (m_head == null)
            {
                throw new InvalidOperationException();
            }
            return m_head.Element;
        }

        public void Clear()
        {
            m_head = null;
            m_tail = null;
            m_count = 0;
        }

        public int Count
        {
            get { return m_count; }
        }
    }
}

The advantage of unit testing is that now the testing is going to be done automatically. The only thing we have to do is open the testing dll file into Nunit and see how’s the outcome. As we’re really good programmers, using the code I showed you, all the tests will pass :)

Unit Testing results window

This is a really simple example of how things should be done with unit testing using C# and Nunit, but I hope it can get you started and you can grasp the philosophy of it. For more information I really recommend reading the book Pragmatic Unit Testing in C# with NUnit.