### Random-access

In [1]

A typical illustration of this distinction is to compare an ancient scroll (sequential; all material prior to the data needed must be unrolled) and the book (direct: can be immediately flipped open to any arbitrary page). A more modern example is a cassette tape (sequential—one must fast forward through earlier songs to get to later ones) and a CD (direct access—one can skip to the track wanted, knowing that that would be the one retrieved).

In data structures, direct access implies the ability to access any entry in a list in constant (independent of its position in the list and of list's size, i.e. $O\left(1\right)$) time. Very few data structures can guarantee this, other than arrays (and related structures like dynamic arrays). Direct access is required, or at least valuable, in many algorithms such as binary search, integer sorting or certain versions of sieve of Eratosthenes.[3]

Other data structures, such as linked lists, sacrifice direct access to permit efficient inserts, deletes, or reordering of data. Self-balancing binary search trees may provide an acceptable compromise, where access time is equal for any member of a collection and only grows logarithmically with its size.