Geeks With Blogs
Robert's Blog ideas about design and development

If I had it to do all over again, I would have TDDed my first linked list from the very beginning.

One thing about the Computer Science classroom that always made me feel ill at ease was the almost complete lack of discussion about good programming practice.

I think this is probably more of a symptom of university culture at large than any one particular thing that CS departments are to blame for. My proof of this is the almost complete lack of any focus on practical application when I was receiving my mathmetics education in college. Never where there two departments whose subject matter saw more potential for practical application who spent less time on practically applying said knowledge than Math and Computer Science.

I firmly believe that seeing how a principle or concept can be applied in one situation will provide insight into how that principle or concept can be reapplied in the future.

Mastery comes from experience using your toolset. There is absolutely a need for theory (theoriticians keep us moving forward), but there is a need for practical application as well. What good does it do to hand someone a tool that is new to them if you don't show them how best to use it?

If I had a dollar for everytime a computer science student (or any student for that matter) came to me for help on a programming project, I'd have alot of dollars, and my degree says Environmental Design folks.

With that in mind, it is my suggestion to all Computer Science professors out there teaching a Data Structures class, that you start the semester by teaching your students Test Driven Development.

No other single technique or practice has had broader impact on my maturity or efficacy as a programmer than TDD. There is virtually no cost to employ the practice of TDD among CS students. While working part-time and going to school full-time, I read the first chapter of Kent Beck's book, Test Driven Development: By Example and was well on my way writing unit tests at work within one week.

Although I don't believe that it is a stated objective of the book, Test Driven Development by Example actively promotes writing self-documenting code. Futhermore, among many folks, myself included, unit tests are seen as part of the documentation themselves. What better to document the use of an object than seeing the object used in a unit test (except maybe usage notes).

The benefit to the programming classroom of TDD is threefold:

  1. Unit tests allow peers and teachers to see the intended behavior of an object written by a student regardless of whether or not the object was sucessfully implemented
  2. Unit tests give the student a safety net
  3. Unit tests serve to document the student's code

I also believe that using a test-first approach will allow students to tackle complex problems more quickly.

There is a paradigm shift that comes with practicing TDD. That shift is the act of focusing on writing code that functions properly right from the very beginning rather than focusing on simply writing code.

I have known many students, myself included, who are guilty of spewing forth large amounts of code without stopping to use the restroom or compile in an effort to meet a deadline. This is a bad habbit that should be broken at the earliest possible time.

I don't care who you are, you should write code one object at a time, one method at a time. TDD does a good job of promoting this. I think TDD can also help students to keep from writing spaghetti code in the first place (along with a talk about separation of concerns, if it is not clear what an object does, it is hard to use it).

I'll conclude this article with a demo of how to unit test a linked list in C# using NUnit, but before I do that, let me say: teachers, teach your students to program well from the start.

Test Driving a Linked List

The source code for this example is available upon request. I don't make it publicly available here, because if you are reading this to acquaint yourself with TDD, I want you to learn something by implementing this code on your own.

To begin, we'll create a C# project named ListList in Visual Studio. Then we'll add nunit.framework.dll as a reference. Now to the code

To the root of my project we'll add a folder named "Tests" to that folder we'll add a class named MyLinkedListFixture.cs

using NUnit.Framework;
namespace LinkedList.Tests
{
[TestFixture]
public class MyLinkedListFixture
{
[Test]
public void CountReflectsNumberOfItemsAdded()
{
Assert.Fail();
}
}
}

The first thing we did was to define a test fixture and a single faliling unit test inside that fixture. That is what test-first is all about. Now we'll compile our project and open the assembly in NUnit. Let's run the test. The bar goes red. We have our first failing test.

Now that we've verified that the test harness is working, we'll write some code to make the test pass. The list we are writing will implement IList<T> from System.Collections.Generic. It is a fairly widely used interface. So now we'll create a class named MyLinkedList at the root of my project

using System;
using System.Collections.Generic;
using System.Text;

namespace LinkedList
{
public class MyLinkedList<T> : IList<T>
{

}
}

Now we'll right click on IList<T> in my class declaration in Visual Studio then select Implement Interface > Implement Interface. This will stub out all the methods defined in IList<T> so that my code can compile.

But wait, shouldn't we define a list node class first? Yes, I think we should. When test-driving code, I usually try to write the most granular object first, and in our case, you can't get more granular than the container for the list items. We'll add MyListNodeFixture.cs to my "Tests" folder

using NUnit.Framework;
namespace LinkedList.Tests
{
[TestFixture]
public class MyListNodeFixture
{
[Test]
public void ClearRemovesItem()
{
Assert.Fail();
}
}
}

Now we have our first failing test for MyListNode. At this point, we will compile my project and run our test to verify that the test suite runs. We have two failing tests.

Now we'll change the test to indicate how the Clear() method shoud behave.

        [Test]
public void ClearRemovesItem()
{
string name = "Adam";
MyListNode<string> node = new MyListNode<string>(name);
node.Clear();
Assert.IsTrue(node.item == null);
}

Of course this won't compile, so now we need to flesh out MyListNode a little.

using System;
using System.Collections.Generic;
using System.Text;

namespace LinkedList
{
public class MyListNode<T>
{
internal T item;

public MyListNode(T item)
{
this.item = item;
}

internal void Clear()
{

}
}
}

Okay, now we'll compile this code. Yet we still have a failing test. Let's amend my Clear() method to make the test pass.

        internal void Clear()
{
item = default(T);
}

That'll do it! Our first passing test! To make our test a little more descriptive, we might rewrite it as:

            string name = "Adam";
MyListNode<string> node = new MyListNode<string>(name);
Assert.IsTrue(node.item.Equals(name));
node.Clear();
Assert.IsTrue(node.item == null);

The above test tells us (when it passes) that we can create an node with an item , that the item is retained by the node, and that invoking Clear() on the node removes the reference to the item. Quoting Practices of an Agile Developer: "[T]ests are like a kind of executable documentation." Tests can inform a teacher of a student's intent while writing code and can even shed a kind of light on the student's thought process while writing code.

Now we'll define a test to verify that when clear is called, the references to adjacent nodes are removed.

        [Test]
public void ClearRemovesReferencesToAdjacentNodes()
{
string name = "Adam";
string name1 = "Jane";
string name2 = "Roger";
MyListNode<string> node = new MyListNode<string>(name);
node.previous = new MyListNode<string>(name1);
node.next = new MyListNode<string>(name2);
node.Clear();
Assert.IsTrue(node.previous == null);
Assert.IsTrue(node.next == null);
}

Again, this won't compile, so we'll flesh out MyListNode a little more.

    public class MyListNode<T>
{
internal T item;
internal MyListNode<T> previous;
internal MyListNode<T> next;
...

Of course, this will compile, but we now have a failing test. Now we'll finish implementing Clear().

        internal void Clear()
{
item = default(T);
previous = null;
next = null;
}

Now we have another passing test. Since that's done, we'll return to MyLinkedList. We'll edit the test CountReflectsNumberOfItemsAdded.

[Test]
public void CountReflectsNumberOfItemsAdded()
{
MyLinkedList<string> list = new MyLinkedList<string>();
list.Add("one");
list.Add("two");
list.Add("three");
Assert.IsTrue(list.Count == 3);
}

This will compile since we've implemented IList<T>, but we still have a failing test.

    public class MyLinkedList<T> : IList<T>
{
protected int count = 0;
...
public void Add(T item)
{
if (item == null)
throw new ArgumentNullException("Parameter item for method Add should not be null");
count++;
}
...
public int Count
{
get { return count; }
}
...

Now we have our first passing test for MyLinkedList. Of course it doesn't do us much good to have a list that merely increments a counter. So now we'll write a test to verify that the first element added to a list is assigned to the list head.

        [Test]
public void WhenFirstItemIsAddedItIsInNodeAtHeadOfList()
{
string name = "Sue";
MyLinkedList<string> list = new MyLinkedList<string>();
list.Add(name);
Assert.IsTrue(list.head.item.Equals(name));
}

We need to add a MyListNode field named "head" to our list in order for our code to compile.

    public class MyLinkedList<T> : IList<T>
{
protected int count = 0;

internal MyListNode<T> head;

...

This code will compile, but we see that our test fails because the reference to list.head will return null causing an exception. So we'll write some code to make the test pass.

        public void Add(T item)
{
if (item == null)
throw new ArgumentNullException("Parameter item for method Add should not be null");
count++;
head = new MyListNode<T>(item);
}

Our test now passes. On to the next one. We also want to check that the tail of our list points to the last node added.

[Test]
public void TailPointsToMostRecentlyAddedItem()
{
string name = "Bill";
MyLinkedList<string> list = new MyLinkedList<string>();
list.Add(name);
Assert.IsTrue(list.tail.item.Equals(name));
}

We can safely state that this will not compile, I'll leave the decision as to whether or not to try to compile to you. So I'll go ahead and add a tail field to the list so that the project will compile.

    public class MyLinkedList<T> : IList<T>
{
...
internal MyListNode<T> tail;
...

Our project compiles but our test throws another exception. We'll add some code to make the test pass.

        public void Add(T item)
{
if (item == null)
throw new ArgumentNullException("Parameter item for method Add should not be null");
count++;
head = tail = new MyListNode<T>(item);
}

Our test passes, excellent! Now we are really starting to pick up speed. We should probably go back to our test fixture and remove duplication to clean it up a little. We'll pull out repeated elements into a setup method like so:

using NUnit.Framework;
namespace LinkedList.Tests
{
[TestFixture]
public class MyLinkedListFixture
{
MyLinkedList<string> list;
string name = "Sue";

[SetUp]
public void Setup()
{
list = new MyLinkedList<string>();
}

[Test]
public void CountReflectsNumberOfItemsAdded()
{
list.Add("one");
list.Add("two");
list.Add("three");
Assert.IsTrue(list.Count == 3);
}

[Test]
public void WhenFirstItemIsAddedItIsInNodeAtHeadOfList()
{
list.Add(name);
Assert.IsTrue(list.head.item.Equals(name));
}

[Test]
public void TailPointsToMostRecentlyAddedItem()
{
list.Add(name);
Assert.IsTrue(list.tail.item.Equals(name));
}
}
}

Hopefully by now you've started to see a pattern emerge:

  • We write a failing test and run it to watch it fail.
  • We'll write code to make the test pass.
  • We'll go back and clean up our code

This approach is commonly refered to as "Red, Green, Refactor". We'll edit our test to make it a little more descriptive

        [Test]
public void TailPointsToMostRecentlyAddedItem()
{
list.Add(name);
Assert.IsTrue(list.tail.item.Equals(name));
string name1 = "Jim";
list.Add(name1);
Assert.IsTrue(list.tail.item.Equals(name1));
}

Our test still passes, so we'll move on to the next one. We want to verify that adding a new node does not change the reference to the head of the list.

        [Test]
public void AddingNewItemDoesNotChangeReferenceToHead()
{
list.Add(name);
Assert.IsTrue(list.head.item.Equals(name));
string name1 = "Jim";
list.Add(name1);
Assert.IsTrue(list.head.item.Equals(name));
}

Let's compile and run this test. We see that it does not pass. Now we'll write code to make the test pass.

        public void Add(T item)
{
if (item == null)
throw new ArgumentNullException("Parameter item for method Add should not be null");
count++;
if(head == null)head = tail = new MyListNode<T>(item);
else tail = new MyListNode<T>(item);
}

At this point, the "Add" method seeems to pretty well implemented. So we'll move on to something else. It'd be nice to be able to insert or remove items from the list. We are going to need the list iterator to perform that work, so we will write the first test for it now. Since we will implement our iterator as a nested internal class, we will just add the tests for it to MyLinkedListFixture.

        [Test]
public void MoveNextReturnsFalseIfListIsEmpty()
{
IEnumerator<string> enumerator = list.GetEnumerator();
Assert.IsFalse(enumerator.MoveNext());
}

This test will tell us if MoveNext returns false with an empty list. Of course this won't compile, so we'll create our enumerator and implement it with the Visual Studio right -click menu as before

using System;
using System.Collections.Generic;
using System.Text;

namespace LinkedList
{
public class MyLinkedList<T> : IList<T>
{
...
internal class MyLinkedListEnumerator<T> : IEnumerator<T>
{

#region IEnumerator<T> Members

public T Current
{
get { throw new Exception("The method or operation is not implemented."); }
}

#endregion

#region IDisposable Members

public void Dispose()
{
throw new Exception("The method or operation is not implemented.");
}

#endregion

#region IEnumerator Members

object System.Collections.IEnumerator.Current
{
get { throw new Exception("The method or operation is not implemented."); }
}

public bool MoveNext()
{
throw new Exception("The method or operation is not implemented.");
}

public void Reset()
{
throw new Exception("The method or operation is not implemented.");
}

#endregion
}
}
}

Now we have a failing test. Let's write some code to make it pass. We'll start off by defining the constructor for our enumerator.

        internal class MyLinkedListEnumerator<T> : IEnumerator<T>
{
internal MyLinkedList<T> list;

public MyLinkedListEnumerator(MyLinkedList<T> list)
{
this.list = list;
}
...

Now we'll go back and implement the GetEnumerator method on MyLinkedList.

        public IEnumerator<T> GetEnumerator()
{
return new MyLinkedListEnumerator<T>(this);
}

We know that this will compile, but that our test will still fail, so now we will implement MoveNext

        internal class MyLinkedListEnumerator<T> : IEnumerator<T>
{
protected MyListNode<T> current;

public bool MoveNext()
{
if (current == null && list.head == null) return false;
return true;
}
...

On to our next test. It would probably be good if MoveNext did something more than return false with an empty list, so we will write a test to see that MoveNext will take us to the first item in the list.

        [Test]
public void MoveNextAdvancesToFirstItemInList()
{
list.Add(name);
IEnumerator<string> enumerator = list.GetEnumerator();
Assert.IsTrue(enumerator.MoveNext());
Assert.IsTrue(enumerator.Current.Equals(name));
}

This test will tell us if MoveNext returns the appropriate value, and if Current returns the appropriate value. We compile and run the test, and we see that we get a NullReferenceException at Current, so we'll implement it.

            #region IEnumerator<T> Members

public T Current
{
get { return current.item; }
}

#endregion

...

#region IEnumerator Members

object System.Collections.IEnumerator.Current
{
get { return Current; }
}

...

We still have a failing test. Current throws an exception because MoveNext doesn't advance to the head of the list, so we'll fix that.

            public bool MoveNext()
{
if (current == null && list.head == null) return false;
current = list.head;
return true;
}

Success, our test passes! Now we want to be sure our enumerator can advance beyond just the first item in the list.

        [Test]
public void MoveNextAdvancesToNthItemInList()
{
list.Add(name);
string name1 = "Jim";
list.Add(name1);
IEnumerator<string> enumerator = list.GetEnumerator();
enumerator.MoveNext();
Assert.IsTrue(enumerator.Current.Equals(name));
enumerator.MoveNext();
Assert.IsTrue(enumerator.Current.Equals(name1));
}

Our test fails, because every time we call MoveNext, it assigns list.head to current.

            public bool MoveNext()
{
if (current == null && list.head == null) return false;
if (current == null) current = list.head;
else if (current.next == null) return false;
else current = current.next;
return true;
}

But wait, our test still fails. That is because we are not making an assignment to the current tail's "next" field when we add and item, so'll we'll fix that.

        public void Add(T item)
{
if (item == null)
throw new ArgumentNullException("Parameter item for method Add should not be null");
count++;
if (head == null) head = tail = new MyListNode<T>(item);
else
{
MyListNode<T> node = new MyListNode<T>(item);
node.previous = tail;
tail.next = node;
tail = node;
}
}

All our test pass again. There is some duplication between the tests for the enumerator. Every one of them requires an iterator, so we'll just move the instantiation of the iterator up into the Setup method.

    [TestFixture]
public class MyLinkedListFixture
{
MyLinkedList<string> list;
string name = "Sue";
IEnumerator<string> enumerator;

[SetUp]
public void Setup()
{
list = new MyLinkedList<string>();
enumerator = list.GetEnumerator();
}

...

[Test]
public void MoveNextReturnsFalseIfListIsEmpty()
{
Assert.IsFalse(enumerator.MoveNext());
}

[Test]
public void MoveNextAdvancesToFirstItemInList()
{
list.Add(name);
Assert.IsTrue(enumerator.MoveNext());
Assert.IsTrue(enumerator.Current.Equals(name));
}

[Test]
public void MoveNextAdvancesToNthItemInList()
{
list.Add(name);
string name1 = "Jim";
list.Add(name1);
enumerator.MoveNext();
Assert.IsTrue(enumerator.Current.Equals(name));
enumerator.MoveNext();
Assert.IsTrue(enumerator.Current.Equals(name1));
}

We also notice that most tests are going to require more than one string to add, so we'll make "name1" a field in our fixture.

    [TestFixture]
public class MyLinkedListFixture
{
MyLinkedList<string> list;
string name = "Sue";
string name1 = "Jim";

Now we'll write a test that will indicate to us that Reset() is doing its job.

        [Test]
public void ResetWorks()
{
list.Add(name);
list.Add(name1);
enumerator.MoveNext();
enumerator.MoveNext();
enumerator.Reset();
enumerator.MoveNext();
Assert.IsTrue(enumerator.Current.Equals(name));
}

We have a failing test again, so let's make it pass.

            public void Reset()
{
current = null;
}

Presto Chango! From red to green. Now we have a working test, not to mention a fully implemented enumerator!

For our next feat, we will insert an item into a list.

        [Test]
public void CanInsertItemAtNthPositionInList()
{
list.Add(name);
list.Add(name1);
string name2 = "Janice";
list.Insert(1, name2);
enumerator.MoveNext();
enumerator.MoveNext();
Assert.IsTrue(enumerator.Current.Equals(name2));
}

Our test fails because Insert is not yet implemented.

        public void Insert(int index, T item)
{
int position = -1;
MyListNode<T> current = null;
do
{
if(current == null) current = head;
else current = current.next;
position++;
}while (position < index - 1 && current.next != null);

MyListNode<T> node = new MyListNode<T>(item);
if (current.next != null)
{
node.next = current.next;
current.next.previous = node;
}
current.next = node;
node.previous = current;
count++;
}

Our test passes, but we want to throw a meaningful exception if someone tries to insert at an index past the end of the list.

        [Test]
[ExpectedException(typeof(IndexOutOfRangeException))]
public void InsertOnNegativeIndexThrowsException()
{
list.Add(name);
list.Insert(-1, "Jane");
}

That looks good, but now we need to write some code to get our test passing

        public void Insert(int index, T item)
{
if (index >= Count) throw new
IndexOutOfRangeException(
"Specified index for insertion must be less than the total number of items."
);
         ...

We want to also verify that inserting on an empty list causes an exception.

        [Test]
[ExpectedException(typeof(Exception))]
public void InsertOnEmptyListThrowsException()
{
list.Insert(0, "Jim");
}

That's good, now lets implement it.

        public void Insert(int index, T item)
{
if (Count == 0)
throw new Exception("Cannot insert into an empty list.");
...

We also want to make sure that an exception is thrown if an insertion is made with a negative index.

 

That test looks sufficient. To the code...

        public void Insert(int index, T item)
{
if (Count == 0)
throw new Exception("Cannot insert into an empty list.");
if (index < 0)
throw new IndexOutOfRangeException("Specified index for insertion must be positive");
...

Continued ...

Posted on Wednesday, November 28, 2007 5:46 AM Unit Testing , C# | Back to top


Comments on this post: Writing a Linked List: Then vs. Now

# re: Writing a Linked List: Then vs. Now
Requesting Gravatar...
Please! and Amen.
Left by Steve Saxer on Feb 28, 2008 1:57 PM

Your comment:
 (will show your gravatar)


Copyright © Robery Stackhouse | Powered by: GeeksWithBlogs.net