5 ms·

That's just a graph.

by chockey 12y ago

throwawaykf05 12y ago
It's not a skip-list, though it is some kind of a graph. I once tried to think of what kind of a graph it is, because it has some weird properties. It is a directed acyclic graph with 1) a fixed number of paths, 2) and each vertex occurs on each path exactly once, and 3) the paths are mutually exclusive, i.e. you cannot traverse one path half-way to a vertex and then follow another path from that vertex. I'm not sure if "mutually exclusive" is the right term... maybe a formal Graph Theoretic definition could be created based on some sort of coloring or labeling of edges. But when you put these properties together you essentially get a single structure representing multiple lists. That is, given items 1 - 5, you could arrange the pointers to traverse them in orders [1, 2, 3, 4, 5] or [1, 3, 5, 4, 2] or [5, 4, 1, 2, 3], but not [1, 5, 2] or [1, 2, 3, 2, 1]. What I don't understand is why anyone would put what is essentially a number of different lists into a single list. I see no advantages either in algorithmic complexity (traversal and addition/insertion/deletion operations are still the same complexity) or implementation. In fact, I can easily see the implementation being a nightmare. It's tricky enough deleting a node from a singly-linked list. I cannot imagine a problem this was invented to solve that could not have been solved more easily with multiple linked lists. Maybe the problem was non-technical, e.g. "get a patent to put on my résumé".
- bonzini 12y ago
  You could use the two lists to cache respectively a pre-order and a post-order visit of a graph. E.g. if you have 1->2 1->4 2->3 3->5 4->5 the lists could be [1,2,4,3,5] and [5,4,3,2,1].
  - throwawaykf05 12y ago
    1) There's no real pre- or post- order to this graph, just an arbitrary number of traversal orders, and 2) caching the traversals is a different data structure that no longer infringes this patent.

5 ms·

That's just a graph.

by chockey 12y ago

That's just a graph.

throwawaykf05 12y ago
It's not a skip-list, though it is some kind of a graph. I once tried to think of what kind of a graph it is, because it has some weird properties. It is a directed acyclic graph with 1) a fixed number of paths, 2) and each vertex occurs on each path exactly once, and 3) the paths are mutually exclusive, i.e. you cannot traverse one path half-way to a vertex and then follow another path from that vertex. I'm not sure if "mutually exclusive" is the right term... maybe a formal Graph Theoretic definition could be created based on some sort of coloring or labeling of edges. But when you put these properties together you essentially get a single structure representing multiple lists. That is, given items 1 - 5, you could arrange the pointers to traverse them in orders [1, 2, 3, 4, 5] or [1, 3, 5, 4, 2] or [5, 4, 1, 2, 3], but not [1, 5, 2] or [1, 2, 3, 2, 1]. What I don't understand is why anyone would put what is essentially a number of different lists into a single list. I see no advantages either in algorithmic complexity (traversal and addition/insertion/deletion operations are still the same complexity) or implementation. In fact, I can easily see the implementation being a nightmare. It's tricky enough deleting a node from a singly-linked list. I cannot imagine a problem this was invented to solve that could not have been solved more easily with multiple linked lists. Maybe the problem was non-technical, e.g. "get a patent to put on my résumé".
- bonzini 12y ago
  You could use the two lists to cache respectively a pre-order and a post-order visit of a graph. E.g. if you have 1->2 1->4 2->3 3->5 4->5 the lists could be [1,2,4,3,5] and [5,4,3,2,1].
  - throwawaykf05 12y ago
    1) There's no real pre- or post- order to this graph, just an arbitrary number of traversal orders, and 2) caching the traversals is a different data structure that no longer infringes this patent.