.NET Collections

I l @ ve RuBoard

A general problem is the need to deal with several objects at once and to somehow keep track of them. There is never one employee, or one car, or generally one of anything. To this end, .NET provides several generic collections in the System.Collections namespace.

Collections in C# implement the IEnumerable interface. The IEnumerable interface allows for traversal over the elements contained with a given collection. The following collections will be covered in brief: stack, queue, and hashtable. Along with these basic collections, an implementation of a linked list that implements the IEnumerable interface and provides an IEnumerator for the elements is also presented.

For detailed information about generic collections, data structures, and algorithms, I suggest either Algorithms in C++ by Sedgewick or The Art of Computer Programming, Volume 3 by Donald Knuth.

Stack

A stack represents a basic FILO, First-in-Last-Out, container. The basic premise of a stack is to push elements onto the top of the stack and to pop elements off the top of the stack. In C#, the System.Collections.Stack (see Listing 2.2.1) also implements the IEnumerable interface, which allows for enumerating the contents of the stack.

Listing 2.2.1 `System.Collections.Stack`

 1: using System;  2: using System.Collections;  3:  4: public class StackTest {  5:  6:     public static void Main( ) {  7:  8:         Stack myStack = new Stack( );  9: 10:         for( int i = 0; i < 10; i++ ) 11:             myStack.Push(i); 12: 13:         for( int i = 0; i < 10; i++ ) 14:             Console.WriteLine( "{ 0} ", myStack.Pop( ) ); 15: 16: 17:         //Refill the stack and use an enumerator to list the elements 18:         for( int i = 0; i < 10; i++ ) 19:             myStack.Push(i); 20: 21:         foreach( int i in myStack ) 22:             Console.WriteLine( "{ 0} ", i ); 23:     } 24: }

The code in Listing 2.2.1 shows the basic use of a stack. Elements are pushed onto the stack and popped off in reverse order. Stacks are useful for recursive algorithms and can serve as place holders.

Queue

A queue represents a FIFO, first in first out, collection. Queues provide an Enqueue and Dequeue methods to add and remove elements to the queue. As with all .NET collections, the Queue collection also provides an IEnumerator interface. Listing 2.2.2 uses the Queue provided by .NET to demonstrate its basic use.

Listing 2.2.2 `Queue`

 1: using System;  2: using System.Collections;  3:  4: public class QueueTest {  5:  6:     public static void Main( ) {  7:  8:         Queue myQueue = new Queue( );  9: 10:         //Fill the queue 11:         for( int i = 0; i < 10; i++ ) 12:             myQueue.Enqueue( i ); 13: 14:         //Empty the queue 15:         for( int i = 0; i < 10; i++ ) 16:             Console.WriteLine( "{ 0} ", myQueue.Dequeue( ) ); 17: 18: 19:         //Fill the queue again 20:         for( int i = 0; i < 10; i++ ) 21:             myQueue.Enqueue( i ); 22: 23:         foreach( int i in myQueue ) 24:             Console.WriteLine( "{ 0} ", i ); 25:     } 26: }

Hashtable

A hashtable is useful when you need to store objects and access them with a given key. The seek time for a hashtable is O(1). Each key is used to generate a hash value that acts as an index for the item. When access to a specific element is required, the hash value of the key is computed and the element is accessed. A hashtable generally trades off memory space for speed and, depending on the use, a hashtable may fit the bill (see Listing 2.2.3).

Listing 2.2.3 `Hashtable`

 1: using System;  2: using System.Collections;  3:  4: struct Person {  5:     public Person( string f, string l ) {  FName = f; LName = l; }  6:     public string LName;  7:     public string FName;  8: }  9: 10: public class HashtableTest { 11: 12:     public static void Main( ) { 13: 14:         Hashtable People = new Hashtable( ); 15: 16:         //Add some people 17:         People.Add( "Smith", new Person( "Jim", "Smith" ) ); 18:         People.Add( "Jones", new Person( "Dawn", "Jones" ) ); 19:         People.Add( "Powell", new Person( "Bob", "Powell" ) ); 20: 21:         //Locate Jim Smith 22:         Person p = (Person)People["Smith"]; 23:         Console.WriteLine("{ 0}  { 1} ", p.FName, p.LName ); 24:     } 25: }

It is important to note that a hashtable will not allow for more than one item to share a key value. Doing so will cause the hashtable to throw an ArgumentException .

Roll Your Own: Linked List

To drive home the importance of interfaces and the extensibility of the .NET framework, a linked list collection is presented that implements the IEnumerable interface and provides an IEnumerator object. By providing the necessary interfaces, the foreach construct can be used to iterate through the contents of the linked list.

Although the linked list presented in Listing 2.2.4 is not by any means complete, the basic plumbing is in place. As an exercise, you should extend the functionality of the linked list. Example extensions include the ability to provide a method to add items at the end of the list or at any point in the list. It would also be of interest to locate a particular object within the list. (Hint: IComparable interface will come in handy.)

Listing 2.2.4 Linked List

 1: //File           :part02_35.cs   2: //Author   :Richard L. Weeks   3: //Purpose  :Implement a linked list that supports the IEnumerable interface   4:   5:   6:   7: using System;   8: using System.Collections;   9:  10:  11:  12: public class _node {  13:  14:   public _node next;  15:   public _node prev;  16:   public object value;  17:  18:   public _node( ) {  next = prev = null; value = null; }  19:   public _node( object o ) {  20:          value = o;  21:          next = prev = null;  22:   }  23:  24:   public _node( _node n ) {  25:         next = n.next;  26:         prev = n.prev;  27:         value = n.value;  28:   }  29: }  30:  31:  32: //Linked list enumerator  33: public class LinkedListEnumerator : IEnumerator {  34:  35:   private _node m_current = null;  36:   private _node m_begin   = null;  37:   private bool  m_last   = false;  38:  39:   public LinkedListEnumerator( _node n ) {  m_current = m_begin = n; }  40:  41:  42:   //Implement the IEnumerator interface  43:   public object Current {  44:          get {  return m_current.value; }  45:          set {  m_current.value = value; }  46:   }  47:  48:   public bool MoveNext( ) {  49:          if( m_last )  50:                 return false;  51:          else {  52:                 m_current = m_current.next;  53:                 m_last = m_current == m_begin ? true : false;  54:                 return true;  55:          }  56:   }  57:  58:   public void Reset( ) {  59:          m_current = m_begin;  60:          m_last = false;  61:   }  62: }  63:  64: public class LinkedList : IEnumerable {  65:  66:   private _node m_root = null;  67:  68:  69:   //Implement the IEnumerable interface method GetEnumerator( )  70:   public IEnumerator GetEnumerator( ) {  71:          return (IEnumerator)new LinkedListEnumerator( m_root.prev );  72:   }  73:  74:  75:   //Implement some basic methods  76:   public void AddHead( object o ) {  77:          _node newNode = new _node( o );  78:          if( m_root == null ) {  79:                 m_root = newNode;  80:                 m_root.next = m_root;  81:                 m_root.prev = m_root;  82:            } else {  83:                   newNode.next = m_root;  84:                   newNode.prev = m_root.prev;  85:                   m_root.prev.next = newNode;  86:                   m_root.prev = newNode;  87:                   m_root = newNode;  88:            }  89:   }  90: }  91:  92:  93:  94:  95: public class LinkedListTest {  96:  97:   public static void Main( ) {  98:  99: 100:          LinkedList l = new LinkedList( ); 101: 102:          for(int i = 0; i < 10; i++ ) 103:                 l.AddHead( i ); 104: 105:          foreach( int i in l ) 106:                 Console.WriteLine( i ); 107:   } 108: }

The linked list example demonstrates the basic concepts of implementing interfaces and how C# can use those interfaces seamlessly. Because the LinkedList class implements the IEnumerable interface and provides an IEnumerator entity, the foreach statement can be used to iterate through the contents of the linked list.