In
computer scienceComputer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
,
random access (sometimes called
direct access) is the ability to access an element at an arbitrary position in a sequence in equal time, independent of sequence size. The position is arbitrary in the sense that it is unpredictable, thus the use of the term "random" in "random access". The opposite is
sequential accessIn computer science, sequential access means that a group of elements is accessed in a predetermined, ordered sequence. Sequential access is sometimes the only way of accessing the data, for example if it is on a tape...
, where a remote element takes longer time to access. A typical illustration of this distinction is to compare an ancient
scrollA scroll is a roll of papyrus, parchment, or paper which has been written, drawn or painted upon for the purpose of transmitting information or using as a decoration.-Structure:...
(sequential; all material prior to the data needed must be unrolled) and the
bookA book is a set or collection of written, printed, illustrated, or blank sheets, made of hot lava, paper, parchment, or other materials, usually fastened together to hinge at one side. A single sheet within a book is called a leaf or leaflet, and each side of a leaf is called a page...
(random: can be immediately flipped open to any random
pageA page is one side of a leaf of paper. It can be used as a measurement of documenting or recording quantity .-The page in typography:...
). A more modern example is a cassette tape (sequential—you have to fast-forward through earlier songs to get to later ones) and a CD (random access—you can skip to the track you want).
In
data structureIn computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently.Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks...
s, random access implies the ability to access any entry in a
list of numbers in constant (i.e. independent of its position in the list and of list's size, i.e.
In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...
) time. Very few data structures can guarantee this, other than arrays (and related structures like
dynamic arrayIn computer science, a dynamic array, growable array, resizable array, dynamic table, or array list is a random access, variable-size list data structure that allows elements to be added or removed...
s). Random access is critical to many algorithms such as binary search,
integer sortingIn computer science, integer sorting is the algorithmic problem of sorting a collection of data values by numeric keys, each of which is an integer. Algorithms designed for integer sorting may also often be applied to sorting problems in which the keys are floating point numbers or text strings...
or
sieve of EratosthenesIn mathematics, the sieve of Eratosthenes , one of a number of prime number sieves, is a simple, ancient algorithm for finding all prime numbers up to a specified integer....
. Other data structures, such as
linked listIn computer science, a linked list is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of a datum and a reference to the next node in the sequence; more complex variants add additional links...
s, sacrifice random access to make for efficient inserts, deletes, or reordering of data.
Self-balancing binary search treeIn computer science, a self-balancing binary search tree is any node based binary search tree that automatically keeps its height small in the face of arbitrary item insertions and deletions....
s may provide an acceptable compromise, where access time is equal for any member of a collection and only grows logarithmically with its size.