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(1)) 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.

References

See also

This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.