Linked List Patent

published: Fri, 24-Nov-2006   |   updated: Fri, 24-Nov-2006

OK, this is hilarious and points out the complete idiocy of the US Patent Office in judging any kind of algorithmic patent: someone has patented (and it was granted in April 2006, no less) a linked list that uses several pointers so that you can iterate the items in the list in one of many orders. And, to make the patent even more delicious, the inventor, Ming-Jen Wang, lives in Colorado Springs. Oh, please Ming-Jen, get in touch, so I can buy you a beer and shake the hand of such an amazing inventor!

This is amazing but true, so stop laughing at the back. The patent number is 7028023, so go and look it up (here's the official Patent Office page for it). I'll wait while you read it, so go ahead and be my guest.

Now the problem with this patent is the complete and utter wealth of prior art. Let's see, the most obvious prior art is, wait for it, the doubly-linked list. Funnily enough, the doubly-linked list maintains two pointers per node so that, shock horror, you can navigate through the items in a forwards or in a backwards direction. Wow-eee! And that my algorithmic reader friends is claim 1 of this junk patent:

1. A computerized list that may be traversed in at least two sequences comprising: a plurality of items that are contained in said computerized list; and a primary pointer and an auxiliary pointer for each of said items of said computerized list such that each of said items has an associated primary pointer and an associated auxiliary pointer, said primary pointer functioning as a primary linked list to direct a computer program to a first following item and defining a first sequence to traverse said computerized list, said auxiliary pointer functioning as an auxiliary linked list to direct said computer program to a second following item and defining a second sequence to traverse said computerized list.

If we imagine many nodes (a "plurality" of them), each with two pointers called — ooh, please sir, please sir, I know, I know — Next and Prev, and the nodes are linked together by the Next pointers, as well as by the Prev pointers so that a node's Prev pointer points to a node whose Next pointer points to the original one, we have a list that satisfies Claim 1 and is also known as our friend the doubly-linked list.

Despite the fact that I'm sure many people have written applications (I certainly have) in which a collection of items are stored in two separate sorted orderings (say, customer objects sorted by ID or by Name), which seems to be the main intent of this patent, it's flawed in many other ways.

For example, it says "The conventional method of searching a list is sequential." Well, duh. It's the only way of searching a list. Even if a list were sorted into some order (or in many orders), you would still have to traverse the list in a sequential manner in order to find a particular item. The only thing that sorting a linked list gives you is that you can cut the search short if the item isn't there. (Note, neither the patent or I are talking about array-based lists: the intent is linked lists, pure and simple.)

It also says "It would be further advantageous if the list could be quickly traversed in different sequences without resorting the list each time." Again, no shit, Sherlock. But amazingly, the patent says nothing about how these sequences can be set up. Think about it: if you have a collection of items, say, customer objects, sorted in ID and in Name orders using the ideas (I almost said common knowledge or axioms) in this patent, how would you insert another item in the list? Well, you would have to sequentially search through the first ordering until you got to the right place and insert the item there, and then you'd have to sequentially search through the second ordering in the same manner and insert the item in the proper place there. Man, all that sequential searching. Makes you yearn for a better data structure, eh?

The final sentence in the Summary just makes me laugh out loud: "The advantages of the present invention are that a list may be traversed in different sequences without resorting or sequentially traversing the list." Huh? "Traversing in difference sequences" by necessity implies "sequentially traversing the list."

Nice one, Ming-Jen. Oh, and you've been slashdotted too.