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
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.
moveToFrontLst = new MoveToFrontLst(); moveToFrontLst.append(1); moveToFrontLst.append(2); moveToFrontLst.append(3);
Over the course we learnt that
[3,2,1], while the implementations online all return
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?