How does a dynamic array work?

In Python, a dynamic array (list, list) is implemented as an array of pointers to objects.

When a list is created or resized:

1. A block of memory is allocated to store pointers. The size of this block is larger than the current number of elements.
2. Existing pointers are copied to the new block.
3. When adding an element, a pointer to it is placed in the next free slot.

Features:

• Memory allocation: Python does not allocate memory immediately for all objects, only for pointers to them. The objects themselves are stored elsewhere.
• Reallocation: When adding elements, if the current memory block is full, Python allocates a new, larger block and copies the old pointers into it. This operation is called amortized O(n), since most insertions take O(1), and rare reallocations make the average time linear relative to the size of the array.
• Deletion: When deleting an element from the middle of the array, elements to the right are shifted left to fill the gap. This is an O(n) operation. Deletion from the end takes O(1).
• Access by index: Accessing an element by index takes O(1), as the address of the pointer is calculated by simple offset.

Operation table and their complexities:

Operation	Average complexity	Worst-case complexity (due to reallocation)
Access by index	O(1)	O(1)
Insert at end	O(1)	O(n)
Insert at start	O(n)	O(n)
Insert in middle	O(n)	O(n)
Remove from end	O(1)	O(1)
Remove from start	O(n)	O(n)
Remove in middle	O(n)	O(n)

# Example of working with a dynamic array (list) in Python
my_list = []  # Creating an empty list (dynamic array)

# Adding elements to the end - most often O(1)
my_list.append(1)
my_list.append(2)
my_list.append(3)

# my_list is now [1, 2, 3]. If memory needs to be reallocated, it is O(n).

# Insert at the beginning - O(n)
my_list.insert(0, 0) # [0, 1, 2, 3]

# Access by index - O(1)
print(my_list[2]) # Will print 2

# Remove from the end - O(1)
my_list.pop() # Removes 3. my_list is now [0, 1, 2]

# Remove from the middle - O(n)
del my_list[1] # Removes 1. my_list is now [0, 2]