An Extensive Examination Of ArrayList in C#


Next Read : Why Strings Are Immutable In Dot Net?

We all use Arrays in c# and other programming languages. Array creates some limitations on design. First, Arrays are homogeneous i.e. you can store only one type of elements. Secondly, when using arrays you must specifically allocate a certain number of elements. Often developers want something more flexible – specially for uncertainty in size of collection. The .Net Framework Base Class Library provides such a data structure called ArrayList located in System.Collections Namespace.

ArrayList is nothing but a Heterogeneous and Self Re-Dimensioning Array :

Elements of different types can be added to the ArrayList. Further, we do not have to concern ourselves with redimensioning the ArrayList. All of this is handled automatically for us. An example of the ArrayList in action can be seen in the code snippet below.

Array List Example
Array List Example

Behind The Scenes :

Behind the scenes the ArrayList uses System.Array of type Object. An object array can hold elements of any type Since all types are derived from Object (either directly or indirectly). By default the size of this array is 16, although it can be defined in constructor or by assigning capacity property. Elements can be added to ArrayList using Add() Method. Behind the scenes , Add() method first compares the no of elements in array with its capacity. If adding the new element causes the count to exceed the capacity, the array is redimensioned and the capacity is automatically doubled.

Performance :

ArrayList provides some additional flexibility compared to array, but this flexibility comes at cost of performance, majorly if you store value types. The ArrayList’s internal array is of object type, so every value type is boxed and stored on heap and each ArrayList element is a reference to a boxed value type. When you access a value type element it is unboxed before you can use it.

The boxing and unboxing, along with the extra level of indirection that comes with using value types in an ArrayList, can hamper the performance of your application when using large ArrayLists with many reads and writes.

ArrayList Data Structure Memory Allocation
The ArrayList contains a contiguous block of object references

The above diagram shows the memory allocation for ArrayList.

The sel-redimensioning of ArrayList should not cause a performance degradation if compared to array. Because you can turn off self-redimensioning by specifying the initial capacity in constructor. If you dont know the exact size, you may have to re-size even with array also when the number of elements inserted increases the size of array.

Memory Allocation on Redimensioning:

Why the size of ArrayList gets doubled when it gets redimensioned? Its a classic computer science  problem to find out how much extra memory should be allocated when running out of space in some buffer.

One option is to allocate just one more element in the array when redimensioning. i.e. if the initial size of array was 10 and when adding 11th element, resize the array to 11. This approach conserves most of the memory but becomes very costly as redimensioning is required at insertion of every additional element.

Second option is to redimension the array 100 or 200 times larger than the current size. i.e. if array is initially allocated 10 element, before inserting 11th element resize it to 1000 elements. This approach greatly reduces the redimensioning overhead , but , if only a few more elements needs to be added, the extra allocated space is wasted.

So after trying various options, the true compromise is to just double the size of array when it becomes exhausted. This is the precise approach that ArrayList takes and its all done automatically for us.

Summary :

  1. ArrayList internally uses array of object type.
  2. ArrayList provides more flexibility than simple array.
  3. Precise size of ArrayList can be set in constructor or by capacity property. By default its 16.
  4. While adding, if no of elements in array exceeds its capacity, array is redimensioned to double of its current size.
  5. Boxing and Unboxing of value types degrades performance of arraylist.

Next Read : Why Strings Are Immutable In Dot Net?

 

Advertisements

2 thoughts on “An Extensive Examination Of ArrayList in C#

What do you think about this article?

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s