Beginner's .NET Micro Framework: Collections

Quick Look — Collections implement traditional data management structures that can be useful in a variety of situations, allowing easy storage, retrieval and manipulation of data contained within them. We will explore the four main collections within the .NET Micro Framework's System.Collections namespace: Queues, Stacks, Maps and Lists.

Queue

A Queue represents a sequence of values that are added to the back of the queue and removed from the front of the queue; its operation is summarily described as First-In, First Out:

While the class contains more methods and properties than described here, the following is a list of pertinent ones that you'll most commonly use:

  • Count contains the number of items in the queue
  • Enqueue() adds an item to the back of queue
  • Dequeue() removes and returns the item at the front of the queue. If the queue is empty, an exception may be thrown
  • Peek() returns the item at the front of the queue without removing it
  • Clear() removes all items in the queue
Queue myQueue = new Queue();  
myQueue.Enqueue("Hello");  
myQueue.Enqueue("World");  
while(myQueue.Count != 0) {  
    Console.Write("{0} ", (string)myQueue.Dequeue());
}
// Output: Hello World

One important thing to note is that items returned from the queue must be boxed back to its original type. Unfortunately, the .NET Micro Framework does not support generics, so you're left either casting the return object or subclassing System.Collections.Queue to return the type you want.

Stack

A Stack has the opposite effect of a queue - items pushed onto the top of the stack are available immediately for retrieval, while items pushed onto the stack earlier are popped off the stack in reversed order to when they were pushed; this structure is also known as Last-In, First-Out (LIFO):

The stack has a similar interface to a queue:

  • Count contains the number of items in the stack
  • Push() adds an item to the top of the stack
  • Pop() removes and returns the item at the top of the stack. If the stack is empty, an exception may be thrown
  • Peek() returns the item on the top of the stack without removing it
  • Clear() removes all items in the stack
Stack myStack = new Stack();  
myStack.Push("Hello");  
myStack.Push("World");  
while(myStack.Count != 0) {  
    Console.Write("{0} ", (string)myStack.Pop());
}
// Output: World Hello

As is with the queue, items popped off the stack must be boxed back into the original type.

Hashtable

In a Hashtable, whereas the queue and stack are sequential access structures (items being added and removed one-by-one), the hashtable presents a random access interface; any item added to the table may be accessed at any time and is also known as a map or dictionary. Items in the table consist of key-value pairs and are indexed according to a hash of the key-value pair.

  • Count returns the number of items in the dictionary
  • Add() adds an key-value pair to the dictionary
  • Remove() removes a single item from the dictionary
  • Clear() removes all items from the dictionary

When accessing this data structure, you can access it much like an array, where keys represent the index and values represent the contents of the item:

Hashtable ht = new Hashtable();  
ht.Add("Manager", "John Smith");  
ht.Add("Storeroom", "Joe Bloggs");  
ht.Add("Cashier", "Jane Jones");

Console.WriteLine("The Manager is: {0}", (string)ht["Manager"]);  
Console.WriteLine("Employees:");  
foreach(DictionaryEntry de in ht) {  
    Console.WriteLine("\t{0}", (string)de.Value);
}

// ## Output ##
// The Manager is: John Smith
// Employees:
//     John Smith
//     Joe Bloggs
//     Jane Jones

ArrayList

An ArrayList is a data structure which allows you to insert, remove and retrieve data to and from any position in the array. Also known as a linked-list, the collection grows according to the number of items placed in it.

Because the list is so easy to manipulate, there is quite a bit more to the interface than the other collections examined previously:

  • Count contains the number of items in the list
  • Add() adds an item to the back of the list (at index ArrayList.Count)
  • Insert() adds an item to the list at the specified index, shifting the items following the specified index back by one
  • Contains() determines whether an item is in the list
  • IndexOf() determines where in the list an item is and gives you the index
  • Remove() removes the first occurrence of the item in the list
  • RemoveAt() removes the item at the specified index, shifting the items following the specified index forward by one
public static void Main()  
{
    ArrayList list = new ArrayList();
    list.Add(5);                 PrintList(list);
    list.Add(27);                PrintList(list);
    list.Insert(1, 53);          PrintList(list);
    list.Insert(list.Count, 98); PrintList(list);
    list.Add(27);                PrintList(list);
    list.RemoveAt(1);            PrintList(list);
    list.Remove(27);             PrintList(list);

    Console.WriteLine("Item at index 2 is: {0}", list[2]);
}

public static void PrintList(ArrayList list)  
{
    foreach(int i in list) {
        Console.Write("{0}, ", i);
    }
    Console.WriteLine();
}
// ## Output ##
// 5,
// 5, 27,
// 5, 53, 27
// 5, 53, 27, 98
// 5, 53, 27, 98, 27
// 5, 27, 98, 27
// 5, 98, 27
// Item at index 2 is: 27

Notes

One main point to consider when using collections in a micro framework device is that of memory consumption. Each collection carries overhead — data that serves no other purpose than to facilitate the items you store in the collection. For example, inserting hundreds of items in an ArrayList will quickly use up most of the memory on a Netduino.

There is however a trick to increasing the size of your collections: by forcing the Garbage Collector to run (System.Diagnostics.Debug.GC(true)), you can clear away some of the transient overhead. The downside is that you must wait for the Garbage Collector to finish, so you are basically trading memory consumption for time. Depending on your application, this may be perfectly suitable.