ANALYZING SELF-ADJUSTING LINEAR LIST ALGORITHMS WITH DELETIONS AND UNSUCCESSFUL SEARCHES

In (Hui and Martel, 1993), we designed and analyzed efficient self-adj usting linear list algorithms. Our analysis proves that a self-adjusti ng linear list algorithm, MP, is competitive to a large class of offli ne adversaries, where the operations are successful searches, unsucces sful searches, and insertions. Analysis of deletions is listed as an o pen question. This paper presents an improved version of MP which is a lso able to handle deletions efficiently, and proves that the new MP a lgorithm is 6-competitive to offline adversaries when considering succ essful searches, unsuccessful searches, insertions, and deletions.