Skip lists are container data structures for keeping items in order, an alternative to various balanced trees like red-black.

The funny thing is how rarely you need that sort of thing if you have an unordered associative container, and a sorting function.

It's possible to combine a hash table with a list. E.g. the hash table references not the items directly, but the conses of a list in which those items are stored as the cdr. Then you have keyed random access to the list, as well as a particular order. Finding a spot where to insert is linear, of course.

A container which keeps items in order is useful primarily for real-time programming, for implementing a priority queue: the situation is that a dynamic set of items is in constant churn, and needs to be in order all the time (where the order is different from the order in which those items come to life or arrive or whatever). For performance, we don't want to just add an item to the end of the queue and then call sort.

If we don't care about this real time aspect, we can just accumulate items and then sort them. Even if we sort a list several times, that may not be of consequence if it is bounded to a small length. Unix treats directories like this: the "dents" are not ordered in any way: globbing expansion and the "ls" utility accumulate names and sort them. Unix could keep directories in sorted order (and there are, I think, some file systems which actually do).

There is an anti-pattern of abusing sorting when people don't have an associative container. An example of this is shell scripts which use sorting to help de-duplicate items, instead of an obvious awk job with an associative array. Another anti-pattern occurred in C++: for long time C++ had only std::map and std::set: ordered containers. These were used all the time, even when order was not required (Now there is std::unordered_map).

In the late 1990's, I wrote a pretty nice red-black tree data structure in C, which ended up used in various places, such as in ext2fs tools. one company I worked for used it for the basis of a "real-time database" for software running on a switch node for real time packet inspection and processing. The implementation had to be modified to allow for shared memory.

I don't miss that kind of container in everyday Lisp programming somehow. I have a several years old branch where that code is half-added to my Lisp dialect. There isn't much motivation to finish the job; the need for that just somehow doesn't arise. Most of the time, either you're dealing with dynamic sets which are unordered (by definition of "set", practically), or else with lists which are ordered, but don't have to be constructed by out-of-order insertions. A lot of the time, the order of a list doesn't actually follow any predicate: the only specification of order is that list instance itself and its actual order. (The order came from somewhere, but its reason is not necessarily known, only that it should be preserved.)

ANSI CL doesn't have any optimized ordered list container, only hashes. Why? It seems like nothing notable of that sort originated in any of the base dialects from which CL was formed.

Suppose you needed some real-time database for some service application: it would make a lot of sense to just pick one and make Lisp bindings to it.