What data structure is used to implement the arraylist

Question

What data structure is used in building arraylist, as we are able to add/delete values dynamically on it.

I was assuming that its using linkedlist but after doing some google, i found that its using vector.. but no more details about it.

Answer 1

On modern processors, the memory cache is king. Using the cache efficiently makes an enormous difference, the processor can easily be stalled for hundreds of cycles when the program accesses an address whose content isn't cached, waiting for the very slow memory bus to supply the data.

Accessing memory is most efficient when you access it sequentially. The odds that a byte will be available in the cache is then the greatest, it is very likely to be present in the same cache line. Which makes arrays by far the most efficient collection object, assuming you index the array elements sequentially.

Accordingly, all .NET collection classes except LinkedList use arrays to store data. Including hashed collections (Hashtable, Dictionary, Hashset), they use an array of arrays. Including ArrayList. LinkedList should be avoided due to its very poor cache locality, except when cheap inserts and deletes at random known locations is the primary concern.

A problem with arrays is that their size is fixed which makes it difficult to implement auto-sizing collections, like ArrayList. This is solved by intentionally wasting address space. Whenever the array fills up to capacity, the array is reallocated and the elements are copied. The reallocation is double the previous size, you can observe this from the Capacity property. While this sounds expensive, the algorithm is amortized O(1) and the virtual memory sub-system in the operating system ensures that you don't actually pay for memory that you don't use.

You can avoid the not-so-cheap copying by guessing the Capacity up front. More details about that in this answer.

Answer 2

Arraylist internally use arrays to store the data and resize the array when ever needed.

The java implementation of Arraylist internally creates an array with initial size and resizes the array.

You can see the implementation here: http://www.docjar.com/html/api/java/util/ArrayList.java.html

This is for Java, but the concepts are same for .NET.

Answer 3

From the MSDN page:

Implements the IList interface using an array whose size is dynamically increased as required.

Some of the benefits of using the class instead of an array directly are:

• it can be used anywhere an IList
• it handles the resizing and copying for you when adding/removing items from the middle of the array
• it keeps track of the 'last' item in the array
• it provides methods for binary searching for items in the array

Answer 4

The ArrayList stores values internally as an array of objects and exposes some public helper methods to make working with the array easier (exposed via the IList interface).

When items are inserted, all the elements to the right of the insertion point are moved to the right, making inserts rather inefficient. Appends, on the other hand, are quick because there is no need to shift elements (unless the internal array has reached capacity, in which case it is replaced with a larger array).

Because the values are stored internally as an array, it provides the advantages of arrays (such as efficient searches if the values are sorted).

Answer 5

See here: ArrayList source

As already mentioned, it is an array underneath.

private object[] _items;

Here is the Add() method:

public virtual int Add(object value)
{
    if (this._size == this._items.Length)
    {
        this.EnsureCapacity(this._size + 1);
    }
    this._items[this._size] = value;
    ArrayList expr_2D = this;
    ArrayList arg_2E_0 = expr_2D;
    expr_2D._version = arg_2E_0._version + 1;
    ArrayList expr_3B = this;
    ArrayList arg_3C_0 = expr_3B;
    ArrayList arg_45_0 = expr_3B;
    int expr_41 = arg_3C_0._size;
    int arg_42_0 = expr_41;
    int arg_44_0 = expr_41;
    int i = arg_42_0;
    arg_45_0._size = arg_44_0 + 1;
    return i;
}

As you can see, EnsureCapacity is called...which ends up calling set_Capacity:

public virtual void set_Capacity(int value)
{
    if (value < this._size)
    {
        throw new ArgumentOutOfRangeException("value", Environment.GetResourceString("ArgumentOutOfRange_SmallCapacity"));
    }
    if (value != this._items.Length)
    {
        if (value <= 0)
        {
            this._items = new object[4];
            goto IL_65;
        }
        object[] array = new object[value];
        if (this._size > 0)
        {
            Array.Copy(this._items, 0, array, 0, this._size);
        }
        this._items = array;
        return;
    }
    IL_65:
}

Where the entire array is copied to a larger array if the capacity needs to be increased.