Python Lists vs. Arrays

Python Lists vs. Arrays

In Python, the terms "list" and "array" are often used interchangeably, but they have important distinctions, especially when discussing data structures from a computer science perspective. Understanding this difference is key to writing efficient code.

What is an Array?

In traditional computer science, an Array is a collection of items stored at contiguous memory locations. This means that the items are stored right next to each other in memory, like houses on a street.

• Fixed Size: Traditionally, arrays have a fixed size, which you must define when you create them.
• Homogeneous: Arrays usually store items of the same data type (e.g., all integers or all strings).
• Fast Access: Because of their contiguous nature, accessing an element by its index is extremely fast (O(1) time complexity).

Python's list: The Dynamic Array

Python's built-in list type is not a traditional array. It's a dynamic array. This means it has the fast access of an array but with the flexibility to grow or shrink in size.

When you create a list, Python allocates a certain amount of contiguous memory. If you keep adding items and the allocated space runs out, Python automatically allocates a new, larger block of memory and copies the old elements over.

# A Python list can hold different data types
my_list = [1, "apple", 3.14]
# You can easily add items
my_list.append(True)

Accessing by index is very fast
print(my_list[1]) # Output: apple
print(my_list)

List Time Complexity

• Access (by index): O(1) - Very fast.
• Append (add to end): O(1) on average. (It's O(n) in the rare case it needs to resize).
• Insert (in middle): O(n) - Slow. All elements after the insertion point must be shifted.
• Delete (from middle): O(n) - Slow. All elements after the deleted item must be shifted.
• Search (for a value): O(n) - Slow. May have to check every element.

Python's array Module

For situations where you need a true, memory-efficient array that stores only items of the same type, Python provides the array module. This is particularly useful for handling large sequences of numbers.

You must specify a "type code" when creating an array to determine the type of its items (e.g., 'i' for signed integer, 'd' for double-precision float).

import array

Create an array of signed integers ('i')
my_array = array.array('i', [10, 20, 30, 40, 50])
print(my_array)
print(my_array[2]) # Access is still O(1)
This would cause an error because it's not an integer
my_array.append("hello")

When to use array.array vs. list?

• Use list for most general-purpose scenarios. It's flexible and easy to use.
• Use array.array when you have a very large sequence of numbers and need to optimize for memory usage and performance.