An array is a contiguous, indexed block of memory whose elements are stored sequentially. Sequential scans let the CPU cache controller predict and preload the next value, making arrays an efficient foundation for collection storage. section 13.3.1
Array-backed structures trade memory locality for constraints that matter when data changes:
- List<T>, Queue<T>, and Stack<T> wrap or use arrays; HashSet<T> and Dictionary<TKey,TValue> also use arrays internally. section 13.3.1
- Linked lists and trees do not store elements contiguously, so following their structure requires less predictable memory access. section 13.3.1
- Arrays cannot share their memory with other arrays, which limits their usefulness for immutable collections that rely on structural sharing. section 13.3.1
ImmutableArray<T> accepts the copying cost of arrays: modifications copy all data and can consume substantial memory, but reads and scans are faster than those of other immutable collections. It suits read-only data passed to code outside your control, especially when updates are rare or the array is small. section 13.3.8
An array-backed stack
A simple stack stores items in a T?[] array, tracks the top index, and protects Push and TryPop with a lock. The implementation rejects pushes when the fixed array is full and clears a popped slot.
