1
$\begingroup$

I'm trying to implement self-organizing lists DS to publish as a public module. Over the course of Algorithms, we learnt that if you add a new element to the list, it should still do the huriectics. For example, in Move-To-Front, when you do insert(2) it will add 2 to the end of the list and then move it to the front right away (without the need to call find(2)).

Looking into different implementation online, I see that they perform the heretics only when find() method is called. When calling insert() they don't perform the heretics.

For example:

moveToFrontLst = new MoveToFrontLst();
moveToFrontLst.append(1);
moveToFrontLst.append(2);
moveToFrontLst.append(3);

Over the course we learnt that moveToFrontLst contains [3,2,1], while the implementations online all return [1,2,3].

It was proven that Move to Front algorithm is 2-competitive, is it the first version or the second version? What is the literature implementation of self-organizing lists?

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.