Arrays

There are two types of arrays. Static and dynamic ones.

Static means that as we declare our array we need to specify the size of it, to let your operating system know how many memory slots/bytes it should allocate. If it would be a 32-bit integer then 4 bytes (slots), if a 64-bit integer, then 8 memory slots.

Time complexities of standard arrays operations:

T - Time complexity; S - Space complexity; None - both Time and Space complexity

• Accessing a value at a given index: O(1)
• Updating a value at a given index: O(1)
• Iterating over: O(n) T, O(1) S
• Inserting a value at the beginning: O(n)
• Inserting a value in the middle: O(n)
• Inserting a value at the end:
  • amortized O(1) when dealing with a dynamic array
  • O(n) when dealing with a static array
• Removing a value at the beginning: O(n)
• Removing a value in the middle: O(n)
• Removing a value at the end: O(1)
• Copying the array: O(n)

Why are updating and getting constant?

As we know the memory address of the first element, we can multiply the number of bytes that a single element needs. For a 32-bit integer that would be 4 bytes. So imagine that our array starts at memory address 8, and we want the element at index 2 (the third element). Since each element is a fixed 4 bytes, we calculate: 8 + 4 * 2 = 16. The element at index 2 is at memory address 16.

Cache Locality

One of the key practical advantages of arrays is cache locality. Because array elements are stored in contiguous memory slots, accessing them sequentially plays very well with the CPU cache. When the processor loads a value from memory, it also loads a chunk of nearby addresses into the cache. With arrays, the next element you need is almost always already in the cache, making sequential access extremely fast in practice. Data structures that scatter elements across memory (like linked lists) lose this benefit and may suffer many more cache misses, even when their theoretical time complexity is the same.

Static vs Dynamic Arrays

In Java, dynamic arrays are represented by ArrayList (and the legacy Vector class). Vector is synchronized, meaning every operation acquires a lock, which introduces unnecessary overhead in single-threaded code. ArrayList is not synchronized and is the standard choice for most use cases. In JavaScript, Python, and several other modern languages, standard arrays under the hood are dynamic arrays.

Dynamic arrays mean that when we create an array with three 64-bit integers, not 24 memory slots will be taken but 48, so the allocated space is generally doubled (the exact factor may differ by language or operating system) and the second half will be empty and ‘reserved’ for us, which allows faster insertions. So when there is space, appending is O(1). But when the last memory slot is taken, the next insertion will allocate a new, larger block of memory, copy all existing elements over, double the capacity, and insert the new element — that operation is O(n). However, as more elements are added, the more rarely this happens, so we say that insertions at the end of a dynamic array have amortized O(1) complexity. If we want to insert at the beginning or in the middle, then it is O(n), because we need to shift elements to make room for the new one.