What data structure is used to implement the archaist

Question

What data structure is used to build arraylist, since we can dynamically add / remove values.

I assumed that his use of a linked list, but after doing some google, I found that his use of the vector ... but no more detailed information about this.

Answer 1

On modern processors, the memory cache is king. Using a cache effectively is of utmost importance; a processor can easily be stopped for hundreds of cycles when a program accesses an address whose contents are not cached, expecting a very slow memory bus to provide data.

Access to memory is most effective with sequential access to it. The likelihood that the byte will be available in the cache will then be the greatest; it will most likely be present on the same cache line. What makes arrays the most efficient collection object today, assuming you are indexing the elements of the array sequentially.

Accordingly, all .NET collection classes, with the exception of 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 the very poor cache location, unless cheap insertion and deletion at randomly known locations is a major concern.

The problem with arrays is that their size is fixed, which makes it difficult to implement auto-separation collections such as ArrayList. This is solved by intentionally using the address space. Whenever an array is filled to capacity, the array is redistributed and elements are copied. The redistribution is twice the previous size; you can observe this from the Capacity property. Although this sounds expensive, the algorithm is depreciated by O (1), and the virtual memory subsystem in the operating system ensures that you do not actually pay for memory that you are not using.

You can avoid not-so-cheap copying by guessing "Forward Gain." More on this in this answer .

Answer 2

Arraylist internally uses arrays to store data and resize the array if necessary.

The Java implementation of Arraylist internally creates an array with an 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 the same for .NET.

Answer 3

On the MSDN page:

Implements the IList interface using an array whose size dynamically increases as needed.

Some advantages of using a class instead of an array directly:

• it can be used anywhere IList
• it handles resizing and copying for you when adding / removing elements from the middle of an array
• it keeps track of the "last" element in the array
• it provides methods for binary search of elements in an array

Answer 4

ArrayList stores the values ​​internally as an array of objects and provides some commonly used helper methods to make working with the array easier (displayed via the IList interface).

When elements are inserted, all elements to the right of the insertion point move to the right, making the insertions quite ineffective. On the other hand, it is added quickly because there is no need to move elements (unless the internal array has reached power, in which case it is replaced by a large array).

Since the values ​​are stored internally as an array, they provide the benefits of arrays (for example, efficient search queries if the values ​​are sorted).

Answer 5

See here: Source ArrayList

As already mentioned, this is the array below it.

 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 with a call to 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: } 

If the whole array is copied to a larger array, if necessary, increase the capacity.