ONDotNet.com    
 Published on ONDotNet.com (http://www.ondotnet.com/)
 See this if you're having trouble printing code examples


Implementing Custom Data Bindable Classes: IList

by James Still
09/02/2003

It's no accident that DataSet, Array, TreeNodeCollection, and many other collection classes all behave in a predictably similar fashion. Each of them derive from the IList interface and each of them fully implement all of the methods defined by that interface's contract. Thus, you can use them as data sources for iterative controls like the DataGrid or list controls like DropDownList. You can enumerate through all of the elements in the collection or access them individually by index position. In this article, the third in a three-part series that picks up where the previous two, on CollectionBase and IEnumerable left off, we're going to implement the IList interface to create a custom collection class.

A Singly Linked List

Suppose that you have a tried and true data structure tucked away in your toolkit, a singly linked list that supports sequential access to its elements. You've relied on it many times over the years. It works great. Your class might even look something like this:


public class LinkedList 
{
  internal class Node 
  { 
    public Object item; 
    public Node next; 
  }

  private Node head = null; 
  private int count = 0;

  public int Count 
  { 
    get 
    { 
      return count; 
    } 
  }
  
  public Object this[int index] 
  { 
    get 
    { 
      Node temp = head; 
      if (index > -1 && index < count) 
      { 
        for(int i = 0; i < index; ++i) 
        { 
          temp = temp.next; 
        } 
        return temp.item; 
      } 
      else 
      { 
        throw new IndexOutOfRangeException(); 
      } 
    } 
  } 
  
  public void Insert(Object item) 
  { 
    if (head != null) 
    { 
      Node newNode = new Node(); 
      newNode.item = item; 
      newNode.next = head; 
      head = newNode; 
    } 
    else 
    {
      head = new Node(); 
      head.item = item; 
    } 
    count++; 
  } 
}
	

Why not use it in your next .NET project? You could, of course. When someone from the front-end group calls your middle-tier object and gets back this data structure it will work just fine, up to a point. But sooner or later one of them will complain that he can't bind it to a DataGrid. Someone else will try to use a foreach statement to iterate through the list, only to discover that your class doesn't support it. In the end, this singly linked list is more trouble than it's worth because it fails to interact well with other .NET components.

Programming .NET Components

Related Reading

Programming .NET Components
By Juval Löwy

The best way for your linked list class to play nice with other pieces of software is for it to implement the IList interface. The IList interface is a contract. It is a guarantee that when it comes to collections your code will behave in a standard way each and every time. The compiler forces you to implement against its predefined members--the methods and properties that describe what your collection will do. Let's take a closer look at the IList interface.

The IList Interface

The IList interface derives from two other interfaces:

    
public interface IList : ICollection, IEnumerable

We covered the IEnumerable interface in the second article in this series so I won't go into too much detail on it here. Altogether it has three properties and seven methods:


	interface IList {
    bool IsFixedSize { get; }
    bool IsReadOnly { get; }
    object this[object key] { get;  set; }
    int Add(object value);
    void Clear();
    bool Contains(object value);
    int IndexOf(object value);
    void Insert(int index, object value);
    void Remove(object value);
    void RemoveAt(int index);
  }

In order to be a .NET collection, all custom collection classes must implement the ICollection interface. It has three properties and one method:

interface ICollection {
    public bool IsSynchronized { get; }
    public int Count { get; }
    public object SyncRoot { get; }
    public void CopyTo(Array array, int index);
  }

IEnumerable is the standard interface for supporting the foreach statement and an IEnumerator instance, both of which support enumeration through the collection. Since IList derives from IEnumerable, you are required to implement it when you derive your custom collection class from IList. It has a single method:

interface IEnumerable {
    public IEnumerator GetEnumerator();
  }

So, by implementing against the IList interface we support a standard method for enumerating our list of elements, getting a single element by index position, and inserting, removing, clearing, and counting them. Now that we know what interface members we must implement, let's begin to port our singly linked list class over to a .NET collection class.

IList

The first step in implementing IList is to derive it in our singly linked list class:

public class  LinkedList : IList {
  
    internal class Node {
        public Object Item;
        public Node Next;
    }
  
    private Node head = null;
    private int count = 0;
  }

Here's a neat trick in Visual Studio: after you type "IList" wait for the yellow tooltip to appear. It will prompt you to hit the Tab key if you want Visual Studio to stub out the properties and methods of IList for you. Unless you enjoy typing, hit the Tab key.

Let's implement the IList properties first. Two of them, IsReadOnly and IsFixedSize, are already done because the IDE has set them to return false. Since we want the list to grow and shrink with new values, this default setting is fine. But we do need to implement the Contains property, which should return true if any node in the list contains the value that is passed in as a parameter:


public bool Contains(object value) 
{
  bool containsNode = false;
  if (head != null) 
  {
    Node tempNode = head;
    if (tempNode.Item == value) 
    {
      containsNode 
        = true;
    }
    else 
    {
      for (int i = 0; i < count; ++i) 
      {
              
        tempNode = tempNode.Next;
              
        if (tempNode.Item == value) 
        {
                  
          containsNode = true;
              
        }
      }
    }
  }
  return containsNode;
}

We also have to implement an indexer so that elements can be accessed in the list by their index position:


	public object this[int index] 
{
  get 
  {
    Node temp = head;
    if (index > -1 && index < count) 
    {
      if (index != 
        0) 
      {
              
        for(int i = 0; i < index; ++i) 
        {
                  
          temp = temp.Next;
              
        }
      }
    }
    return temp.Item;
  }
  set 
  {
    Node temp = head;
    if (index > -1 && index < count) 
    {
      if (index != 
        0) 
      {
              
        for(int i = 0; i < index; ++i) 
        {
                  
          temp = temp.Next;
              
        }
      }
      temp.Item = 
        value;
    }
  }
}

That takes care of the properties for IList. Now let's implement its methods. The first method is Add, which accepts any object as its value and will insert a new node at the end of the list to store that value. It should return the index position of the new node:


public int Add(object value) 
{
  if (IsFixedSize) 
  {
    throw new NotSupportedException("List is a fixed size.");
  }

  if (head != null) 
  {
    Node tempNode = head;
    Node newNode = new Node();
    newNode.Item = value;

    // add Item to end of list
    for(int i = 0; i < count - 1; ++i) 
    {
      tempNode = tempNode.Next;
    }
    tempNode.Next = newNode;
  }
  else 
  {
    head = new Node();
    head.Item = value;
  }
  count++;
  return count;
}

The Clear method removes all nodes from the list:


	public void Clear() 
{
  if (IsReadOnly) 
  {
    throw new NotSupportedException("List is read-only.");
  }
  if (head != null) 
  {
    Node prevNode;
    Node tempNode = head;
    for (int i = 0; i < count; ++i) 
    {
      prevNode = tempNode;
      tempNode = tempNode.Next;
      prevNode = null;
    }
  }
}

The IndexOf method takes a value as a parameter and searches the list for that value. If found, it returns the index number for that node, otherwise it returns -1:


public int IndexOf(object value) 
{
    int idx = -1;
    Node temp = head;
    for(int i = 0; i < count; ++i) 
		{
        if (temp.Item == value) 
				{
            idx = i;
        }
    }
    return idx;
  }

The Insert method is similar to the Add method except that it can insert a new node anywhere in the list. That requires a little more work to implement:


	void System.Collections.IList.Insert(int index, object value) 
{
  if ((IsReadOnly) || (IsFixedSize)) 
  {
    throw new NotSupportedException("List is either " + 
      "read-only or a fixed size.");
  }

  if (index > -1 && index < count) 
  {
    // insert at position index
    if (head != null) 
    {
      Node currNode 
        = head;
      // get to 
      index position
        for (int i = 0; i == index; ++i) 
        {
          currNode = currNode.Next;
        }
      Node nextNode = currNode.Next;
      // create new node and assign value
      Node newNode  = new Node();
      newNode.Item  = value;
      // insert new node between curr and Next
      currNode.Next = newNode;
      newNode.Next = nextNode; 
    }
    else 
    {
      // insert in first position as the head
    head = new Node();
    head.Item = value;
    }
  }
  else 
  {
    throw new 
      ArgumentOutOfRangeException("Index is out of range.");
  }
  count++;
}

The last two methods in the IList interface are Remove and RemoveAt, which are similar in that both remove a node from the list. The difference is that Remove will search the list for a passed-in value and remove the first node that matches that value:


public void Remove(object value) 
{
  if (head != null) 
  {
    Node prevNode = head;
    Node tempNode = head;
  
    if (tempNode.Item == value) 
    {
      head = null;
    }
    else 
    {
      for (int i = 0; i < count; ++i) 
      {
        tempNode = tempNode.Next;
              
        if (tempNode.Item == value) 
        {
          // point previous node to Next node
          Node nextNode = tempNode.Next;
          prevNode.Next = nextNode;
          tempNode = null;
          count--;
          return;
        }
        else 
        {
          prevNode = tempNode;
        }
      }
    }
  }
  else 
  {
    throw new Exception("List is empty.");
  }
}

RemoveAt merely gets the node from the list at the location specified by the passed-in index position. In both cases, if the node to be removed is somewhere in the middle of the list, then we must link the previous node to the node after the one to be removed. If we didn't do that we'd break the chain and lose the integrity of our list:


public void RemoveAt(int index) 
{
  if ((IsReadOnly) || (IsFixedSize)) 
  {
    throw new NotSupportedException("List " +
      "is either read-only or a fixed size.");
  }

  if (index > -1 && index < count) 
  {
    if (head != null) 
    {
      // get to index position
      Node prevNode  = head;
      Node tempNode = head;
      if (index != 0) 
      {
        for (int i = 0; i < index; ++i) 
        {
          prevNode = tempNode;
          tempNode = tempNode.Next;
        }
        prevNode.Next = tempNode.Next;
        tempNode = null;
      }
      else 
      {
        head = tempNode.Next;
      }
      count--;
    }
    else 
    {
      throw new Exception("List is empty.");
    }
  }
  else 
  {
    throw new 
      ArgumentOutOfRangeException("Index is out of range.");
  }
}

ICollection

Now all of the members of IList have been implemented, so let's turn our attention to the three members of the ICollection interface. Because thread safety is beyond the scope of this article just leave IsSynchronized and SyncRoot alone. The Count method is easy enough to code:

public int Count { get { return count; } }

That leaves us with the CopyTo method, which takes a one-dimensional array passed in by reference and loads it up with values from the linked list. The method expects an index parameter for the starting position, which must be within the bounds of the collection or else an ArgumentOutOfRangeException is thrown. Also, if the array passed in is not large enough to hold the range of elements in the collection, then an ArgumentException is thrown:


public void CopyTo(Array array, int index) 
{
  Node tempNode = head;
  if (index < 0 || index >= count) 
  {
    throw new 
      ArgumentOutOfRangeException("The index is out of range.");
  }
  if (array.Length < (this.Count - index) + 1) 
  {
    throw new ArgumentException("Array " +
      "cannot hold all values.");
  }
  // advance to starting index position
  for(int i = 0; i < index; ++i) 
  {
    tempNode = tempNode.Next;
  }
  // iterate through list adding to array
  int j = 0;
  for(int i = index; i < count; ++i) 
  {
    array.SetValue(tempNode.Item, i);
    tempNode = tempNode.Next;
    j++;
  }
}

IEnumerator

The last thing we have to do is implement the GetEnumerator method. I won't devote the space to explain it here since the second article in this series covered it in depth. Basically, you just have to return an IEnumerator instance:


public IEnumerator GetEnumerator() 
{
  return new ListEnumerator(this);
}

public class ListEnumerator : IEnumerator 
{
  private int idx = -1;
  private  LinkedList linkedList;
  public ListEnumerator(LinkedList linkedList) 
  {
    this.linkedList = linkedList;
  }
  public void Reset() 
  {
    idx = -1;
  }
  public object Current 
  {
    get 
    {
      if (idx > -1)
        return 
          linkedList[idx];
      else
        return -1;
    }
  }
  public bool MoveNext() 
  {
    idx++;
    if (idx < linkedList.Count)
      return true;
    else
      return false;
  }
}

The singly linked list now fully implements the IList interface. It supports enumeration of its elements with the foreach statement. It allows for complex data binding with .NET iterative or list controls such as a DataGrid, a Repeater or a DropDownList. And best of all, by implementing against IList, our linked list class has now become a data source that can be used predictably throughout the project.

Stressing LinkedList

Let's stress the new class. In a console application that references the LinkedList class, instantiate it and populate it with five string values:


LinkedList myList = new LinkedList();
myList.Add("Alpha");
myList.Add("Beta");
myList.Add("Gamma");
myList.Add("Delta");
myList.Add("Epsilon");
Console.WriteLine("Loaded " + myList.Count.ToString() + 
                  " items into list.");

If you run the program you should see the message "Loaded 5 items into list." Since our class now supports the foreach statement we can easily enumerate the elements in the collection and write them out to the console:


foreach (object o in myList) {
    string s = (string)o;
    Console.WriteLine(s);
}

If we want to remove an item from the middle (the "Gamma" string value at index position 2) we would call:

myList.RemoveAt(2);

Now let's remove the first and last elements from the collection and print out the remaining elements to the console:


myList.RemoveAt(0);
myList.Remove("Epsilon");
foreach (object o in myList) {
  string s = (string)o;
  Console.WriteLine(s);
}

The two remaining strings "Beta" and "Delta" print out to the console.

Conclusion

In this article we took a simple singly linked list and turned it into a robust .NET collection class. We did that by implementing against the IList interface, which requires us to implement certain methods and properties that guarantee our class will behave the way a collection class should in the .NET Framework. You now have everything you need to implement IList in your own projects.

Related Links

James Still James Still is an experienced software developer in Portland, Oregon. He collaborated on "Visual C# .NET" (Wrox) and has immersed himself in .NET since the Beta 1 version was released.


Return to ONDotnet.com

Copyright © 2009 O'Reilly Media, Inc.