.NET 1.1

The ArrayList Collection

The thirty-seventh part of the C# Fundamentals tutorial describes the use of the ArrayList class. This general-purpose collection class provides the ability to create and manipulate a group of related objects as if they were a variable-length array.

The ArrayList Collection

When using standard one-dimensional arrays, the array is predefined to be a fixed length. Once the length is set, it may not be altered. This can be a drawback if the number of elements to be held in an array is variable and unknown until run-time.

The ArrayList is a general-purpose collection structure provided by the .NET framework. It provides a group of objects that is not fixed in size and it includes flexible functionality to control the contents of the collection. This includes the ability to modify ranges of values, perform sort operations and search the contents of the ArrayList.

Implemented Collection Interfaces

In the previous article of the C# Fundamentals tutorial I reviewed the main interfaces used by collections. The ArrayList implements two of these, namely ICollection and IList. This means that all of the properties and methods defined by ICollection and IList are also supported by ArrayList. These behaviours are not addressed in this article. Instead, the additional behaviour that is specific to the ArrayList class is considered.

Declaring an ArrayList

Constructors

The ArrayList class provides three standard constructors that allow a new ArrayList object to be instantiated and populated. The first constructor is the most basic, as it requires no parameters. The new collection is generated with the capacity to store several items. When extra items are added, the capacity of the collection doubles automatically. It doubles again each time the capacity of the ArrayList is exceeded. The Hashtable class is found in the System.Collections namespace so to execute the examples, add using System.Collections; to the source code.

If the maximum number of items that will be stored in an ArrayList is known before the collection is created, it is more efficient to declare the capacity required. If the size is underestimated and the stated capacity is exceeded, the capacity will still be doubled to accommodate extra items. To declare the initial capacity of an ArrayList an integer value is passed to the constructor.

The third constructor for the ArrayList allows the entire contents of the new collection to be initialised using the contents of any other array or collection that supports the ICollection interface. The array or collection is passed as a parameter to the constructor. Each item is added to the new ArrayList in the order that they are enumerated from the source collection. The following example demonstrates this by creating an array of strings that is used to initialise an ArrayList.

string[] fruitArray = new string[] {"Apple", "Banana", "Grape"};

ArrayList fruitCollection = new ArrayList(fruitArray);

// List collection items
foreach (string fruit in fruitCollection)
    Console.WriteLine(fruit);

/* OUTPUT

Apple
Banana
Grape

*/

ArrayList.Repeat

In some situations it may be useful to create a new ArrayList collection that is pre-populated with multiple instances of the same value or object. The static Repeat method provides this functionality by returning such a collection that can be assigned to an ArrayList.

ArrayList myCollection = ArrayList.Repeat("Item",5);

// List collection items
foreach (string s in myCollection)
    Console.WriteLine(s);
    
/* OUTPUT

Item
Item
Item
Item
Item

*/

NB: If an ArrayList is populated with a reference type using Repeat, all of the items in the collection will be references to the same object in memory. ie. changing the properties of one item in the collection will give the impression that all of the other items have also changed because they actually are the same object. This does not occur when populating with value types.

Modifying ArrayList Contents

The ArrayList is designed to provide a flexible array-like collection of objects. This includes the provision of many methods that permit modification of the ArrayList's contents. The following sections describe the modification methods that have not been covered in the earlier article relating to collection interfaces.

Adding Multiple Items

The ArrayList contains two methods that allow several items to be added in a single command. In each case, the additional items are held in a collection or array that implements the ICollection interface.

The AddRange method adds the entire contents of a collection to the end of an ArrayList. The ICollection object holding the items to be appended is passed as the only parameter of the method.

ArrayList myCollection = ArrayList.Repeat("Item",3);
ArrayList extraItems = ArrayList.Repeat("Extra",2);

// Add extra items
myCollection.AddRange(extraItems);

// List collection items
foreach (string s in myCollection)
    Console.WriteLine(s);

/* OUTPUT

Item
Item
Item
Extra
Extra

*/

The InsertRange method provides a similar function to AddRange. However, the method requires an additional parameter to indicate the index at which the new items should be inserted. Existing items in the ArrayList are moved to a higher index to allow the insertion.

ArrayList myCollection = ArrayList.Repeat("Item",3);
ArrayList extraItems = ArrayList.Repeat("Extra",2);

// Add extra items
myCollection.InsertRange(1,extraItems);

// List collection items
foreach (string s in myCollection)
    Console.WriteLine(s);

/* OUTPUT

Item
Extra
Extra
Item
Item

*/

Removing Multiple Items

ArrayLists allow a range of items to be deleted from a collection in a single command. This is achieved using the RemoveRange method. RemoveRange accepts two parameters. The first parameter specifies the index of the first item to be deleted. The second parameter indicates the number of concurrent collection entries to be erased.

ArrayList myCollection = ArrayList.Repeat("Item",5);

// Remove three items starting with the first item in the ArrayList
myCollection.RemoveRange(0,3);

// List collection items
foreach (string s in myCollection)
    Console.WriteLine(s);

/* OUTPUT

Item
Item

*/

Replacing Multiple Items

Often it is useful to replace the contents of part of an ArrayList with the items from another. This is achieved using the SetRange method. SetRange requires two parameters: the index of the first item to overwrite and the collection to be used to replace the existing entries from that position forwards. The replacement items must be in an ICollection-based array or collection.

ArrayList myCollection = ArrayList.Repeat("Item",5);
ArrayList newItems = ArrayList.Repeat("New",2);

// Overwrite items
myCollection.SetRange(1,newItems);

// List collection items
foreach (string s in myCollection)
    Console.WriteLine(s);

/* OUTPUT

Item
New
New
Item
Item

*/

Reversing ArrayList Items

The ArrayList class provides an interesting method named Reverse. In its simplest form the method simply reverses the order of all of the items in the collection. This is demonstrated in the following example.

ArrayList myCollection = new ArrayList(new string[]
    {"One", "Two", "Three", "Four", "Five"});

// Reverse items
myCollection.Reverse();

// List collection items
foreach (string s in myCollection)
    Console.WriteLine(s);

/* OUTPUT

Five
Four
Three
Two
One

*/

If only a section of the ArrayList contents are to be reversed whilst all other items are left in their original positions, two integer parameters are used with the Reverse method. The first parameter specifies the index number of the first item in the collection that is to be affected. The second parameter is used to determine how many items in the collection will be reversed. In the following example, the first and last entries in the ArrayList remain in place whilst the middle of the collection is reversed.

ArrayList myCollection = new ArrayList(new string[]
    {"One", "Two", "Three", "Four", "Five"});

// Reverse items
myCollection.Reverse(1,3);

// List collection items
foreach (string s in myCollection)
    Console.WriteLine(s);

/* OUTPUT

One
Four
Three
Two
Five

*/

Querying ArrayList Contents

As the ArrayList implements the IList interface, it supports the two standard query methods for lists. These are the Contains and IndexOf methods that have been described in an earlier article. The ArrayList method also provides further methods that can be used to search the contents of the collection. These are described in the following sections.

Retrieving an Entry's Index

The IList interface's IndexOf method searches for a specified object within a list collection and, if found, returns the index of the first matching item. This functionality is extended for ArrayLists with the addition of two overloaded versions of the method.

The first overloaded version of IndexOf accepts an additional integer parameter. This specifies the index position from which the search should commence. Any items with a lower index are not included in the search. This provides an advantage over the basic version of the method in that multiple occurrences of the same value may be easily located.

The following example loops until every occurrence of the text, "Find me", is found. The loop ends when the index value becomes -1, indicating that the search object was not found.

ArrayList myCollection = new ArrayList(new string[]
	{"One", "Two", "Find Me", "Three", "Find Me", "Four", "Find Me", "Five"});

int location = -1;

do
{
    location = myCollection.IndexOf("Find Me", location + 1);
    if (location != -1)
        Console.WriteLine("Found at index {0}", location);
}
while (location != -1);

/* OUTPUT

Found at index 2
Found at index 4
Found at index 6

*/

The second overloaded IndexOf method adds a second integer parameter. The second parameter determines the size of the range to search within the ArrayList. Items that appear in the collection earlier than the first index or after the end of the search range are not matched.

ArrayList myCollection = new ArrayList(new string[]
    {"One", "Two", "Three", "Four", "Five"});

Console.WriteLine(myCollection.IndexOf("One",1,3));     // Outputs -1
Console.WriteLine(myCollection.IndexOf("Three",1,3));   // Outputs 2
Console.WriteLine(myCollection.IndexOf("Five",1,3));    // Outputs -1

Often it is more useful to search for the last occurrence of an item in a collection, or a range within a collection, rather than the first. Using the ArrayList's LastIndexOf method such a search can be performed. The parameters that can be specified match those of the IndexOf method. However, it should be noted that when a second integer parameter is used to specify the range size that this range starts at the specified last index and counts backwards.

ArrayList myCollection = new ArrayList(new string[]
    {"One", "Two", "Three", "Four", "Five"});

Console.WriteLine(myCollection.LastIndexOf("One"));     // Outputs 0
Console.WriteLine(myCollection.LastIndexOf("One",3,3)); // Outputs -1

Sorting an ArrayList

Some ArrayList query operations are only useful when the contents of the collection have been sorted. The ArrayList's Sort method can be used to order items in an array in various manners. If the Sort method is used without parameters, the items within the array are relocated to place them in ascending order. In the case of numeric and string values, this order is numeric or alphabetic.

When an ArrayList contains objects, each object must implement the IComparer interface and provide compatible comparisons. This interface provides the information needed to determine the ordering. The ordering of objects using IComparer is beyond the scope of a basic tutorial. It is important to note that the object types must be comparable. It is not possible, for example, to sort an ArrayList containing both alphanumeric strings and integer values.

The following example uses the Sort method to alphabetically order an ArrayList containing string values:

ArrayList myCollection = new ArrayList(new string[]
	{"One", "Two", "Three", "Four", "Five"});

// Sort items
myCollection.Sort();

// List collection items
foreach (string s in myCollection)
    Console.WriteLine(s);

/* OUTPUT

Five
Four
One
Three
Two

*/

NB: There are further overloaded versions of Sort. These allow different sorting options to be specified and permit the sorting of a range of values in an ArrayList. However, these topics are more complex than can be explained in a fundamentals tutorial.

Performing a Binary Search

A binary search is a much faster and more efficient method by which an item in a sorted list can be found. Instead of looping through every value in the collection, the middle value is checked. If this value is larger than the value to find, another item half way between the low value and the initial lookup is checked. If the value is smaller, the opposite occurs. Each time an item is compared in the ArrayList, half of the remaining items can be immediately discounted as potential matches. To demonstrate the efficiency difference, a search of a 65,536 item ArrayList using IndexOf may require 65,536 individual comparisons. When using a binary search algorithm, the maximum number of tests is just sixteen.

The BinarySearch method allows this fast searching once an ArrayList has been sorted. If the ArrayList is not sorted before the operation then the results of the method can be incorrect. It should be noted that when duplicates exist in the collection, the item found by a binary search is not necessarily the one with the lowest index number.

ArrayList myCollection = new ArrayList(new string[]
	{"One", "Two", "Three", "Four", "Five"});

// Sort items
myCollection.Sort();

// List collection items
foreach (string s in myCollection)
    Console.WriteLine(s);

// Perform a search
Console.WriteLine("'One' found at index {0}", myCollection.BinarySearch("One"));

/* OUTPUT

Five
Four
One
Three
Two
'One' found at index 2

*/

Extracting a Range of Values

If you need to extract a range of values from an ArrayList, this can be achieved using the GetRange method. The method allows a start index and number of items to be specified. The corresponding group of items is returned in a new ArrayList.

ArrayList myCollection = new ArrayList(new string[]
	{"One", "Two", "Three", "Four", "Five"});

// Extract items
ArrayList extract = myCollection.GetRange(1,3);

// List collection items
foreach (string s in extract)
    Console.WriteLine(s);

/* OUTPUT

Two
Three
Four

*/

Copying an ArrayList

Copying to an Array

As the ArrayList class implements the IList interface, it supports the use of the CopyTo method that copies the contents of a collection into a one-dimensional array. In addition to the basic CopyTo functionality, the ArrayList provides two overloaded versions of the method. The first requires no parameters and simply copies to entire contents of the collection into an existing array. The array must be compatible with the types of object in the ArrayList to avoid an exception being thrown.

ArrayList myCollection = new ArrayList(new string[]
    {"One", "Two", "Three", "Four", "Five"});

string[] array = new string[5];

// Copy items
myCollection.CopyTo(array);

// List array items
foreach (string s in array)
	Console.WriteLine(s);

/* OUTPUT

One
Two
Three
Four
Five

*/

The second overloaded CopyTo method accepts four parameters. The first parameter specifies the zero-based index in the ArrayList being copying from. The second parameter is the ArrayList object itself. The third parameter holds the first index in the target array to receive copied items and the final parameter determines how many entries from the collection should be copied. This allows you to copy a subset of data from the ArrayList into an existing array.

ArrayList myCollection = new ArrayList(new string[]
	{"One", "Two", "Three", "Four", "Five"});

string[] array = new string[5];

// Copy items
myCollection.CopyTo(1,array,0,3);

// List array items
foreach (string s in array)
    Console.WriteLine(s);

/* OUTPUT

Two
Three
Four

*/

Another function exists that permits an ArrayList's contents to be extracted into an array. The ToArray method returns a new array of objects. This means that the array does not need to be created prior to the copy. However, the basic method only generates an array of basic object instances. In the following example the ArrayList items are copied to a series of objects; each a boxed string. The ToString method, though not strictly necessary, makes it clear that the objects are being converted to strings for output.

ArrayList myCollection = new ArrayList(new string[]
	{"One", "Two", "Three", "Four", "Five"});

// Copy items
object[] array = myCollection.ToArray();

// List array items
foreach (object o in array)
    Console.WriteLine(o.ToString());

/* OUTPUT

One
Two
Three
Four
Five

*/

If the ArrayList contains a collection of items that are all of the same type, this type may be specified when using the ToArray method. If every item in the collection can be successfully cast to the specified type then the copying creates a new array of that type. To indicate the type to the compiler, the typeof command is used. This command accepts the relevant class or data type name as a parameter. It is important to note that the method still returns an array of objects. However, because the types of the array elements are consistent, the entire array may then be cast to the correct type.

In the following example, note the use of typeof(string) to specify the type of each array element to copy. Also note the casting of the object array to a string array with the case operator (string[]).

ArrayList myCollection = new ArrayList(new string[]
	{"One", "Two", "Three", "Four", "Five"});

// Copy items
string[] array = (string[])myCollection.ToArray(typeof(string));

// List array items
foreach (string s in array)
    Console.WriteLine(s);

/* OUTPUT

One
Two
Three
Four
Five

*/

ArrayList Capacity

As previously mentioned, when an ArrayList is first declared, it is created with a predetermined size. The size may be specified directly in the constructor, indirectly due to the manner in which the ArrayList is created or defaulted to a size determined by the .NET framework.

As items are added to the ArrayList and the capacity is exceeded, the capacity automatically doubles to allow the new additions. Each time this occurs, there is an overhead in allocation of new memory and copying of ArrayList data. It is advisable, therefore, to set the capacity of an ArrayList when the maximum size of the collection is known and when the number of entries that may be used is reasonably stable.

The capacity of an ArrayList can be obtained and modified using the Capacity property. This property holds an integer value.

ArrayList myCollection = new ArrayList();

int capacity = myCollection.Capacity;
Console.WriteLine("Default capacity is {0} items", capacity);

myCollection.Capacity = 40;
capacity = myCollection.Capacity;
Console.WriteLine("New capacity is {0} items", capacity);

/* OUTPUT

Default capacity is 16 items
New capacity is 40 items

*/

Once an ArrayList has been fully populated and no further items will be added, the memory allocated to the unused part of the collection can be reclaimed. The TrimToSize method sets the capacity of the collection to match the current contents.

ArrayList myCollection = new ArrayList();

myCollection.Add("One");
myCollection.Add("Two");
myCollection.Add("Three");
myCollection.Add("Four");
myCollection.Add("Five");

int capacity = myCollection.Capacity;
Console.WriteLine("Initial capacity is {0} items", capacity);

myCollection.TrimToSize();
capacity = myCollection.Capacity;
Console.WriteLine("New capacity is {0} items", capacity);

/* OUTPUT

Initial capacity is 16 items
New capacity is 5 items

*/

ArrayList Wrappers

Creating a Fixed Size ArrayList

It is possible to create an ArrayList that has a fixed size using the static FixedSize method. This method is executed against an existing ArrayList to return a new, fixed size version. The fixed size collection is actually a wrapper for the original collection so any changes made to either ArrayList are mirrored exactly in the other. However, any attempt to add a new item to the fixed size variant causes a NotSupportedException to be thrown.

NB: New items may be added to the underlying ArrayList. These will be added to the fixed size collection without an exception occurring.

ArrayList myCollection = new ArrayList(new string[]
    {"One", "Two", "Three", "Four", "Five"});

ArrayList myFixed = ArrayList.FixedSize(myCollection);

Console.WriteLine(myFixed.IsFixedSize);     // Outputs "True"

myFixed.Add("Six");                         // Throws a NotSupportedException

Creating a Read-Only ArrayList

In some cases, a read-only wrapper for an ArrayList is not restrictive enough. Occasionally it is useful to create a wrapper collection that is read-only. This type of ArrayList, generated by the static ReadOnly method, causes a NotSupportedException if any attempt is made to modify its contents. The underlying ArrayList may be modified however.

ArrayList myCollection = new ArrayList(new string[]
    {"One", "Two", "Three", "Four", "Five"});

ArrayList myReadOnly = ArrayList.ReadOnly(myCollection);

Console.WriteLine(myReadOnly.IsFixedSize);  // Outputs "True"
Console.WriteLine(myReadOnly.IsReadOnly);   // Outputs "True"

myReadOnly[0] = "Apple";                    // Throws a NotSupportedException

Creating a Synchronised ArrayList

In the earlier article where collection interfaces were discussed, the concept of a thread-safe synchronised collection was described. In order to create a thread-safe ArrayList, a synchronised wrapper collection is generated using the static Synchronized method.

ArrayList myCollection = new ArrayList(new string[]
    {"One", "Two", "Three", "Four", "Five"});

ArrayList myThreadSafe = ArrayList.Synchronized(myCollection);

Console.WriteLine(myThreadSafe.IsSynchronized);	    // Outputs "True"

Providing ArrayList Functionality to Other IList Classes

The functionality provided by the ArrayList collection class is very flexible when reading, querying and adjusting a collection's contents. Functionality such as that provided by the BinarySearch, Sort and Reverse methods is useful in many situations. However, sometimes it is not appropriate to use an ArrayList in every situation, even when this functionality may be required.

The ArrayList class includes a static method named Adapter. This method is very powerful as is creates an ArrayList wrapper for other classes that implement the IList interface, including basic arrays. By wrapping a suitable array or collection, you can apply ArrayList functionality that is not usually available to the underlying class.

NB: Some functions of the ArrayList may cause a NotSupportedException. For example, it is not possible to add new items to an ArrayList that is a wrapper to a fixed size array.

string[] numbers = new string[]
    {"One", "Two", "Three", "Four", "Five"};

ArrayList wrapper = ArrayList.Adapter(numbers);

// Sort the ArrayList and underlying array
wrapper.Sort();

// List wrapper items
foreach (string s in wrapper)
    Console.WriteLine(s);

// Perform a search
Console.WriteLine("'One' found at index {0}", wrapper.BinarySearch("One"));

/* OUTPUT

Five
Four
One
Three
Two
'One' found at index 2

*/