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.
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.
|
Related Reading Programming .NET Components |
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 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.
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.");
}
}
|
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++;
}
}
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.
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.
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.
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.