> What is a data structure if not an implementation?
The patent is a cartoon of a half-baked idea. It does not even describe how to implement element addition or removal. (Unless the caller maintains some special structure, many O(1) list operations become O(N). Removal is delicate because you need all incoming pointers.). It's unclear whether the "inventor" ever implemented the data structure.
First, it should be obvious that I was not defending this patent. Attacking the patent as "a cartoon of a half-baked idea" is pointless, and doesn't answer my question at all.
Second, the patent describes an implementation that allows multiple traversals. That it doesn't cover addition or removal seems irrelevant. The patent is for the structure that allows the traversals. You could build up the structure in a number of ways, but the end result would be the same.
"The implementation of a data structure usually requires writing a set of procedures that create and manipulate instances of that structure." (http://en.wikipedia.org/wiki/Data_structure)
If you gloss over construction and modification details, this "invention" is entirely covered by "Fortran-style" linked lists which have been in common use since the 1950s. (Store the primary list in an array, then have one or more integer arrays containing the index of the next node. Relative to storing the "aux_next" pointer inside the node, this allows dynamically creating and destroying an arbitrary number of indices.)
I don't think the patent office or judicial system generally refers to Wikipedia for what constitutes an implementation.
This invention is obvious and trivial and there seems to be lots of prior art. I'm not sure why you still seem to think I'm defending it. Regardless, describing how these lists should be constructed would not make this any less trivial or obvious.
The original point made by vonmoltke was that the patent text does not define an implementation in any meaningful sense. My wikipedia link was merely corroborating my opinion that an implementation of a data structure involves the fundamental operations on that data structure. If a data structure implementation can be complete without such details, then an AVL tree is equivalent to a red-black tree.
Ironically, what you're asking for is not a more complete implementation, but more algorithms. If I patent a mechanical device, it's not expected that I describe how to build the device. That's not the invention, and it's not the implementation (it's an algorithm for producing an implementation). Likewise, if the patent is on the in-memory structure that allows for multiple list traversals, then describing how to build that structure is pure algorithm, not implementation, and outside the scope of the patent claims.
The patent is a cartoon of a half-baked idea. It does not even describe how to implement element addition or removal. (Unless the caller maintains some special structure, many O(1) list operations become O(N). Removal is delicate because you need all incoming pointers.). It's unclear whether the "inventor" ever implemented the data structure.