iBet uBet web content aggregator. Adding the entire web to your favor.
iBet uBet web content aggregator. Adding the entire web to your favor.



Link to original content: https://doi.org/10.1007/978-1-4939-2864-4_266
Online List Update | SpringerLink
Skip to main content
Springer Nature Link
Log in

Online List Update

  • Reference work entry
  • First Online:
Encyclopedia of Algorithms

  • 87 Accesses

Years and Authors of Summarized Original Work

  • 1985; Sleator, Tarjan

Problem Definition

List update is one of the classic problems in the context of online computation. The main motivation for the study of the problem is self-adjusting lists. Consider a linear list which represents a dictionary abstract data type. There are three elementary operations in the dictionary, namely, insertion, deletion, and lookup (search). To perform these operations on an item x, an algorithm needs to search for x, i.e., examine the list items, one by one, to find x. For the case of an insertion, all items should be sequentially checked to ensure that the inserted item is not already in the list. A deletion also requires finding the item that is being deleted. In this manner, all operations can be translated into a sequence of lookups or accesses to the items in the list. To access an item at index i, an algorithm examines i items and therefore incurs an access cost of i. Immediately after the access, the...

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 1,599.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Hardcover Book
USD 1,999.99
Price excludes VAT (USA)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Recommended Reading

  1. Albers S (1998) Improved randomized on-line algorithms for the list update problem. SIAM J Comput 27:682–693

    Article  MathSciNet  MATH  Google Scholar 

  2. Albers S, Lauer S (2008) On list update with locality of reference. In: Proceedings of the 35th international colloquium on automata, languages, and programming (ICALP), Reykjavik. Lecture notes in computer science, vol 5125. Springer, pp 96–107

    Google Scholar 

  3. Albers S, Westbrook J (1996) Self-organizing data structures. In: Online algorithms: the state of the art, Dagstuhl. Lecture notes in computer science, vol 1442. Springer, pp 13–51

    Google Scholar 

  4. Albers S, von Stengel B, Werchner R (1995) A combined BIT and TIMESTAMP algorithm for the list update problem. Inf Process Lett 56(3):135–139

    Article  MATH  Google Scholar 

  5. Ambühl C, Gärtner B, von Stengel B (2013) Optimal lower bounds for projective list update algorithms. ACM Trans Algorithms 9(4):31

    Article  MathSciNet  MATH  Google Scholar 

  6. Angelopoulos S, Dorrigiv R, López-Ortiz A (2008) List update with locality of reference. In: Proceedings of the 8th Latin American theoretical informatics symposium (LATIN), Búzios. Lecture notes in computer science, vol 4957. Springer, pp 399–410

    Google Scholar 

  7. Chung FRK, Hajela DJ, Seymour PD (1988) Self-organizing sequential search and Hilbert’s inequality. J Comput Syst Sci 36(2):148–157

    Article  MathSciNet  MATH  Google Scholar 

  8. Dorrigiv R, Ehmsen MR, López-Ortiz A (2009) Parameterized analysis of paging and list update algorithms. In: Proceedings of the 7th international workshop on approximation and online algorithms (WAOA), Copenhagen. Lecture notes in computer science, vol 5893. Springer, pp 104–115

    Google Scholar 

  9. Kamali S, López-Ortiz A (2013) A survey of algorithms and models for list update. In: Space-efficient data structures, streams, and algorithms, Waterloo. Lecture notes in computer science, vol 8066. Springer, pp 251–266

    Google Scholar 

  10. Kamali S, López-Ortiz A (2014) Better compression through better list update algorithms. In: Proceedings of the 23rd data compression conference (DCC), Snowbird, pp 372–381

    Google Scholar 

  11. Martínez C, Roura S (2000) On the competitiveness of the move-to-front rule. Theor Comput Sci 242(1–2):313–325

    Article  MathSciNet  MATH  Google Scholar 

  12. Munro JI (2000) On the competitiveness of linear search. In: Proceedings of the 8th European symposium on algorithms (ESA), Saarbrücken. Lecture notes in computer science, vol 1879. Springer, pp 338–345

    Google Scholar 

  13. Reingold N, Westbrook J, Sleator DD (1994) Randomized competitive algorithms for the list update problem. Algorithmica 11:15–32

    Article  MathSciNet  MATH  Google Scholar 

  14. Rivest R (1976) On self-organizing sequential search heuristics. Commun ACM 19:63–67

    Article  MathSciNet  MATH  Google Scholar 

  15. Sleator D, Tarjan RE (1985) Amortized efficiency of list update and paging rules. Commun ACM 28:202–208

    Article  MathSciNet  Google Scholar 

  16. Teia B (1993) A lower bound for randomized list update algorithms. Inf Process Lett 47:5–9

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. David R. Cheriton School of Computer Science, University of Waterloo, Waterloo, ON, Canada

    Shahin Kamali

Authors
  1. Shahin Kamali
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Shahin Kamali .

Editor information

Editors and Affiliations

  1. Department of Electrical Engineering and Computer Science, Northwestern University, Evanston, IL, USA

    Ming-Yang Kao

Rights and permissions

Reprints and permissions

Copyright information

© 2016 Springer Science+Business Media New York

About this entry

Cite this entry

Kamali, S. (2016). Online List Update. In: Kao, MY. (eds) Encyclopedia of Algorithms. Springer, New York, NY. https://doi.org/10.1007/978-1-4939-2864-4_266

Download citation

Publish with us

Policies and ethics

Search

Navigation