Arrays and Dynamic Arrays

What is an array?

An array stores values side by side in one continuous block of memory. Because every slot is the same size, the computer can work out where item i lives with one multiplication:

address of arr[i] = address of arr[0] + i × size of one item

That is why reading or writing arr[i] takes the same tiny amount of time whether the array holds 10 items or 10 million: it is O(1). No other structure beats arrays at "give me the item at position i".

The cost of keeping everything side by side shows up when you change the shape of the array. To insert a value at the front, every existing value must shift one place to the right to make room. That is O(n) work.

Static and dynamic arrays

A static array has a fixed size chosen when it is created, like int[] a = new int[10] in Java or int a[10] in C++. It can never hold an eleventh item.

A dynamic array grows as you add items. Python's list, JavaScript's Array, Java's ArrayList and C++'s std::vector are all dynamic arrays. Underneath, each one is a static array with some spare room:

• size is how many items you have stored.
• capacity is how many slots the hidden array has.

When you append and there is spare room, the new item goes into the next free slot: O(1). When the array is full, it allocates a bigger block (usually double the capacity), copies every item across, and then appends. That one append costs O(n).

Why appending is still "O(1)"

Growing is expensive, but it happens rarely. With doubling, appending n items causes copies of 1 + 2 + 4 + … + n/2 items, which adds up to less than n. Spread over n appends, that is less than one copy per append. We call this amortised O(1): any single append might be slow, but the average over many appends is constant.

Growing by a fixed amount instead (say, 10 slots at a time) would cost O(n²) for n appends, which is why every real implementation multiplies the capacity.

Operations and their cost

Building a dynamic array yourself

The class below keeps a fixed-size storage block plus size and capacity, and doubles the storage when it runs out. insert and remove_at show the shifting that makes middle operations O(n). It also counts how many items were copied while growing, to show the amortised cost in action.

class DynamicArray:
    def __init__(self):
        self.capacity = 1
        self.size = 0
        self.data = [None] * self.capacity  # stands in for a fixed block of memory
        self.copies = 0

    def _grow(self):
        bigger = [None] * (self.capacity * 2)
        for i in range(self.size):
            bigger[i] = self.data[i]
            self.copies += 1
        self.data = bigger
        self.capacity *= 2

    def push(self, value):
        grew = self.size == self.capacity
        if grew:
            self._grow()
        self.data[self.size] = value
        self.size += 1
        return grew

    def get(self, index):
        if not 0 <= index < self.size:
            raise IndexError("index out of range")
        return self.data[index]

    def set(self, index, value):
        if not 0 <= index < self.size:
            raise IndexError("index out of range")
        self.data[index] = value

    def insert(self, index, value):
        if self.size == self.capacity:
            self._grow()
        for i in range(self.size, index, -1):  # shift right, starting from the end
            self.data[i] = self.data[i - 1]
        self.data[index] = value
        self.size += 1

    def remove_at(self, index):
        removed = self.get(index)
        for i in range(index, self.size - 1):  # shift left to close the gap
            self.data[i] = self.data[i + 1]
        self.size -= 1
        self.data[self.size] = None
        return removed

    def pop(self):
        return self.remove_at(self.size - 1)

    def __str__(self):
        return "[" + ", ".join(str(self.data[i]) for i in range(self.size)) + "]"


arr = DynamicArray()
for value in (10, 20, 30, 40, 50):
    before = arr.capacity
    grew = arr.push(value)
    note = f" (grew from {before})" if grew else ""
    print(f"push({value}): size {arr.size}, capacity {arr.capacity}{note}")
print("copies made while growing:", arr.copies)
arr.insert(0, 5)
print("after insert(0, 5):", arr)
print("get(3):", arr.get(3))
arr.set(3, 35)
print("after set(3, 35):", arr)
print("remove_at(1) returned", arr.remove_at(1))
print("pop() returned", arr.pop())
print("now:", arr, f"size {arr.size}, capacity {arr.capacity}")

push(10): size 1, capacity 1
push(20): size 2, capacity 2 (grew from 1)
push(30): size 3, capacity 4 (grew from 2)
push(40): size 4, capacity 4
push(50): size 5, capacity 8 (grew from 4)
copies made while growing: 7
after insert(0, 5): [5, 10, 20, 30, 40, 50]
get(3): 30
after set(3, 35): [5, 10, 20, 35, 40, 50]
remove_at(1) returned 10
pop() returned 50
now: [5, 20, 35, 40] size 4, capacity 8

Notice that capacity stays at 8 after removing items. Most dynamic arrays never shrink on their own, because shrinking and then growing again would waste work. Python, Java and C++ give you a way to release the spare room if you need to (trimToSize() in Java, shrink_to_fit() in C++).

Arrays in the standard libraries

Strings are arrays too

A string is an array of characters, so s[i] is O(1). In Python, JavaScript and Java, strings are immutable: "changing" one actually builds a new string. Adding characters one at a time in a loop therefore copies the whole string each time, which is O(n²) overall. Collect the pieces in a list and join them once ("".join(parts) in Python, parts.join("") in JavaScript, StringBuilder in Java). C++ std::string is mutable and appends in amortised O(1).

Common mistakes

• Off-by-one errors. Valid indices run from 0 to n − 1. A loop condition of i <= n reads past the end.
• Removing items while looping forwards. Each removal shifts the remaining items left, so the loop skips the next one. Loop backwards, or build a new array.
• Inserting at the front in a loop. n front inserts cost O(n²). Append everything and reverse once, or use a deque.
• Accidental aliasing. b = a copies the reference, not the array; changing b changes a. Use a.copy(), [...a], a.clone() or a vector copy.

When to use an array

Arrays are the default choice. Use one when you read by position, loop over all the data, or add and remove mostly at the end. Their memory layout makes them very fast in practice, often faster than structures with better textbook complexity. Reach for something else when you constantly insert or remove at the front (a deque), need fast lookup by value (a hash map or set), or need the items kept sorted as they change (a balanced tree or heap).