capacity
The number of items a structure has room for before it must grow, as opposed to the number it currently holds.
In more detail
A dynamic array's length can be smaller than its capacity; the spare slots let appends proceed without copying. A ring buffer has a fixed capacity and overwrites its oldest item instead of growing. A hash table's load factor compares its item count with its capacity.
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.
- load factor — The number of items stored in a hash table divided by the number of slots, a measure of how full it is.
- ring buffer — A fixed-size array used as a loop: when writes reach the end they wrap to the start, overwriting the oldest data.
- over-allocation — Reserving more memory than is needed right now so that future growth does not require a copy every time.
Taught in
- Amortised Analysis: Why Append Is Cheap — Algorithms & Data Structures for Working Engineers
- Hash Tables: Chaining, Open Addressing And Load Factor — 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
- B-Trees: The Structure Behind Every Database Index — Algorithms & Data Structures for Working Engineers
- Dynamic Programming: Memoisation And Tabulation — Algorithms & Data Structures for Working Engineers