Page "Random access" Paragraph 2

In data structures, random access implies the ability to access any entry in a list in constant ( i. e. independent of its position in the list and of list's size, i. e. ) time.

Very few data structures can guarantee this, other than arrays ( and related structures like dynamic arrays ).

Random access is critical, or at least valuable, to many algorithms such as binary search, integer sorting or certain versions of sieve of Eratosthenes.

Other data structures, such as linked lists, sacrifice random access to make for 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.