I was once asked the question how to optimize a linked list? Well, I'm not sure... So long as the linked list is somehow a linear data structure, we can only visit the previous elements to get the successive elements. I would try to build a BST instead, or maintain one table where the entries points to the middle nodes in the linked list so that we can somehow skip nodes.

Well, there is one not-so-famous data structure named skip list, which is recognized as a kind of linked list. It is not as typical as linked list, tree or graph that every textbook would give a introduction to, however it is still essential and used widely in industry.

The following is a picture of skip list from Wikipedia. However this picture is a little bit misleading: the bricks with the same number are exactly the same one node, rather than a few nodes of the same value.

The basic idea of skip list is that all nodes are divided into several kinds with different levels. The level is given when one node is created, and the level follows the distribution of logarithm distribution (if 3 levels then there would be 25% three levels, 50% two levels and 100% one levels). And the three level node would have 3 pointers pointing to its neighbor in the third level, in the second level and first level. Note that the three neighbors may overlap.

When we search, we search from the top level first because there are fewer nodes in the top level. And then we go to the next level if necessary.

The benefit of skip list is its performance. It is as good as or even better than a balanced tree because the insertion takes less operation.

And there is a good reference on the C++ implement of skip list: http://en.literateprograms.org/Skip_list_(C_Plus_Plus)#chunk def:Find Node