Arrays vs ArrayLists vs Linked Lists (Does Python Even Have Arrays?)

Introduction

#

An array stores items of one type in a fixed number of equal slots. The slots are next to each other in memory.

A Python list can grow, and it can hold items of any type. So, does Python have arrays at all?

Arrays in Memory

#

For a program, memory is one long row of bytes. Each byte has a number called its address.

An array keeps its items in this row next to each other with no gaps, which is called contiguous memory. Because every item has the same type, every item takes the same number of bytes.

So, item i is at the start address plus i times the item size. Because no items come before the first item, its index is zero, which is called zero-based indexing.

Finding any item takes one multiplication and one addition at any index and any length. So, reading or writing an item is O(1).

Because memory itself is one big array of bytes, an array is the most direct way to store items in memory. Many other structures are built on arrays, such as hash tables, matrices, and priority queues. Python’s strings, tuples, dictionaries, and sets also keep their data in arrays.

Slow Array Operations

#

Keeping items next to each other also has a cost. Inserting or removing is slow everywhere except at the end.

Suppose the array has a free slot after its last item. Because no slot is free before the first item, an insert at the front moves every item one slot to the right. Removing the first item moves every other item back one slot. For n items, both take about n moves. So, both are O(n).

A plain array also doesn’t count how many of its slots hold items. A C string, for example, marks its end with a zero byte. So, finding its length checks every character, which is O(n).

Because the memory right after the array may already hold something else, the number of slots is fixed. When every slot is full, the program has to make a bigger array and copy every item into it. So, adding an item to a full array is O(n) too.

Where does an array’s memory come from? A program gets memory for most of its data from the stack and from the heap. Both are parts of a process’s memory. We covered processes in detail in a previous video, so let’s go over them quickly.

Stack and Heap

#

A program in execution is called a process. Whenever you click and launch an application, or you execute some code, the OS creates a process for you and assigns a process ID. Each process gets its own address space, divided into text, data, stack, and heap sections.

Text holds your program’s code. Data holds your global variables and constants. Stack and heap are where your local and dynamic data lives. A process also owns resources like open files and hardware devices. Finally, each process has its own CPU state, meaning the register values it was last running with. Together, all of this is its execution context.

What does a Python process look like? Do you think the Python code you write goes into the text section? We just said that’s where code normally lives, but that’s not true for Python, or for interpreted languages in general. The most common implementation of Python is written in C. So the text section of your CPython process holds compiled C code, not your Python code. CPython reads your source from the .py file, parses it, builds an abstract syntax tree, and compiles it to bytecode. Bytecode is a set of instructions for CPython’s virtual CPU, much like assembly is for your actual CPU. Your functions, classes, and data end up on the heap, not in the text section and not on the stack.

The stack memory is fast and simple. Each function call pushes a frame holding its local variables, and popping that frame when the function returns is nearly free. It also stays packed together, so its data is more likely to be accessed quickly from memory. But it’s small, and sizes have to be known up front, so anything large or dynamically sized goes on the heap instead. The heap allows dynamic sizes and large allocations, but it costs more. The memory allocator has to find a free block, it sometimes has to ask the kernel for more memory with a system call, and that memory has to be tracked and released separately.

Pointers

#

An array is contiguous whether it’s on the stack or the heap, so reading or writing an item is O(1) in both. But the stack and the heap differ in two ways for an array.

First, the stack keeps each call’s data packed together. So, an array on the stack can never grow. A program can get a heap block of any size while it runs.

Second, an array on the stack is gone when its call returns, but a heap block stays until the program frees it. So, an array that must grow, or last longer than its call, goes on the heap.

A heap block’s address is known only when the program gets the block. So, the program keeps that address. A value that holds an address is called a pointer.

As we mentioned, in CPython, the objects a program makes live on the heap. A Python variable is a name bound to an object. In CPython, that binding is implemented internally using references to PyObjects, which at the C implementation level are pointer-like values. A function’s bindings live in its frame, and CPython keeps its frames on the heap as well.

Dynamic Arrays

#

How does an array grow? A dynamic array copies its items into a bigger block for us, but only rarely.

It keeps a pointer to its block on the heap. It also counts its items and the slots in its block. The number of slots is called the capacity.

An append puts the new item in the next free slot. When no slot is free, the array gets a new block. The size of the new block is proportional to the capacity. For example, the new block can have twice the capacity. The array copies its items over and points to the new block.

If the capacity doubles each time, copies happen only at one, two, four, and eight items, and so on. Together, they copy fewer than two items per append at any length. So, an append is O(1) amortized, which means O(1) on average over a long run of appends.

The spare slots cost memory. With doubling, about half of the block is empty right after the array grows.

Examples of dynamic arrays include Java’s ArrayList and the C++ vector.

Python Lists

#

CPython’s list is not a textbook array but a dynamic array. However, its slots don’t hold the items. Each slot holds a pointer to an object somewhere else in memory.

Every pointer takes eight bytes (on 64-bit systems), no matter what it points to. Because the slots hold only pointers, they stay equal even when the objects differ in type and size. So, a list gets flexibility and a uniform structure at the same time. It can hold any type, and its block is still an array.

CPython grows a list by about an eighth instead of doubling. Growing by an eighth copies more often, but an append is still O(1) amortized. And while a long list grows, it never has more than about one empty slot for every eight items.

A Python list differs from a textbook array in two ways. It can grow, and its slots hold pointers instead of items. Java’s ArrayList works the same way and also holds pointers to objects.

Because a list holds pointers, multiplying a list copies its pointers but not the objects.

grid: list[list[int]] = [[0] * 3] * 3
grid[0][0] = 1
print(grid)

In this grid, all three slots point to the same row. So, setting one cell changes a whole column.

So, we use a list comprehension to make a grid instead.

grid: list[list[int]] = [[0] * 3 for _ in range(3)]
grid[0][0] = 1
print(grid)

Python’s array module keeps the numbers themselves in the slots, and so do NumPy’s numeric arrays outside the standard library. Both need every item to have the same type.

Linked Lists

#

A Python list keeps its pointers in one block, but a linked list keeps each item in its own small block, which is called a node. Because its nodes can be anywhere in memory, a linked list is not contiguous. So, each node holds a pointer to the next node. A linked list follows i pointers to reach item i, so indexing it is O(n). A Python list finds any item with arithmetic instead. Because no items move, a linked list can insert after a node it has already reached in O(1).

List Operations

#

What does each operation cost in an array, a list, and a linked list? Different languages have different names for them. Each cost comes from how the items are stored. Let’s reason through each cost.

Reading or writing item i computes one address in an array and in a list. So, both are O(1). A linked list has to follow i pointers instead, making its reads and writes O(n).

A list and a standard library’s linked list keep a count of their items. So, taking their length is O(1). A C string keeps no count. So, finding its length is O(n).

Appending to a list and popping from its end are O(1) amortized. A full array has to copy every item into a bigger array before an append, which makes its append O(n). A standard library’s linked list also keeps a pointer to its last node. So, its append is O(1).

Inserting or removing at the front moves every item in an array and in a list. So, both are O(n). A linked list moves no items, making its insert at the front O(1). At a million items, we measured about 265 µs for a list’s insert at the front, and about 8 ns for an append.

Checking whether an item is present compares the items one by one in all three, and finding an item’s index does the same. So, all three are O(n).

A Python list slice copies one pointer for each item it takes. So, a slice of k items takes O(k) time and O(k) memory. A linked list first follows i pointers to reach the slice. So, its slice takes O(i + k) time.

Coding Interviews

#

In an interview, a solution’s complexity is built from costs like these. A loop over n items runs its body n times. So, an O(1) operation keeps the loop at O(n), and an insert or pop at the front makes it O(n²).

In the next chapter, we’ll see how a Python dictionary uses an array to find any key in one step on average, and why a bad hash makes it check keys one by one.

See you there!