This is not a skip list, not at all. The skip list is a probabilistic data structure that gives expected access times comparable to a BBST. The patent covers a linked list with an extra set of links that provide a different traversal.

One example of which would be a doubly linked list, which (according to Wikipedia) goes back at least to IBM's TSS/360 operating system (1967), and was discussed in The Art of Computer Programming volume 1, published in 1968.

A doubly-linked list generally refers to a bidirectional linked list, where the pointers are next and prev. This type of list allows traversal in both directions, but it's still essentially a single traversal. Multiply-linked lists provide next1, next2, etc. pointers for multiple unrelated traversals, each in a single direction (unless we assume a "multiply-doubly-linked list").

Arguably we could consider a doubly-linked list to be a special case of the multiply-linked list, but it would be a poor choice, as certain key operations (such as insertion) are more expensive with a multiply-linked list.

This multiply-linked list just seems to be a special case of an item being in multiple separate lists. In this case, the separate lists also happen to contain all the same items as the first list. Further, these are all special cases of the directed graph.

Regarding the overall conversation, it looks like everyone is arguing over whether "linked list" should be interpreted inclusively to contain all list-like linked data structures, or exclusively to refer strictly to those data structures referred to by the "linked list" moniker in traditional CS textbooks. There is also the issue of whether "linked list" has an informal, conversational meaning among a subset of programmers that differs from its formal definition (I believe this thread demonstrates that it does), and whether it should have such separate meanings.

It is my opinion that neither of these arguments is helpful to the anti-bad-patent/anti-software-patent cause, and it seems that excessive infighting over apparently trivial concerns is a credibility-destryoing hallmark of the stereotypical geek. After all, if you were a politician, would you continue to listen to a presentation in which the presenters started arguing with each other over whether the background color of the slides was more appropriately described as purple or fuchsia (Is fuchsia a subset of purple, or are they separate entirely? Sounds familiar...)?

As an aside, sometimes I wish I could draw a circle around an entire thread and say, "I'm responding to this whole blob," with the page layout updated accordingly ;).

While I ended up arguing a lot of tangents, my original point was that the title diminishes the standing of the anti-patent crowd. Whether "linked list" is taken as a generic term that describes a whole class of data structures or whether it's restricted to just the basic "linked list" types, the title is misleading. The patent does not cover the basic linked list types nor does cover the entire the entire class.

This patent is ridiculous enough without exaggeration. I believe that the patent system is broken, but making misleading claims about frivolous patents weakens the arguments. The truth is already ridiculous enough.

As for your comment about "excessive infighting over apparently trivial concerns", I wish I could dispute that. I feel that geeks as a group tend to be pedantic jackasses, and I'm often guilty of that myself. It does hurt our credibility as a whole.

By the way, your interpretation of multiply-linked lists is correct. You can look at it as multiple separate lists crammed together for minor space savings or as a directed graph with labeled edges (labels here represents which "list" an edge is for). This is why I don't think it's an especially useful data structure; there are better alternatives for most cases.

The patent by itself does not describe a skip list, but the most common skip list implementations use a multilevel list data structure similar to what's described in the patent.