Python list
Python's built-in ordered, growable sequence, implemented as a dynamic array of pointers to objects.
In more detail
Index access and append at the end are fast: O(1) and O(1) amortised. Inserting or removing at the front, including list.pop(0), shifts every other element and costs O(n). That makes a list an excellent stack and a poor queue.
Related terms
- dynamic array — An array that grows on demand by allocating a larger block and copying the existing items across when it runs out of room.
- deque — A double-ended queue: a sequence that adds and removes items at either end in O(1) time; Python provides it as collections.deque.
- stack — A collection where the last item added is the first one removed, like a pile of plates.
- slicing — Taking a sub-sequence of a list, string or tuple with the syntax seq[start:stop], which in Python returns a new copy.
Taught in
- Amortised Analysis: Why Append Is Cheap — Algorithms & Data Structures for Working Engineers
- Arrays: Contiguous Memory And Constant-Time Access — Algorithms & Data Structures for Working Engineers
- Linked Lists: Nodes, Pointers And Sentinels — Algorithms & Data Structures for Working Engineers
- Stacks And Queues: Last In Or First In — Algorithms & Data Structures for Working Engineers
- Choosing The Right Sequence — Algorithms & Data Structures for Working Engineers