Via Grady Booch:

Fellow IBMer Jim Conallen pointed me to this report which indicates that the linked list data structure has been patented. A quick search at the USPTO verifies that this claim is real: the abstract for this patent may be found here . The patent was filed on September 26, 2002, the inventor being Ming-Jen Wang of LSI Logic Corporation , and subsequently US Patent 7028023 was granted last year, on April 11th, 2006.

I wonder just how many times this patent application was processed by software using linked lists in its implementation?

Looking at the abstract, I'd actually say that this isn't a patent for linked lists, at least not in the traditional sense. I can't access the images, but it seems that the idea is that each data element in the list has at least two pointers stored with it. The first pointer is to the next element as in a standard linked list, and the second pointer is to another element. Following the first pointers gives the canonical order of the list, whereas following the second pointers gives a differing ordering. If the elements are people, the canonical ordering might be sorted by last name, and the second ordering sorted by first name. Other orderings, e.g. order by age, can be added by adding an extra pointer to each item.

Personally, I'm happy to let Ming Jen Wang have his patent. Hard-coding the number of possible orderings right in the data structure seems like a bad idea. Linked lists are great for insertion and deletion, but the usage here seems to be more that a single, unchanging list needs to be sorted in many ways. In that case it would make more sense to allocate a separate array of pointers for each ordering. Adding and deleting orderings is then easy, and using each is fast. If you also want to add and delete items to the main list, simply make each ordering array itself a linked list.

So, while I would say this patent probably doesn't transgress too badly in terms of prior art, I would still have rejected it The USPTO home page says a patent must be "new, useful [and] non-obvious", and this for me fails the "useful" test. Even if someone shows an area where it's useful, then it still fails the "non-obvious" test. Teach linked lists to a class, then ask "but what if you wanted a second ordering too", and I bet more than one will come up with this.

Ironically, the USPTO home page currently trumpets their new accelerated process, citing a case where the average review time of 2 years was cut to 6 months. The trick? Rather than the USPTO searching for prior art, they let the applicant do it. Right...