Section 9.6. ListT

9.6. List<T>

The classic problem with the Array type is its fixed size. If you don't know in advance how many objects an array will hold, you run the risk of declaring either too small an array (and running out of room) or too large an array (and wasting memory).

Your program might be asking the user for input, or gathering input from a web site. As it finds objects (strings, books, values, etc.), you will add them to the array, but you have no idea how many objects you'll collect in any given session. The classic fixed-size array is not a good choice, as you can't predict how large an array you'll need.

The List class is an array whose size is dynamically increased as required. Lists provide a number of useful methods and properties for their manipulation. Some of the most important are shown in Table 9-3.

Table 9-3. List methods and properties

Method or property	Purpose
Capacity	Property to get or set the number of elements the List can contain. This value is increased automatically if count exceeds capacity. You might set this value to reduce the number of reallocations, and you may call trim( ) to reduce this value to the actual Count.
Count	Property to get the number of elements currently in the array.
Item( )	Gets or sets the element at the specified index. This is the indexer for the List class.[4]
Add( )	Public method to add an object to the List.
AddRange( )	Public method that adds the elements of an ICollection to the end of the List.
BinarySearch( )	Overloaded public method that uses a binary search to locate a specific element in a sorted List.
Clear( )	Removes all elements from the List.
Contains( )	Determines if an element is in the List.
CopyTo( )	Overloaded public method that copies a List to a one-dimensional array.
Exists( )	Determines if an element is in the List.
Find( )	Returns the first occurrence of the element in the List.
FindAll( )	Returns all the specified elements in the List.
GetEnumerator( )	Overloaded public method that returns an enumerator to iterate through a List.
Getrange( )	Copies a range of elements to a new List.
IndexOf( )	Overloaded public method that returns the index of the first occurrence of a value.
Insert( )	Inserts an element into the List.
InsertRange( )	Inserts the elements of a collection into the List.
LastIndexOf( )	Overloaded public method that returns the index of the last occurrence of a value in the List.
Remove( )	Removes the first occurrence of a specific object.
RemoveAt( )	Removes the element at the specified index.
RemoveRange( )	Removes a range of elements.
Reverse( )	Reverses the order of elements in the List.
Sort( )	Sorts the List.
ToArray( )	Copies the elements of the List to a new array.
trimToSize( )	Sets the capacity of the actual number of elements in the List.

^[4] The idiom in the FCL is to provide an Item element for collection classes which is implemented as an indexer in C#.

When you create a List, you don't define how many objects it will contain. Add to the List using the Add( ) method, and the list takes care of its own internal bookkeeping, as illustrated in Example 9-13.

Example 9-13. Working with List

#region Using directives using System; using System.Collections.Generic; using System.Text; #endregion namespace ListCollection {    // a simple class to store in the List    public class Employee    {       private int empID;       public Employee( int empID )       {          this.empID = empID;       }       public override string ToString( )       {          return empID.ToString( );       }       public int EmpID       {          get          {             return empID;          }          set          {             empID = value;          }       }    }    public class Tester    {       static void Main( )       {          List<Employee> empList = new List<Employee>( );          List<int> intList = new List<int>( );          // populate the List          for ( int i = 0; i < 5; i++ )          {             empList.Add( new Employee( i + 100 ) );             intList.Add( i * 5 );          }          // print all the contents          for ( int i = 0; i < intList.Count; i++ )          {             Console.Write( "{0} ", intList[i].ToString( ) );          }          Console.WriteLine( "\n" );          // print all the contents of the Employee List          for ( int i = 0; i < empList.Count; i++ )          {             Console.Write( "{0} ", empList[i].ToString( ) );          }          Console.WriteLine( "\n" );          Console.WriteLine( "empList.Capacity: {0}",             empList.Capacity );       }    } } Output: 0 5 10 15 20 100 101 102 103 104 empArray.Capacity: 16

With an Array class, you define how many objects the array will hold. If you try to add more than that, the Array class will throw an exception. With a List, you don't declare how many objects the List will hold. The List has a property, Capacity , which is the number of elements the List is capable of storing:

public int Capacity { get; set; }

The default capacity is 16. When you add the 17th element, the capacity is automatically doubled to 32. If you change the for loop to:

for (int i = 0;i<17;i++)

the output looks like this:

0 5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 empArray.Capacity: 32

You can manually set the capacity to any number equal to or greater than the count. If you set it to a number less than the count, the program will throw an exception of type ArgumentOutOfRangeException.

9.6.1. Implementing IComparable

Like all collections, the List implements the Sort( ) method, which allows you to sort any objects that implement IComparable. In the next example, you'll modify the Employee object to implement IComparable:

public class Employee : IComparable<Employee>

To implement the IComparable<Employee> interface, the Employee object must provide a CompareTo() method:

public int CompareTo(Employee rhs) {    return this.empID.CompareTo(r.empID); }

The CompareTo( ) method takes an Employee as a parameter. We know this is an Employee because this is a type-safe collection. The current Employee object must compare itself to the Employee passed in as a parameter and return -1 if it is smaller than the parameter, 1 if it is greater than the parameter, and 0 if it is equal to the parameter. It is up to Employee to determine what smaller than, greater than, and equal to mean. In this example, you delegate the comparison to the empId member. The empId member is an int and uses the default CompareTo( ) method for integer types, which will do an integer comparison of the two values.

The System.Int32 class implements IComparable<Int32>, so you may delegate the comparison responsibility to integers.

You are now ready to sort the array list of employees, empList. To see if the sort is working, you'll need to add integers and Employee instances to their respective arrays with random values. To create the random values, you'll instantiate an object of class Random; to generate the random values, you'll call the Next( ) method on the Random object, which returns a pseudorandom number. The Next( ) method is overloaded; one version allows you to pass in an integer that represents the largest random number you want. In this case, you'll pass in the value 10 to generate a random number between 0 and 10:

Random r = new Random(); r.Next(10);

Example 9-14 creates an integer array and an Employee array, populates them both with random numbers, and prints their values. It then sorts both arrays and prints the new values.

Example 9-14. Sorting an integer and an employee array

#region Using directives using System; using System.Collections.Generic; using System.Text; #endregion namespace IComparable {    // a simple class to store in the array    public class Employee : IComparable<Employee>    {       private int empID;       public Employee( int empID )       {          this.empID = empID;       }       public override string ToString( )       {          return empID.ToString( );       }       public bool Equals( Employee other )       {          if ( this.empID == other.empID )          {             return true;          }          else          {             return false;          }       }       // Comparer delegates back to Employee       // Employee uses the integer's default       // CompareTo method       public int CompareTo( Employee rhs )       {          return this.empID.CompareTo( rhs.empID );       }    }    public class Tester    {       static void Main( )       {          List<Employee> empArray = new List<Employee>( );          List<Int32> intArray = new List<Int32>( );          // generate random numbers for           // both the integers and the          // employee id's          Random r = new Random( );          // populate the array          for ( int i = 0; i < 5; i++ )          {             // add a random employee id             empArray.Add( new Employee( r.Next( 10 ) + 100 ) );             // add a random integer             intArray.Add( r.Next( 10 ) );          }          // display all the contents of the int array          for ( int i = 0; i < intArray.Count; i++ )          {             Console.Write( "{0} ", intArray[i].ToString( ) );          }          Console.WriteLine( "\n" );          // display all the contents of the Employee array          for ( int i = 0; i < empArray.Count; i++ )          {             Console.Write( "{0} ", empArray[i].ToString( ) );          }          Console.WriteLine( "\n" );          // sort and display the int array          intArray.Sort( );          for ( int i = 0; i < intArray.Count; i++ )          {             Console.Write( "{0} ", intArray[i].ToString( ) );          }          Console.WriteLine( "\n" );          // sort and display the employee array          Employee.EmployeeComparer c = Employee.GetComparer( );          empArray.Sort(c);          empArray.Sort( );          // display all the contents of the Employee array          for ( int i = 0; i < empArray.Count; i++ )          {             Console.Write( "{0} ", empArray[i].ToString( ) );          }          Console.WriteLine( "\n" );       }    } } Output: 4 5 6 5 7  108 100 101 103 103  4 5 5 6 7  100 101 103 103 108

The output shows that the integer array and Employee array were generated with random numbers. When sorted, the display shows the values have been ordered properly.

9.6.2. Implementing IComparer

When you call Sort( ) on the List, the default implementation of IComparer is called, which uses QuickSort to call the IComparable implementation of CompareTo() on each element in the List.

You are free to create your own implementation of IComparer, which you might want to do if you need control over how the sort ordering is defined. In the next example, you will add a second field to Employee, yearsOfSvc. You want to be able to sort the Employee objects in the List on either field, empID or yearsOfSvc.

To accomplish this, create a custom implementation of IComparer, which you pass to the Sort() method of the List. This IComparer class, EmployeeComparer, knows about Employee objects and knows how to sort them.

EmployeeComparer has the WhichComparison property, of type Employee. EmployeeComparer.ComparisonType:

public Employee.EmployeeComparer.ComparisonType    WhichComparison  {    get{return whichComparison;}    set{whichComparison = value;} }

ComparisonType is an enumeration with two values, empID or yearsOfSvc (indicating that you want to sort by employee ID or years of service, respectively):

public enum ComparisonType {    EmpID,    YearsOfService };

Before invoking Sort( ), create an instance of EmployeeComparer and set its ComparisionType property:

Employee.EmployeeComparer c = Employee.GetComparer();  c.WhichComparison=Employee.EmployeeComparer.ComparisonType.EmpID; empArray.Sort(c);

When you invoke Sort( ), the List calls the Compare method on the EmployeeComparer, which in turn delegates the comparison to the Employee.CompareTo() method, passing in its WhichComparison property:

public int Compare( Employee lhs, Employee rhs ) {     return lhs.CompareTo( rhs, WhichComparison ); }

The Employee object must implement a custom version of CompareTo( ), which takes the comparison and compares the objects accordingly:

public int CompareTo(     Employee rhs,      Employee.EmployeeComparer.ComparisonType which) {    switch (which)    {       case Employee.EmployeeComparer.ComparisonType.EmpID:          return this.empID.CompareTo(rhs.empID);       case Employee.EmployeeComparer.ComparisonType.Yrs:          return this.yearsOfSvc.CompareTo(rhs.yearsOfSvc);    }    return 0; }

The complete source for this example is shown in Example 9-15. The integer array has been removed to simplify the example, and the output of the employee's ToString( ) method has been enhanced to enable you to see the effects of the sort.

Example 9-15. Sorting an array by employees' IDs and years of service

#region Using directives using System; using System.Collections.Generic; using System.Text; #endregion namespace IComparer {    public class Employee : IComparable<Employee>    {       private int empID;       private int yearsOfSvc = 1;       public Employee( int empID )       {          this.empID = empID;       }       public Employee( int empID, int yearsOfSvc )       {          this.empID = empID;          this.yearsOfSvc = yearsOfSvc;       }       public override string ToString( )       {          return "ID: " + empID.ToString( ) +          ". Years of Svc: " + yearsOfSvc.ToString( );       }       public bool Equals( Employee other )       {          if ( this.empID == other.empID )          {             return true;          }          else          {             return false;          }       }       // static method to get a Comparer object       public static EmployeeComparer GetComparer( )       {          return new Employee.EmployeeComparer( );       }       // Comparer delegates back to Employee       // Employee uses the integer's default       // CompareTo method       public int CompareTo( Employee rhs )       {          return this.empID.CompareTo( rhs.empID );       }       // Special implementation to be called by custom comparer       public int CompareTo(          Employee rhs,          Employee.EmployeeComparer.ComparisonType which )       {          switch ( which )          {             case Employee.EmployeeComparer.ComparisonType.EmpID:                return this.empID.CompareTo( rhs.empID );             case Employee.EmployeeComparer.ComparisonType.Yrs:                return this.yearsOfSvc.CompareTo( rhs.yearsOfSvc );          }          return 0;       }       // nested class which implements IComparer       public class EmployeeComparer : IComparer<Employee>       {                    // private state variable          private Employee.EmployeeComparer.ComparisonType             whichComparison;          // enumeration of comparison types          public enum ComparisonType          {             EmpID,             Yrs          };          public  bool Equals( Employee lhs, Employee rhs )          {             return this.Compare( lhs, rhs ) == 0;          }          public  int GetHashCode(Employee e)          {             return e.GetHashCode( );          }          // Tell the Employee objects to compare themselves          public int Compare( Employee lhs, Employee rhs )          {              return lhs.CompareTo( rhs, WhichComparison );          }          public Employee.EmployeeComparer.ComparisonType             WhichComparison           {             get{return whichComparison;}             set{whichComparison = value;}          }       }    }    public class Tester    {       static void Main( )       {          List<Employee> empArray = new List<Employee>( );          // generate random numbers for           // both the integers and the          // employee id's          Random r = new Random( );          // populate the array          for ( int i = 0; i < 5; i++ )          {             // add a random employee id             empArray.Add(                new Employee(                   r.Next( 10 ) + 100, r.Next( 20 )                )             );          }          // display all the contents of the Employee array          for ( int i = 0; i < empArray.Count; i++ )          {             Console.Write( "\n{0} ", empArray[i].ToString( ) );          }          Console.WriteLine( "\n" );          // sort and display the employee array          Employee.EmployeeComparer c = Employee.GetComparer( );          c.WhichComparison =              Employee.EmployeeComparer.ComparisonType.EmpID;          empArray.Sort( c );          // display all the contents of the Employee array          for ( int i = 0; i < empArray.Count; i++ )          {             Console.Write( "\n{0} ", empArray[i].ToString( ) );          }          Console.WriteLine( "\n" );          c.WhichComparison = Employee.EmployeeComparer.ComparisonType.Yrs;          empArray.Sort( c );          for ( int i = 0; i < empArray.Count; i++ )          {             Console.Write( "\n{0} ", empArray[i].ToString( ) );          }          Console.WriteLine( "\n" );       }    } } Output: ID: 103. Years of Svc: 11 ID: 108. Years of Svc: 15 ID: 107. Years of Svc: 14 ID: 108. Years of Svc: 5 ID: 102. Years of Svc: 0 ID: 102. Years of Svc: 0 ID: 103. Years of Svc: 11 ID: 107. Years of Svc: 14 ID: 108. Years of Svc: 15 ID: 108. Years of Svc: 5 ID: 102. Years of Svc: 0 ID: 108. Years of Svc: 5 ID: 103. Years of Svc: 11 ID: 107. Years of Svc: 14 ID: 108. Years of Svc: 15

The first block of output shows the Employee objects as they are added to the List. The employee ID values and the years of service are in random order. The second block shows the results of sorting by the employee ID, and the third block shows the results of sorting by years of service.

If you are creating your own collection, as in Example 9-11, and wish to implement IComparer, you may need to ensure that all the types placed in the list implement IComparer (so that they may be sorted), by using constraints as described earlier.