Here's a strange fact: in an array holding a billion items, grabbing the 999,999,999th item is just as fast as grabbing the first item. The computer doesn't skim past the first 999,999,998 items to get there. So how does it know exactly where to look?

The answer is the one rule every array follows: it stores a collection of items of the same type, such as integers or strings, and keeps them contiguous, much like a row of numbered lockers. Since every locker is the same size and sits right next to the previous one, the computer can calculate where any index lives instead of searching for it. The locker analogy does break in one spot. A real locker can sit empty, but an array never leaves a gap. So if you remove an item from the middle, everything after it has to slide over to close the hole.

Let's watch the array's instant access happen with real numbers. Say an array of 4-byte integers starts at memory address 1000. Index 0 lives at address 1000, index 1 at 1004, and index 2 at 1008. Where is index 3? It's at 1000 + 3 × 4 = 1012, one multiply and one add. Those two steps land on any element, whether the array holds six items or six billion. That's all O(1) access really means: the cost stays the same as the array grows.

The same packed layout that makes access cheap makes rearranging expensive. Take the array [3, 7, 12, 25, 31, 48] and insert a 5 at the front. Before reading on, commit to a guess: how many of the six values have to move?

Inserting one element forced six moves, and on a million-item array a front insert moves a million items. That cost is why insert and delete are O(n), and it's a big part of why linked lists exist. The table below summarizes the costs you just watched, plus one row, resize, that gets its own walkthrough further down the page:

Cheap access is what every array technique is really about. Pointers let you directly access and modify array elements at any position, and since every position costs the same to reach, nothing stops you from working both ends of an array at once. Here's what that looks like:

def reverse(array: List[int]) -> List[int]:
    left, right = 0, len(array) - 1
    while left < right:
        array[left], array[right] = array[right], array[left]
        left += 1
        right -= 1
    return array

# Example usage
my_array = [1, 2, 3, 4, 5, 6]
print(reverse(my_array))  # Output: [6, 5, 4, 3, 2, 1]

The reverse() function above takes an array of integers and flips it in place, meaning the original array is modified without needing extra space for another array. It uses two pointers: left starts at the beginning, and right starts at the end. Each round swaps the pair and walks both pointers inward, so the six elements above are fully reversed after just three swaps. When the pointers meet in the middle, the work is done.

Contiguous storage comes with a catch: the computer has to reserve the whole block up front. That's why static arrays have a fixed size, set when the program is compiled. The bytes right after the array usually belong to other data, so the block can't grow in place and you can't add more elements once the array is full. Trying anyway causes an error or unexpected behavior. Python hides this from you, but the limit is still there under the hood, and it raises an obvious question: what do you do when you run out of room?

What do you do when a full array runs out of room? Dynamic arrays answer with a blunt move: when the block fills up, allocate a bigger block somewhere else and copy every element over. That's the resize row from the operations table, it costs O(n) every time it happens, and in exchange dynamic arrays can grow and shrink while the program is running.

You might think this makes appending risky, since any append could be the unlucky one that triggers a full copy. The escape hatch is how much bigger the new block is: most implementations double the capacity. The code below starts at a capacity of 1 and appends five elements. Before you trace it, make your prediction: how many times will the array resize?

class DynamicArray:
    def __init__(self):
        self.array = [None]  # Start with an array of size 1
        self.size = 0

    def append(self, element):
        if self.size == len(self.array):
            # Array is full, time to resize
            new_array = [None] * (2 * len(self.array))
            # Copy elements to the new array
            for i in range(self.size):
                new_array[i] = self.array[i]
            self.array = new_array
            print(f"Array doubled. New capacity: {len(self.array)}")

        # Add the new element
        self.array[self.size] = element
        self.size += 1

# Example usage
dynamic_array = DynamicArray()
for i in range(5):
    dynamic_array.append(i)
    print(f"Added {i}. Current size: {dynamic_array.size}, Capacity: {len(dynamic_array.array)}")

Three times: the capacity jumps from 1 to 2, from 2 to 4, and from 4 to 8. Now count the copying those resizes did: 1 + 2 + 4 = 7 values moved across five appends, fewer than two moves each. Doubling keeps copies so rare that the average append still runs in constant time, which is exactly what amortized O(1) means. Most languages have dynamic arrays built in. Python calls them List, and Java calls them ArrayList. Get comfortable with whatever your language offers, since you'll use them constantly.

Look back at the operations table: reading is cheap anywhere, but the only cheap place to add or remove is the end of the array. Stacks are what you get when you lean into that and only ever touch the end. They follow the LIFO principle. They aren't arrays themselves, but they're often built on top of one. Since stacks only add or remove from the end, arrays are a natural fit. They have two main operations: push adds an item on top, and pop removes the top item. Both run in constant time because both stay at the cheap end.

class Stack:
    def __init__(self):
        self.items = []  # A list is the underlying dynamic array

    def push(self, item):
        # Add an item to the top of the stack - O(1)
        self.items.append(item)

    def pop(self):
        # Remove and return the top item - O(1)
        if self.is_empty():
            raise IndexError("pop from an empty stack")
        return self.items.pop()

    def peek(self):
        # Return the top item without removing it - O(1)
        if self.is_empty():
            raise IndexError("peek from an empty stack")
        return self.items[-1]

    def is_empty(self):
        # True when the stack has no items - O(1)
        return len(self.items) == 0

    def size(self):
        # Number of items currently on the stack - O(1)
        return len(self.items)

    def clear(self):
        # Remove every item from the stack - O(1)
        self.items = []

The animation above shows how stacks work in practice. Just like a stack of plates where you can only add or remove from the top, each operation works with the most recently added element. The plate analogy breaks in one spot: a careful hand can slide a plate out of the middle of a real stack, but a stack structure never allows it, and that restriction is the whole point. This LIFO behavior is exactly what you want when you have to unwind work in the reverse order you did it.

Arrays and stacks come up constantly in coding interviews. The tips below cover the patterns to watch for and the mistakes that trip people up most:

Before you start, quiz yourself on two things from this page: why does inserting at the front of an array cost O(n), and why does append count as O(1) even though a resize copies everything? If both answers come back quickly, you're ready. These classic array and stack problems cover in-place updates, single-pass scans, and the LIFO patterns you just learned about: