Middle
How is a list structured in Python?
sobes.tech AI
Answer from AI
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)