4 ms·
It's not a skip-list. It's a single-linked list, except that it may contain more than one "next" pointer per item. This way you could traverse it by either one
by ramchip 17y ago
It's not a skip-list. It's a single-linked list, except that it may contain more than one "next" pointer per item. This way you could traverse it by either one of the next pointers, so you could keep the list ordered by 2 predicates at the same time.
Doesn't sound very useful in practice to me though. The interface would be complicated, error-prone, slow in many use cases, and this functionality can be much more simply be achieved by keeping two lists of pointers/references. It's also more or less obvious, so I'd be surprised if no one had done that before.
- pmjordan 17y agoActually, it's an old idea and very useful for exactly that: different orderings. It's used extensively in the Linux kernel, for example, where structs contain multiple list_head members.
- ramchip 17y agoInteresting! I found a good explanation at http://locklessinc.com/articles/flexible_lists_in_cpp/ http://locklessinc.com/articles/flexible_lists_in_cpp/ I do wonder how they could have missed the obviousness of it. Or maybe it's just the shotgun approach to patent trolling.
- showerst 17y agoWhoops, you're right. Doesn't really change the fact that this is in no way novel, and likely has published prior art going back to at least the 70s. I just don't see how anyone with any significant knowledge of computer science could think this was a new idea.