random access
Reaching any element of a sequence directly by its position, in the same time whatever the position.
In more detail
Arrays and Python lists offer O(1) random access because the position translates straight into a memory address. Linked lists and deques do not: reaching the middle means walking through the elements or blocks before it. If your code indexes into the middle often, choose a contiguous structure.
Related terms
- array — A sequence of same-sized slots stored one after another in a single block of memory, so any slot can be reached by its index directly.
- linked list — A sequence made of nodes scattered in memory, each holding a value and a pointer to the next node.
- 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.
Taught in
- 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
- Deques And Ring Buffers — Algorithms & Data Structures for Working Engineers
- Choosing The Right Sequence — Algorithms & Data Structures for Working Engineers