Key Differences between Self-Adjusting Lists and Regular Linked List

Question

I am in a data structures class (based on C++) and I must honestly say that my instructor has not taught us much about self-adjusting lists. Nonetheless, I've been assigned a project that requires implementing such a class.

The only note my instructor left for this project about self-adjusting lists was this:

A self-adjusting list is like a regular list, except that all insertions are performed at the front, and when an element is accessed by a search, it is moved to the front of the list, without changing the relative order of the other items. The elements with highest access probability are expected to be close to the front.

What I do not get about this is why all insertions must be performed at the front of the list. Wouldn't it be better to insert at the end considering that the data being inserted has been accessed zero times?

Also, are there any more key differences I should look out for? I cannot seem to find a good source online that goes in-depth about this topic.

Answer 1

What I do not get about this is why all insertions must be performed at the front of the list. Wouldn't it be better to insert at the end considering that the data being inserted has been accessed zero times?

Usually recently added items are more likely candidates for access. Moreover inserting at beginning is constant time operation.

For example if you buy books and keep the latest book on the top so that it can be accessed most easily. If you search and read an old book from pile, it is brought on the top.

Offcourse, you want to keep the latest bought book on the top, although you have never read it.

Also, are there any more key differences I should look out for? I cannot seem to find a good source online that goes in-depth about this topic

Although the average and worst access time of such list is same to the normal list theoretically(random node), but in practice, average access/search time is much faster.

---

If the number of nodes grow to really large number, a self-balancing BST (red-black tree for example) or hash would give better access time.

There are many other schemes used to keep the list self-adjusted: For example:

• Most recently used on the head (As you told)
• Keep the list sorted by access count (a node recently accessed may not necessarity come at front)
• When a node which is not head node is accessed, swap it with the previous node.

Exact choice of strategy depends on your requirement and profiling in target environment is the best way to choose one over another.