Self Organizing List | Set 1 (Introduction) - GeeksforGeeks

Self Organizing List | Set 1 (Introduction) - GeeksforGeeks

One idea to make search faster for Linked Lists is Skip List. Another idea (which is discussed in this post) is to place more frequently accessed items closer to head.. There can be two possibilities. offline (we know the complete search sequence in advance) and online (we don't know the search sequence).
In case of offline, we can put the nodes according to decreasing frequencies of search (The element having maximum search count is put first). For many practical applications, it may be difficult to obtain search sequence in advance. A Self Organizing list reorders its nodes based on searches which are done. The idea is to use locality of reference (In a typical database, 80% of the access are to 20% of the items). Following are different strategies used by Self Organizing Lists.

1) Move-to-Front Method: Any node searched is moved to the front. This strategy is easy to implement, but it may over-reward infrequently accessed items as it always move the item to front.

2) Count Method: Each node stores count of the number of times it was searched. Nodes are ordered by decreasing count. This strategy requires extra space for storing count.

3) Transpose Method: Any node searched is swapped with the preceding node. Unlike Move-to-front, this method does not adapt quickly to changing access patterns.

Read full article from Self Organizing List | Set 1 (Introduction) - GeeksforGeeks