Array Variations

Array-Based Linear Data Structures

Type	Description	Key Characteristic	Typical Use Case	Access Pattern	Memory Behavior	Notes
Array	Fixed-size indexed collection	Contiguous memory	Fast lookup	Indexed	Contiguous	Basic building block
Associative Array	Key–value mapping	Key-based access	Dictionaries, maps	Key-based	Depends on implementation	Often hash-backed
Bit Array	Array of bits	Bit-level storage	Flags, permissions	Indexed (bit)	Compact	Memory efficient
Bit Field	Group of bits in a word	Bit masking	Low-level systems	Bit-level	Very compact	Used in C/C++
Bitboard	Bit array representing state	Encodes board positions	Game engines	Bit-level	Compact	Chess, Go
Bitmap	Bit-based image representation	Pixel-level bits	Graphics, fonts	Indexed	Compact	Binary images
Circular Buffer	Array with wrap-around	Fixed-size queue	Streaming data	Indexed	Contiguous	Overwrites old data
Control Table	Lookup-driven array	Precomputed values	Control systems	Indexed	Contiguous	Fast decision making
Image	Multi-dimensional array	Pixel grid	Image processing	Indexed (2D/3D)	Contiguous	Matrix-based
Dope Vector	Descriptor for array	Stores bounds & strides	Compilers	Indexed	Metadata-based	Used internally
Dynamic Array	Resizable array	Automatic growth	Lists, vectors	Indexed	Contiguous	Amortized resizing
Gap Buffer	Array with a gap	Fast insert near cursor	Text editors	Indexed	Contiguous + gap	Editor internals
Hashed Array Tree	Tree of arrays	Scalable dynamic size	Large collections	Indexed	Semi-contiguous	Used in functional langs
Lookup Table	Precomputed results	Constant-time access	Math, encoding	Indexed	Contiguous	Trades memory for speed
Matrix	2D array	Row–column layout	Math, ML	Indexed (2D)	Contiguous	Linear algebra
Parallel Array	Multiple arrays in sync	Columnar storage	Data processing	Indexed	Contiguous	Cache-friendly
Sorted Array	Ordered array	Binary search enabled	Search-heavy systems	Indexed	Contiguous	Costly insertions
Sparse Matrix	Stores non-zero values	Memory optimized	Scientific computing	Indexed (indirect)	Sparse	Uses mappings
Iliffe Vector	Array of pointers to arrays	Non-contiguous rows	Irregular matrices	Indexed	Non-contiguous	Flexible rows
Variable-length Array	Size decided at runtime	Stack allocation	Temporary storage	Indexed	Contiguous	Language dependent