Ok, to summarize said claims and said summary: 1) A data structure where each item has two (or three) pointers, and specifically it has to be done so that there are exactly two (or three) ways of traversing the list.
This is not a doubly linked list, nor does it resemble one: doubly linked lists have ONE ordering, each item using two pointers to point forwards or backwards with respect to the ordering. The point is that this patent presents a completely and utterly useless data structure. A linked list is not made for searching quickly. But yet, the patent claims:
"The conventional method of searching a list is sequential. This involves traversing the list to locate a specific item in the list. [...] The conventional method is time consuming and may require many computational cycles to find the necessary items in the proper sequence."
This method is not conventional. It's the only method. That's the whole point of linked lists. Then it continues:
"Lists may be sorted so that the items may be accessed sequentially. Once the list is sorted into a particular sequence, the individual items may be accessed in order very quickly. However, there is substantial overhead in the reordering of the items into the desired order."
If it means accessing an individual item randomly, this cannot be done, unless the list is first sorted into an array and use binary search, which breaks away from the linked-list structure. If it means accessing all items in order, then no, there is no substantial overhead in the reordering of the items.... it's the same overhead as accessing the items in order.
Then the conclusion sums up these fallacious arguments into its climax:
"In some cases, there is a need for the list to be presented in more than one order.... It would therefore be advantageous to provide a system and method for quickly traversing a sequential list in a second sequence."
Indeed it would be nice to quickly traverse the list in a different order. But first this does now allow us to search better (as suggested in the first paragraph), nor is the new data structure more efficient than other data structures out there (you CANNOT do better than linear time sorting if you need to traverse the list!).
This is like a classic example of a "bad, horrible" data structure that undergraduates are asked to analyze in a homework question, like "here's a data structure. Write a paragraph showing why it isn't a good idea. Can you come up with something better?"
Notice that this structure does NOT allow constant time insertion/deletion, which is the whole point of linked lists (the tradeoff for not being able to search quickly). Without a tree structure, there is no way of knowing where to insert a random element, except to prepend or append it to the list. So when insertion/deletion is frequent, binary search trees are better, as they still allow linear time traversal. If search time is critical, use hash tables. If one needs multiple orderings, then use multiple index trees (aka database). When the data is fixed and never changes, then multiple arrays storing values and pointers to the items are better, because they not only allow linear time traversal, but also fast search. I can go on and on here... to put it bluntly, the said data structure is a new idea, in the sense that it's so stupid no one would actually use it (and thus would never mention it).
Don't worry guys. This patent managed to dig so low technically that it is worse than obvious data structures. And if anyone is dumb enough to pay them for such patent... well, natural selection.
Slashdot Mirror
Ok, to summarize said claims and said summary:
... It would therefore be advantageous to provide a system and method for quickly traversing a sequential list in a second sequence."
1) A data structure where each item has two (or three) pointers, and specifically it has to be done so that there are exactly two (or three) ways of traversing the list.
This is not a doubly linked list, nor does it resemble one: doubly linked lists have ONE ordering, each item using two pointers to point forwards or backwards with respect to the ordering. The point is that this patent presents a completely and utterly useless data structure. A linked list is not made for searching quickly. But yet, the patent claims:
"The conventional method of searching a list is sequential. This involves traversing the list to locate a specific item in the list. [...] The conventional method is time consuming and may require many computational cycles to find the necessary items in the proper sequence."
This method is not conventional. It's the only method. That's the whole point of linked lists. Then it continues:
"Lists may be sorted so that the items may be accessed sequentially. Once the list is sorted into a particular sequence, the individual items may be accessed in order very quickly. However, there is substantial overhead in the reordering of the items into the desired order."
If it means accessing an individual item randomly, this cannot be done, unless the list is first sorted into an array and use binary search, which breaks away from the linked-list structure. If it means accessing all items in order, then no, there is no substantial overhead in the reordering of the items.... it's the same overhead as accessing the items in order.
Then the conclusion sums up these fallacious arguments into its climax:
"In some cases, there is a need for the list to be presented in more than one order.
Indeed it would be nice to quickly traverse the list in a different order. But first this does now allow us to search better (as suggested in the first paragraph), nor is the new data structure more efficient than other data structures out there (you CANNOT do better than linear time sorting if you need to traverse the list!).
This is like a classic example of a "bad, horrible" data structure that undergraduates are asked to analyze in a homework question, like "here's a data structure. Write a paragraph showing why it isn't a good idea. Can you come up with something better?"
Notice that this structure does NOT allow constant time insertion/deletion, which is the whole point of linked lists (the tradeoff for not being able to search quickly). Without a tree structure, there is no way of knowing where to insert a random element, except to prepend or append it to the list. So when insertion/deletion is frequent, binary search trees are better, as they still allow linear time traversal. If search time is critical, use hash tables. If one needs multiple orderings, then use multiple index trees (aka database). When the data is fixed and never changes, then multiple arrays storing values and pointers to the items are better, because they not only allow linear time traversal, but also fast search. I can go on and on here... to put it bluntly, the said data structure is a new idea, in the sense that it's so stupid no one would actually use it (and thus would never mention it).
Don't worry guys. This patent managed to dig so low technically that it is worse than obvious data structures. And if anyone is dumb enough to pay them for such patent... well, natural selection.