TDD Fun(?) : Creating a linked list in C#

I was reminded just today that it’s been a while since I’ve implemented a linked list from scratch, and it sounded kind of fun.  I also thought that I should create it via a TDD (test-driven development) strategy to give myself an additional +1 to my good-little-coder attribute.

To begin, I’ll do a quick overview of what I needed in order to create a linked list. First, I needed a Node class to hold three values: Next, Previous and Value.  “Next” is a Node-type that holds, you guessed it, the next Node in the list, adjacent to the current Node.  “Previous” is the same concept, except it of course holds the value of the node “in front of” the current node, and “Value” is the currently held value of that node.  For this little demo, I’m not going to use generics, so the LinkedList will be un-typed, so to speak, and therefore Value will actually be an object so that it can old any type.

Next, I’d need a LinkedList class to keep track of the root node, and handle the adding and deleting of nodes in the list. More on that in a bit, we’ve got to write some tests before we delve into this any further!

[Test]
public void CanCreateNewList()
{
    string testValue = "root";
    LinkedList linkedList = new LinkedList(testValue);

    Assert.AreEqual(testValue, linkedList.CurrentNode.Value);
}

[Test]
public void CanAddNodeWhereNextNodeIsNull()
{
    string rootValue = "root";
    string childValue = "child";

    LinkedList linkedList = new LinkedList(rootValue);

    linkedList.AddNode(childValue);

    Assert.AreEqual(linkedList.CurrentNode.Value, childValue);
    Assert.AreEqual(linkedList.CurrentNode.Prev.Value, rootValue);
    Assert.AreEqual(linkedList.Length, 2);
}

[Test]
public void CanAddNodeWhereNextNodeIsNotNull()()
{
    string rootValue = "root";
    string childValue = "child1";
    string newChildValue = "child2";

    LinkedList linkedList = new LinkedList(rootValue);
    linkedList.AddNode(childValue);
    linkedList.Previous(); // root
    linkedList.AddNode(newChildValue);

    Assert.AreEqual(linkedList.CurrentNode.Value, newChildValue);
    Assert.AreEqual(linkedList.CurrentNode.Prev.Value, childValue);
    Assert.AreEqual(linkedList.Length,3);
}

[Test]
public void CannotUsePrevOnRoot()
{
    string rootValue = "root";
    LinkedList linkedList = new LinkedList(rootValue);
    var prevNode = linkedList.Previous();
    var prevPrevNode = linkedList.Previous();

    Assert.AreEqual(rootValue, linkedList.CurrentNode.Value);
    Assert.AreEqual(rootValue, prevNode.Value);
    Assert.AreEqual(rootValue, prevPrevNode.Value);
}

[Test]
public void CannotUseNextOnLastElement()
{
    string rootValue = "root";
    LinkedList linkedList = new LinkedList(rootValue);

}

[Test]
public void CanDeleteNode()
{

    int oldLength, newLength;
    LinkedList linkedList = new LinkedList("root");
    linkedList.AddNode("child");
    oldLength = linkedList.Length;
    linkedList.Delete(1);
    newLength = linkedList.Length;
    Assert.GreaterThan(oldLength, newLength);
}

[Test]
[ExpectedException(typeof(IndexOutOfRangeException))]
public void CannotDeleteNodeWithInvalidIndex()
{
    int oldLength, newLength;
    LinkedList linkedList = new LinkedList("root");
    linkedList.AddNode("child");
    oldLength = linkedList.Length;
    linkedList.Delete(99);
    newLength = linkedList.Length;
    Assert.GreaterThan(oldLength, newLength);
}

[Test]
public void CanGetNodeByGoto()
{
    string rootValue = "root";
    string child1Value = "child1";
    string child2Value = "child2";
    string child3Value = "child3";
    string child4Value = "child4";
    LinkedList linkedList = new LinkedList(rootValue);
    linkedList.AddNode(child1Value);
    linkedList.AddNode(child2Value);
    linkedList.AddNode(child3Value);
    linkedList.AddNode(child4Value);

    Assert.AreEqual(linkedList.Goto(2).Value,child2Value);
}

[Test]
[ExpectedException(typeof(IndexOutOfRangeException))]
public void CannotGetNodeWithInvalidIndex()
{
    string rootValue = "root";
    LinkedList linkedList = new LinkedList(rootValue);

    var node = linkedList.Goto(99);

    Assert.IsNotNull(node);
}

The above tests are the product of my TDD. I created the test, ran the test (they failed), then wrote supporting code to make the test pass. Refactored, repeated, then wrote the next test.

So, what do they do?  The above tests test for the following (if you don’t want to sort through the code):

• Tests that I can successfully create a new LinkedList object
• Tests that I can add a node to a LinkedList object
• Tests that I can delete a node from a LinkedList object
• Tests that I cannot delete a node that doesn’t exist
• Tests that I can quickly “jump to” a node by passing its index
• Tests that I cannot “jump to” a node that doesn’t exist

The code for the Node class:

public class Node
{
    public Node Next { get; set; }
    public Node Prev { get; set; }
    public object Value { get; set; }
}

The code for the LinkedList class:

public class LinkedList
{
    private Node _CurrentNode;
    private int _Count;
    private int _CurrentPosition;

    public Node CurrentNode
    {
        get { return _CurrentNode; }
    }

    public int Count
    {
        get { return _Count; }
    }

    public int CurrentPosition
    {
        get { return _CurrentPosition; }
    }

    public LinkedList(object value)
    {
        _Count = 1;
        _CurrentPosition = 0;

        _CurrentNode = new Node() { Next = null, Prev = null, Value = value };
    }

    public void AddNode(object value)
    {
        if(CurrentNode.Next==null)
        {
            CurrentNode.Next = new Node() {Next = null, Prev = CurrentNode, Value = value};
            _CurrentPosition++;
            _Count++;
            _CurrentNode = _CurrentNode.Next;
        }
        else
        {
            _CurrentNode = _CurrentNode.Next;
            _CurrentPosition++;
            AddNode(value);
        }
    }

    public Node Next()
    {
        if(_CurrentNode.Next != null)
        {
            _CurrentNode = _CurrentNode.Next;
            _CurrentPosition++;
        }
        return _CurrentNode;
    }
    public Node Previous()
    {
        if(_CurrentNode.Prev != null)
        {
            _CurrentNode = _CurrentNode.Prev;
            _CurrentPosition--;
        }
        return _CurrentNode;
    }

    public void Delete(int i)
    {
        var node = this.Goto(i);
        var prevNode = node.Prev;
        var nextNode = node.Next;

        if (prevNode != null)
        {
            prevNode.Next = nextNode;
            if (nextNode != null) nextNode.Prev = prevNode;
        }
        _Count--;
        _CurrentPosition = i - 1;
    }

    public Node Goto(int i)
    {
        if(i>Count-1)
            throw new IndexOutOfRangeException("Index out of range: " + i);
        if(CurrentPosition > i)
        {
            Previous();
            return Goto(i);
        }
        if(CurrentPosition < i)
        {
            Next();
            return Goto(i);
        }
        return CurrentNode;
    }

And that’s really it. I can create a new linked list, add, delete and jump to a specific node.

Tagged as: c#, linked-list, mbunit, TDD, test