Arrays algorithms

ArrayList

An ArrayList uses an array as a fundamental data type instead, and then practice linked lists operations. Its purpose is to be as traversible as an array, with the ability to grow like a Linked List.

For this we need two datas:

Length

The length is the amount of entries inside the array.

Capacity

The capacity is the number of possible entries of the array.

For example, an array with a capacity of 6 and a length of 3:

[1, 2, 3, , , ]
       |      |
    Length    |
              |
           Capacity

ArrayLists are very good with Stack like operations:

Push

Go to the lenght, add the new value at lenght +1.

Pop

Goto the length, remove the value and decrement the length.

If the length is the same as the capacity, and a Push happens, then a new array with a larger capacity is created, and the data from the initial array is copied inside the new one. The goal with ArrayList is to balance between using the last amount of memory, and do the least amount of growing operations.

This is why ArrayLists aren't as good with Queue like operations:

Enqueue

If the array has the capacity, all entries starting from the last one need to be moved by +1, one by one, to make space for the new entry at the head of the array.

Deque

All entries starting from this first one need to be moved by -1, one by one, to free make space at the end of the end of the array.

The same issues happen when inserting in the middle of the ArrayList.

ArrayBuffer - Ring Buffer

An ArrayBuffer is an over-capacity array that does not use 0 as the head and length as the tail. Instead, the head and the tail have an index, with free space before the head and after the head.

[....[----------->]......]
0    |            |      n
    Head        Tail

The ArrayBuffer eases some operations:

Deque

Clean the entry then add 1 to the head, without the need to move the remaining entries by -1.

Push

Add the new entry at length, then add 1 to the tail.

If the push reaches the maximum capacity of the array, it can circle back to the start of they array plus the modulo of the length, and set its tail there (hence the name Ring Buffers).

[->]....[---------------]
0  |    |               n
 Tail Head

The moment the is as the same position than the head, and a push happens, the array needs to be resized. To maintain order, the copy needs to start at the head, go to the length, and write into a larger ArrayBuffer.