A patent was just issued for the Linked List — no kidding!

If there was ever an example of what is wrong with software patents, this has got to be a classic:
http://www.google.com/patents?vid=USPAT7028023&id=Szh4AAAAEBAJ&dq=linked+list

If the patent office can issue a patent for something as ubiquitous as the linked list, and do it in 2006 (nearly 40 years after Knuth described it in his Art of Computer Programming series), then how can they be trusted to properly investigate prior art on anything?

With your help, perhaps we can stamp out software patents in our lifetime!

About these ads

13 responses to “A patent was just issued for the Linked List — no kidding!

  1. No way! I was miffed when Unisys had the gif lzw patent but this is just silly.

  2. Hmm.. just like all the other monkeys that read the headline on reddit, but didn’t bother to take 2 minutes to actually read the patent..

    Go read it please. Not saying it’s any kind of wonderful thing, but it’s NOT a patent on “the Linked List”.

  3. The title of the patent is misleading–it does not describe the traditional linked list [http://en.wikipedia.org/wiki/Linked_list]. The patent doesn’t seem to describe anything that others haven’t been doing with nested hashes (Ruby, Perl, …). The data structure may be more appropriately labeled a “multi-linked list”.

  4. But consider the case where “multi” equals 2, and the second sequence is the reverse of the first sequence. That’s a doubly-linked list. As far as I can tell, it’s included in the description of the claims of the patent. I see nothing which says the two sequences must be independent.

    It’s obvious from the example drawings in the patent that a doubly-linker list isn’t what the filer had in mind. But the description is so general that it does include the doubly-linked list in the claim.

    Ideally, this would be a honeypot – someone has deliberately issued this patent, hoping to lure some patent troll into wasting money on a court case where the prior art is in one of the most widely-used CS texts ever.

    More likely, the patent examiners know nothing about programming, or weren’t paying attention, or both…

  5. Yes, a doubly-linked list does fall inside the description of the data structure in this patent; however, it’s an “idea” that also goes further than that. And, what do you know, ideas are patentable!

  6. The idea at its root is a ‘collections node’ with more than one traversal capability. We used something like that years ago adding a parent pointer to red-black tree-nodes. My guess is that anyone involved in collections processing has done something that exmplifies this prior art. It is like patenting vegetables after eating a french fry.

  7. however, it’s an “idea” that also goes further than that. And, what do you know, ideas are patentable!

    That may be so, but I personally believe this is bad and the patent law should be changed.

    Anyone more patent-savvy than me know when it became allowable to patent ideas? I know this was not the case years ago.

  8. This is the best news I’ve heard all day. At my next job interview, when they ask me the same stupid “Reverse a linked list” question, I can tell them that its my policy not to violate other people’s intellectual property.

  9. Patents have always been ideas.

    Your headline remains incredibly misleading.

  10. Patents have not “always been about ideas”. In the past you actually had to have a working model to get a patent.

  11. While patents have always been *about* ideas, the fundamental patentable object must be (and still is) an implementation of that idea. The acid test: is there enough of a description that would enable someone versed in the art to implement the thing? In this case, yes, there’s enough detail in the description, so it’s not “just an idea” being patented. Moreover, you don’t have to have the object in hand to get it patented, and it could even be something that, given current technology, cannot even be built (yet).

    In this case, the patent clearly reads on a *lot* of prior art (e.g., the doubly linked list, many forms of search trees, jump pointers for prefetch, etc.), so I think your headline is appropriate: the holder of this patent can go after pretty much anyone using any sort of dynamic list or even tree. Not saying he’d win, but every targeted company would have to go through the hassle of putting together a defense and spend a few days/weeks in court. A lot of people would rather just pay the guy than go through the hassle and expense (and take the risk of losing). Idiotic patents such as this (due to lazy? incompetent? paid off? examiners) can generate an enormous pile of headaches for the court system, and it is easy to argue that they hinder innovation and competition to a pretty significant degree (sort of the opposite goal that the patent system is aiming for).

  12. So, warp drive can then be patented, given that we cannot yet build it, but it’s a heck of an idea?

  13. Already done — warp speed – http://www.google.com/patents/US6960975

    “pushing said space vehicle forward in modified spacetime at a speed possibly approaching a local light-speed, the local light-speed which may be substantially higher than the light-speed in the ambient space.”

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s