<p>The self-adjusting linked lists described by Bentley have practical applications in data compression.  For example, <a href="http://en.wikipedia.org/wiki/Bzip2">bzip2</a> uses <a href="http://en.wikipedia.org/wiki/Move-to-front_transform">move-to-front</a> encoding (among many other tricks).  See also <a href="http://www.cs.cmu.edu/~sleator/papers/Adaptive-data-compression.htm">this paper</a> by Bentley et al.</p>

CC BY-SA 3.0
2011-12-14T09:26:21.030Z
2011-12-14T09:26:21.030Z
Jeffε
<p>I can think of two situations where a linked list based linear search with heuristics may be better than using a hash table:
1. For small lists the overhead associated with calculating the hash function may matter more than the improvement in complexity.
2. You need a large enough table to avoid collisions (number of buckets should be at least twice the number of entries). In applications where memory is an issue (e.g. embedded systems), this can be a significant factor.</p>

CC BY-SA 3.0
2011-12-13T13:38:20.067Z
2011-12-13T13:38:20.067Z
Shitikanth
<p>I've read the paper by <strong>Jon L. Bentley</strong> <em>"Amortized analyses of self-organizing sequential search heuristics"</em>. It deals with different schemes for improving linear search. (such as after every access to an element move it to front or transpose neighboring elements) And at the end of the paper was a section for those who are interested in practical applications of this techniques. </p>

<p>It says that such techniques has practical applications if you want to do a linear search quicker (obviously, it's true). 
But can you give some example of such problem? 
If we need to make fast searching , insertion and deletion why don't you use <em>HashTable</em>? I thought the only reason why we use <em>Linked List</em> is that it <strong>preserves order</strong> and its very easy to implement. Am I right? 
But with such heuristics we don't preserve order. But it's still easy to implement...</p>

<p>So for what purposes do we use such heuristics that don't preserves order for list?
Thank you very much!</p>

<ds.data-structures><research-practice><heuristics>
Self-organizing Sequential Search Heuristics
user197284
# Self-organizing Sequential Search Heuristics

(Asked by: username_0 on 2011-12-13)

I've read the paper by **Jon L. Bentley** *"Amortized analyses of self-organizing sequential search heuristics"*. It deals with different schemes for improving linear search. (such as after every access to an element move it to front or transpose neighboring elements) And at the end of the paper was a section for those who are interested in practical applications of this techniques.

It says that such techniques has practical applications if you want to do a linear search quicker (obviously, it's true).
But can you give some example of such problem?
If we need to make fast searching , insertion and deletion why don't you use *HashTable*? I thought the only reason why we use *Linked List* is that it **preserves order** and its very easy to implement. Am I right?
But with such heuristics we don't preserve order. But it's still easy to implement...

So for what purposes do we use such heuristics that don't preserves order for list?
Thank you very much!

**Tags:** ds.data-structures, research-practice, heuristics


---

## 2 answers

### Answer by username_1 on 2011-12-14. Score: 7 | Accepted answer

The self-adjusting linked lists described by Bentley have practical applications in data compression. For example, [bzip2](http://en.wikipedia.org/wiki/Bzip2) uses [move-to-front](http://en.wikipedia.org/wiki/Move-to-front_transform) encoding (among many other tricks). See also [this paper](http://www.cs.cmu.edu/~sleator/papers/Adaptive-data-compression.htm) by Bentley et al.


---

### Answer by username_2 on 2011-12-13. Score: 3

I can think of two situations where a linked list based linear search with heuristics may be better than using a hash table:
1. For small lists the overhead associated with calculating the hash function may matter more than the improvement in complexity.
2. You need a large enough table to avoid collisions (number of buckets should be at least twice the number of entries). In applications where memory is an issue (e.g. embedded systems), this can be a significant factor.


---

