Composite Types

A.K.A. non-primitive types.

Somewhat depends on the language, but this is the list Wikipedia uses.

Array

Fixed set of values in adjacent space.

E.G. string (an array of characters).

Indexable in constant (\( \Theta(1) \)) time with no wasted space. An index \( i \) can be modified in constant time as well. Since the length is fixed, insertion and deletion operations don't apply.

Record

A.K.A. tuple or structure (struct).

Union

Can have any of several representations or formats within the same position in memory.