How is a list structured in Python?

A list in Python is an ordered, mutable collection of elements based on a dynamic array.

• Ordered: Elements are stored and accessible by index.
• Mutable: Elements can be added, removed, and modified after creation.
• Dynamic array: The list can grow or shrink in size as elements are added or removed. Python manages memory allocation for the array automatically.
• Heterogeneous types: A list can contain elements of different data types (int, str, float, other lists, etc.) simultaneously.
• Implementation in CPython: In the standard Python implementation (CPython), a list is implemented as an array of pointers to Python objects. When the list size changes, memory is reallocated and elements are copied, which can be inefficient for frequent insertions/deletions at the beginning or middle of very large lists. For such cases, it is better to use collections.deque.

# Example of creating and using a list
my_list = [1, "hello", 3.14, [4, 5]]

# Accessing elements by index
print(my_list[0])  # Output: 1
print(my_list[-1]) # Output: [4, 5]

# Modifying an element
my_list[1] = "world"
print(my_list)     # Output: [1, 'world', 3.14, [4, 5]]

# Adding an element
my_list.append(True)
print(my_list)     # Output: [1, 'world', 3.14, [4, 5], True]

# Removing an element
my_list.remove(3.14)
print(my_list)     # Output: [1, 'world', [4, 5], True]

# Length of the list
print(len(my_list)) # Output: 4

Operations like shifting (inserting or deleting at the beginning/middle) have a complexity of $O(n)$, where $n$ is the length of the list, due to the need to shift subsequent elements. Appending at the end (append) usually has amortized complexity of $O(1)$, as memory reallocation does not occur with every operation.

# Example of inserting an element at the beginning (O(n))
my_list.insert(0, "start")
print(my_list)

# Example of deleting an element by index (O(n))
del my_list[1]
print(my_list)