Article

Arrays in Computer Science and Python - An overview with space and time complexities

What are Arrays? An Overview in Computer Science

An array is a fundamental data structure used to store collections of elements that can be accessed by indexes. Arrays are widely used in programming due to their efficiency and simplicity.

Key Characteristics of Arrays

Arrays are of course ordered, and in most programming languages, the index starts at 0.
Arrays use a contiguous block of memory. This allows efficient random access with indexes.
In many programming languages, you have to specify the size of an array at initialization time, so it can reserve the appropriate amount of memory from the start. (but not in Python)
In many programming languages (again, not in Python) you can store only one type of objects inside.

Understanding Arrays in Python: Lists Explained

In Python, arrays are implemented using a versatile data structure called lists.

Key Features of Python `list`

Python uses a flexible version of arrays called dynamic arrays.
In Python, you can store multiple types of objects in a single array. However, in many other languages, arrays often store only a single type of object (e.g., only integers or only floats).
You don’t have to declare the size of a list in Python, as Python manages this automatically.
If the list exceeds its originally allocated space, Python will automatically resize the array by moving it to a different memory location (if necessary) and extending its available space. This operation has a time complexity of $O(n)$ . Where $n$ is, of course, the number of elements in the list.
Lists in Python are mutable (really important!).

It is also worth noting that regular arrays (in languages like C) are storing values directly. Python is storing in the list a references to the actual objects - so it adds a little bit of overhead during access.

What Happens When Python Lists Grow Beyond Its Originally Allocated Memory Block?

A larger block of memory is allocated (usually larger than needed right now to prepare for further appending).
The existing elements are copied to the new block.
The old memory block is released.

To minimize the frequency of resizing, Python lists over-allocate memory. The exact "growth factor" depends on specific implementation, but it typically increases the size by around 1.125 - 1.5 times the current capacity.

Time Complexity of List Resizing

This resizing operation takes $O(n)$ and it is what makes appending to a Python list amortized $O(1)$ .

Array Operations and Their Space and Time Complexities

The table below shows time and space complexities for standard operations on arrays. This applies both to "regular", fixed-size arrays in low-level languages (like C) and to Python dynamic arrays (lists). The only big difference is in the time complexity of inserting a value at the end. Please be sure to read the note below the table!

Operation	Time Complexity	Space Complexity	Notes
Creating an array	$O(n)$	$O(n)$	where $n$ is the number of elements you’re actually initializing
Accessing a value by index	$O(1)$	$O(1)$	-
Updating a value by index	$O(1)$	$O(1)$	-
Inserting a value at the beginning	$O(n)$	$O(1)$	because you need to move the whole array one position to the right
Inserting a value in the middle	$O(n)$	$O(1)$	same as above, in theory it would be $1/2 n$ , but we drop constants
Inserting a value at the end	$O(n)$	$O(1)$	because you need to create a new, bigger array and move your old array (In Python it's actually $O(1)$ - see below!)
Removing a value at the beginning/middle	$O(n)$	$O(1)$	look above at inserting for explanation
Removing a value at the end	$O(1)$	$O(1)$	in both arrays and dynamic arrays (though in low-level languages like C, arrays have a fixed size and no built-in concept of "removal"
Making a copy of the whole array	$O(n)$	$O(n)$	-

Notes

WARNING! In Python, inserting a value at the end of an array is amortized $O(1)$ due to its dynamic array implementation. Although resizing the array has a complexity of $O(n)$ , following insertions are most often $O(1)$ . That's why we say that it is "amortized" since "on average" it's close to $O(1)$ . We get $O(n)$ for each array extension but at the same time we get "enough" $O(1)$ insertions after so it all "roughly cancels out" to $O(1)$ .

Examples of Basic Array Operations in Python

# Creating an array: O(n) (and O(n) space complexity) (n is of course the number of elements in the list)
my_list = [1, 2, 3, 4, 5]


# Accessing value by index: O(1)
value = my_list[3]


# Updating value on index: O(1)
my_list[3] = 123


# Inserting a value at the beginning of the array: O(n)
my_list.insert(0, 123)


# Inserting a value in the middle of the array: O(n)
my_list.insert(len(my_list)//2, 123)


# Inserting a value at the end of the array: O(1) (it's "amortized" O(1) actually)
my_list.append(123)


# Removing a value at the beginning or in the middle of the array: O(n)
my_list.pop(0)


# Removing a value at the end of the array: O(1)
my_list.pop()


# Making a copy of a whole array: O(n) (this is a shallow copy!)
my_list_copy = my_list.copy()


# Depending on the contents of the "my_list", copy.deepcopy() could be worse than O(n)
import copy
my_list_deepcopy = copy.deepcopy(my_list)


# Slicing a list: O(k) (k is the size of the slice)
sliced_list = my_list[1:4]


# Membership checking (using the `#!python in` keyword): O(n)
is_member = 3 in my_list
not_member = 999 not in my_list

Other Popular Python List Operations and Their Performance

Operation	Time Complexity	Space Complexity	Notes
`my_list_length = len(my_list)`	$O(1)$	$O(1)$	the list length is stored and updated, not calculated "on the fly"
`my_list.remove(123)`	$O(n)$	$O(1)$	removes the first occurrence of the specified value (uses linear search)
`is_present = 5 in my_list`	$O(n)$	$O(1)$	checks if an element exists in the list (uses linear search)
`max_value = max(my_list)`	$O(n)$	$O(1)$	traverses the entire list to find the maximum value
`min_value = min(my_list)`	$O(n)$	$O(1)$	similar to finding the maximum value, but for the minimum
`total_sum = sum(my_list)`	$O(n)$	$O(1)$	iterates through the list to calculate the total sum of elements
`any_true = any(my_list)`	$O(n)$	$O(1)$	checks if any element in the list evaluates to `True`
`all_true = all(my_list)`	$O(n)$	$O(1)$	checks if all elements in the list evaluate to `True`
`my_list.reverse()`	$O(n)$	$O(1)$	reverses the list in-place, modifying the original list
`new_reversed_list = my_list[::-1]`	$O(n)$	$O(n)$	creates a new reversed copy of the list, requiring additional space
`my_list.sort()`	$O(n log n)$	$O(1)$	sorts the list in-place using Python's Timsort algorithm
`my_list_sorted = sorted(my_list)`	$O(n log n)$	$O(n)$	creates a sorted copy of the list, requires additional memory allocation

Introducing Python’s `array` Module: Efficient and Fixed-Type Arrays

In Python, the closest native structure to an array (as in other programming languages like C++) is the array module. Unlike Python's list, the array module provides arrays that can only store elements of a single type, making them more memory-efficient for certain applications.

Here's an example of an array using the array module:

import array

# Create an array of integers
int_array = array.array('i', [1, 2, 3, 4, 5])


# Access an element by index
print("Element at index 2:", int_array[2])


# Modify an element
int_array[2] = 10
print("Modified array:", int_array)


# Append an element to the array
int_array.append(6)
print("Array after appending:", int_array)


# Remove an element from the array
int_array.remove(10)  # Removes the first occurrence of 10
print("Array after removing 10:", int_array)


# Iterate through the array
for element in int_array:
    print(element)


# Slice the array
sliced_array = int_array[1:4]
print("Sliced array:", sliced_array)

This makes the array module more similar to arrays in C or Java, as opposed to Python's list.

Why Use `array` Instead of a `list`?

Memory Efficiency: Arrays use less memory because they are fixed-type and contiguous in memory. Arrays stores the raw data (e.g., integers, floats) itself in a tightly packed, contiguous block of memory. (lists in Python store references, the actual objects themselves can live anywhere in memory)
Performance: Operations on arrays can be faster when working with large datasets, especially in numerical computations. But don't be disappointed. Regular Python lists are much faster in a lot of situations!

Take a Look at Some Benchmarks of `list` vs. `array`

import timeit
import array
import sys

# Measure memory usage
list_memory = sys.getsizeof([i for i in range(10**6)])
array_memory = sys.getsizeof(array.array('i', range(10**6)))
print(f"Python list memory size: {list_memory / 1024 / 1024:.6f} MB")  # Python list memory size: 8.057335 MB
print(f"Array memory size: {array_memory / 1024 / 1024:.6f} MB")  # Array memory size: 3.902386 MB

# Benchmark of converting a collection of integers into bytes format (kinda like serialization)
list_to_bytes_time = timeit.timeit(
    "bytes(lst)",
    setup="lst = [i % 256 for i in range(10**6)]",
    number=10
)
array_to_bytes_time = timeit.timeit(
    "bytes(arr)",
    setup="import array; arr = array.array('B', [i % 256 for i in range(10**6)])",
    number=10
)
print(f"Python list to bytes: {list_to_bytes_time:.6f} seconds")  # Python list to bytes: 0.031110 seconds
print(f"Array to bytes: {array_to_bytes_time:.6f} seconds")  # Array to bytes: 0.000260 seconds

# Benchmark of accessing elements by index
list_access_time = timeit.timeit(
    "x = lst[500000]",
    setup="lst = [i for i in range(10**6)]",
    number=10**6
)
array_access_time = timeit.timeit(
    "x = arr[500000]",
    setup="import array; arr = array.array('i', range(10**6))",
    number=10**6
)
print(f"Python list access by index: {list_access_time:.6f} seconds")  # Python list access by index: 0.009259 seconds
print(f"Array access by index: {array_access_time:.6f} seconds")  # Array access by index: 0.019861 seconds

# Benchmark of summing all numbers
list_sum_time = timeit.timeit(
    "sum(lst)",
    setup="lst = [i for i in range(10**6)]",
    number=10
)
array_sum_time = timeit.timeit(
    "sum(arr)",
    setup="import array; arr = array.array('i', range(10**6))",
    number=10
)
print(f"Python list sum: {list_sum_time:.6f} seconds")  # Python list sum: 0.056205 seconds
print(f"Array sum: {array_sum_time:.6f} seconds")  # Array sum: 0.086834 seconds

As you can see, array is better optimized for memory efficiency. And we can find some use cases when it's significantly faster than Python's list. But at the same time, it's slower than list in many "normal" applications.

Why Arrays Can Be better Than Lists (in certain tasks)

How `array` Store Data

Arrays store values directly in a tightly packed block of memory. Each value is stored as raw binary data, which is compact and efficient.
This makes operations like converting to raw formats (e.g., bytes) or processing large numerical datasets faster (in certain tasks) and more memory-efficient.

How `list` Store Data

Lists don’t store values directly. Instead, they store references (or pointers) to objects. Each object includes extra metadata, such as its type and reference count.
For many operations, Python has to "follow" these references, unpack the objects, and then perform the task. This adds overhead, making lists slower for some tasks.

When to Use Each

Use Arrays when you need efficiency with numerical data, compact memory usage, or direct access to raw data (e.g., for serialization or interfacing with external systems).
Use Lists when you need flexibility to store mixed data types or need to perform operations that involve Python's powerful object model.

It is not that common to replace built-in lists with arrays in Python. If you need better performance, it’s highly likely that you could benefit from another data structure instead. So as a rule of thumb, start with regular lists in Python.

If you are looking for some alternatives for more specific tasks than regular list, you can look into deque from collections for efficient pops and inserts at both ends. And numpy arrays for numerical work and others.

So `my_list[0]` Has The Same Performance as `my_list[9999]`, Right?

Yeah, about that - Kinda, but not exactly. Both of those operations are $O(1)$ . But in reality my_list[0] is a tiny bit faster than my_list[9999]. Both in Python, and in "normal" arrays - but in "normal" arrays the difference is significantly smaller.

I wanted to write about it because I got in wrong in one of my interviews.

my_list[0]: Accessing the first element may be a tiny bit faster because it requires no additional offset computation. The address of the first element is directly available.
my_list[9999]: Accessing the element on index 9999 requires an offset computation (base address + 9999 * size of each element). While this computation is extremely fast, it might still take a tiny bit longer than accessing the first element.

Also, the first few elements of a list are more likely to be in the CPU cache. This can also contribute to the difference.

It's an interesting bit of knowledge, but in most cases you can safely assume that both are $O(1)$ . Don't overthink it.

Take a Look at a Benchmark Showcasing This "Phenomenon"

import timeit

small_index_time = timeit.timeit(
    "x = lst[0]",
    setup="lst = [i for i in range(10**6)]",
    number=10**6
)
medium_index_time = timeit.timeit(
    "x = lst[9999]",
    setup="lst = [i for i in range(10**6)]",
    number=10**6
)
large_index_time = timeit.timeit(
    "x = lst[999999]",
    setup="lst = [i for i in range(10**6)]",
    number=10**6
)

print(f"Accessing 0 index: {small_index_time:.6f} seconds")  # Accessing 0 index: 0.007704 seconds
print(f"Accessing 9999 index: {medium_index_time:.6f} seconds")  # Accessing 9999 index: 0.009496 seconds
print(f"Accessing 999999 index: {large_index_time:.6f} seconds")  # Accessing 999999 index: 0.009564 seconds

Final Words

If you are feeling adventurous, feel free to take a look at how lists in Python are really implemented in the source code over here - https://github.com/python/cpython/blob/main/Objects/listobject.c

I hope you found this helpful! If you have any feedback, questions or requests, please reach out to me through Contact page!

Article | built-in python data-structure

You might also be interested in:

Article Note | built-in python magic-method data-structure

Created with ❤ by me, for you!

BLOCK of BYTES - Bite-sized coding lessons for busy developers