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.