Analyzing self-adjusting linear list algorithms with deletions and unsuccessful searches

Abstract

In (Hui and Martel, 1993), we designed and analyzed efficient self-adjusting linear list algorithms. Our analysis proves that a self-adjusting linear list algorithm, MP, is competitive to a large class of offline adversaries, where the operations are successful searches, unsuccessful searches, and insertions. Analysis of deletions is listed as an open question. This paper presents an improved version of MP which is also able to handle deletions efficiently, and proves that the new MP algorithm is 6-competitive to offline adversaries when considering successful searches, unsuccessful searches, insertions, and deletions.