Skip to main content

​
Overview

Array is a data structure that lets you store multiple values in one variable. Each value in the array is called an element, and elements are accessed using their index, which starts at 0 for the first element.
OperationsComplexityDescription
Access/Edit i-th elementO(1)Arrays give direct access to elements through their index.
Insert/RemoveO(n)Adding or removing an element at a specific index requires shifting all later elements to make room or fill the gap.
Insert/Remove at endO(1)Adding or removing an element at the end only needs updating the last index.

​
Background

Arrays are usually stored as contiguous memory blocks. This means all elements sit next to each other in memory with no gaps in between.
When an array is created, the system allocates a block of memory large enough to hold all elements. The memory address of each element is based on the starting address of the array. The first element sits at the starting address, and each following element is placed at the next available address.
int arr[5] = {3, 7, 1, 2, 3};
If each integer takes 4 bytes, the memory addresses look like this:
Address of arr[0] = starting address
Address of arr[1] = starting address + 4
Address of arr[2] = starting address + 8
Address of arr[3] = starting address + 12
Address of arr[4] = starting address + 16
Because the memory is contiguous, accessing elements is efficient. The address of any element can be calculated from the starting address and the size of each element. This makes direct access possible without looping or searching.
Different languages are designed with different goals related to performance, control, and flexibility, arrays can differ with their declaration and capabilities. Static Arrays:
  • They have a fixed size declared ahead of time.
  • They use a set amount of memory for the entire program.
  • Trying to add more elements than the set size can lead to overflow or memory issues.
Dynamic Arrays:
  • They do not need a fixed size in advance.
  • They can grow or shrink during runtime.
  • Some languages give them a default starting capacity. When this capacity is exceeded, the array is resized.
  • Resizing usually means creating a new larger block of memory, often 2x or 1.5x bigger, copying all existing elements into it, and freeing the old block.
    The worst case for resizing has a time complexity of O(n) because all elements must be copied one by one.
Here is a video about JavaScript arrays and how the V8 engine handles them: https://www.youtube.com/watch?v=m9cTaYI95Zc