A Python list is an ordered, sequence-like collection that can hold numbers, strings, and other lists together. It resizes dynamically as elements are added, making it more flexible than a fixed-size array, though that flexibility can reduce performance in critical code. section 2.7
At the abstract-data-type level, a list is a sequence whose elements can be traversed and accessed sequentially. Arrays and linked lists are two different data-structure refinements of that same idea. section 7.3
Choose a list or array-like structure according to the flexibility and performance your program needs:
- Use a Python list when convenient dynamic resizing and mixed element types matter more than maximum performance. section 2.7
- Consider a type-consistent array implementation when the elements share a type; array.array remains dynamic, while NumPy can provide fixed-size arrays. section 2.7
- Remember that arrays and linked lists support the list abstraction with different operation costs, so performance-sensitive code deserves measurement before optimization. section 2.7 section 7.3
A list-backed heap
A heap can store its elements in a Python list. The list acts as the internal array while helper methods calculate parent and child positions and compare element priorities. section 10.16
class Heap:
def __init__(self, elements=None, element_priority=lambda x: x):
self._priority = element_priority
if elements is not None and len(elements) > 0:
self._heapify(elements)
else:
self._elements = []
This implementation shows a Heap class using a Python list internally and rebuilding its structure from existing elements. section 10.16
