contiguous memory
Memory laid out as one unbroken block, with each item directly after the previous one.
In more detail
Contiguity is what lets an array compute any slot's address with arithmetic instead of following links. It also makes scanning fast, because the processor loads neighbouring items into its cache together. Linked lists give up contiguity in exchange for cheap insertion at known positions.
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.
- memory address — The number that identifies one byte's position in memory, much like a house number on a very long street.
- CPU cache — A small, very fast memory on the processor that keeps copies of recently used data, and the data next to it, so it can be read again quickly.
- linked list — A sequence made of nodes scattered in memory, each holding a value and a pointer to the next node.
Taught in
- Hash Tables: Chaining, Open Addressing And Load Factor — 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
- Deques And Ring Buffers — Algorithms & Data Structures for Working Engineers
- Choosing The Right Sequence — Algorithms & Data Structures for Working Engineers