The Doubly-Linked List Appears to Have Been Patented

I saw a tweet today that said “The doubly-linked list, a structure I studied thirty years ago, has recently been patented.”  After giggling at the absurdity of the idea, I went and at a patent dated 4/11/06 that appears to be for the doubly-linked list.  The prior art was extremely thin, only went back to 1995, and didn’t mention that entire computer languages have been created around the list as a core data structure.  One of my first Pascal programming exercises in high school (in 1981 – on an Apple II using USDC Pascal) was to write a series of operations on lists, including both linked and doubly-linked lists (I always thought it was funny they were called “doubly-linked” instead of “double-linked” lists.)  Anyone who ever graduated from MIT and took 6.001 learned to love all varieties of the linked list, including the doubly-linked one.  That was 1984 for me by the way.

Ironically, Wikipedia had great entries – with source code no less – about both linked lists and doubly-linked lists.  The linked list history goes back to 2001, well before the patent was filed.  My understanding is that patent examiners aren’t allowed to use Wikipedia – I’m meeting with some PTO folks on Friday and I’m going to ask them if this is fact or fiction.  Regardless, this patent is another example of how ridiculous the situation has become.

  • Sateesh

    Nice, its time for someone to patent the bubble sort. Would be a profitable business model to take Knuth's Art of Computer Programming and start patenting algorithms – and then sell the patents to Apple, so they can sue Google, HTC, Microsoft and every other company in the universe.

  • I'm just glad i don't have to pay for every GIF i use anymore. 🙂

  • DaveJ
  • No shit! I even think in linked lists. Prior art only back to 1995? What, were we all just born yesterday or does no one car about link lists anymore? Totally absurd.

  • Anon Inventor

    The sad part is that if the patent-holder decides to take action against someone, the defendant cannot go to court and cite the prior art, as patents are presumed valid (innocent) until proven guilty at the patent office. The defendant must open up a legal front at the PTO, get the patent invalidated and/or its scope narrowed, before coming back to court and demonstrating the prior art argument.

  • Insanity.

  • A few years ago, blockbuster was being sued by netflix for infringing on its patent of the queue of movies. A queue.

  • Bill Mosby

    I'm sure I have mentioned this linked-list patent in a comment here not all that long ago. You should see some of the stuff in the area of 3-D graphics manipulation techniques that have been patented. And there was a "business method" patent on a golf grip (not the physical item, but the way you hold it) and also one for swinging on a swing with an elliptical motion. I swear to you that I am absolutely not making this up. My apologies to Dave Barry for borrowing that last line. Good thing that literary works aren't patentable, or I'd have had to pay royalties on that line. Ditto every two or three word combination in this comment, if examination for such worked as well as as that used on software patents.

  • Bill Mosby

    I think a lot of that may have been done already. Knuth himself testified before congress in 1994 that he had already by that time seen patents on code that his students routinely "invented" every time they did homework in his classes.

  • Bill Mosby

    I used linked lists in the programming course I took in 1968.

  • Manjeet

    So next time when they teach doubly linked list in college… college and we both will be payin royalty to some nutcase… calling it is own.

  • manjeet I don't think after being education system have to pay the royalty but it may that publishers have to give them royalty to publish their research and it should be.

  • I vaguely remembered that when I was poking around – thanks for the comment.  I’d love to see the golf grip business process patent – I saw some physical golf grip patents when I poked around for a minute but couldn’t find the business method one.

  • heh patent the in place merge sort and then sue oracle for infringement… they have enough money i may never have to work again =)

  • Maybe everyone who use(s) a VAX or VAX emulator is in violation?

    The INSQUE and REMQUE instructions (for the VAX-11) worked on doubly-linked lists.
    You can read all about them in "VAX Architecture Handbook, Volume 1 – 1977" from Digital Equipment Corporation.

    I preferred the interlocked version – INSQHI

  • Bill Mosby

    Here's the one for swinging: Patent number: 6368227, "Method of swinging on a swing" Steven Olson

    This is one for gripping a golf club: Patent number: 7261652, "Method of holding a putter and putting a golf ball" Thomas Robert Gold. Not sure if it's the one I saw before, but it'll do.

    Here is one other interesting one, from Proceedings of SAICSIT 2005, Pages 217–225, by Bob Jolliffe, School of Computing, University of South Africa, article titled "The Word-processing Patent – a Sceptical View from a Person Having Ordinary Skill in the Art". From the abstract: "In April of 2004 a patent was published by the South African patent office entitled: “Word-processing document stored in a single XML file that may be manipulated by applications that understand XML”. The description refers to a word-processing program which reads and writes documents in a native XML format."

  • Jamie

    Wait, does this mean that the singly-linked list is still available to patent? I will own you LISP, mwahahahaha

  • Then I'll own the same implementation in Scheme, the Lisp variant used in the 6.001 course that Brad referred to above.


  • This "you can't use Wikipedia" thing pisses me off (I'd be really interested to hear about your meeting at PTO).

    Of course, Wikipedia itself shouldn't be cited as an authoritative source, but why couldn't PTO (or my daughters when working on school projects) use the bibliography of a Wikipedia article to re-do the research done by the article's authors?

  • Bill Mosby

    PTO is not the only one to ban Wikipedia. I work for an online tutoring service, and occasionally help students find references to information on the web. The tutoring service will instantly deactivate me if I give a student a reference to Wikipedia, even if the reference is a link on another web page (unless it was so well hidden that it was hard to see). Seems that libraries, through which a lot of students access the tutoring service, are highly allergic to Wikipedia. Or so I am told.

  • Michael Birdsong

    After implementing Network Address Translation functionality in the Internet Routers of my employer at the time (the late Compatible Systems, here in Boulder), I later found out that Cisco Systems held a patent on that IP networking feature. Oddly, I found this fact out about a year after Cisco Systems had acquired Compatible Systems.

    I was working with doubly-linked lists back in 1995 on a 'video game for the US Navy' project at Ball Aerospace. I find it very strange that someone has now 'patented' such a basic data manipulation/access/storage algorithm.

  • Guest

    Patent attorney here. This statement is completely incorrect. The defendant is free to challenge the patent in court and/or the PTO based on prior art and numerous other defenses.

  • The thing is that there's research that shows that Wikipedia is very accurate.

    and, of course:

  • Bill Mosby

    I use it all the time for math and physics refreshers; I know the stuff but have to look up things from time to time. And I always find it accurate in those areas. In many other things I have first hand knowledge of, I also find it to be accurate.
    There's no real problem as far as I'm concerned.

    One other good source for finding prior software art is the Association for Computing Machinery publications database. It goes back to the 70s online at least. But it does cost a couple of hundred dollars per year to get access to it.

  • Guest

    >> My understanding is that patent examiners aren’t allowed to use Wikipedia – I’m meeting with some PTO folks on Friday and I’m going to ask them if this is fact or fiction.

    Patent attorney again . . .

    It's a little more complicated than a blanket prohibition against using Wikipedia entries as prior art evidence, Brad. Assuming the publication date of the Wikipedia entry can be authenticated, a Wikipedia entry is available to be cited as prior art for its content. However, a statement in a Wikipedia entry that some device or system existed as of a particular date would not be available as prior art because the veracity of that statement can't be assessed. To make a non-patent analogy, a statement like this is basically hearsay, which is not admissible as evidence under administrative law standards which govern proceedings in the USPTO. By contrast, if the Wikipedia entry provides a footnote with a link to a publication that describes the system or method then that publication would be admissible as prior art.

    The PTO does not encourage examiners to use Wikipedia because it raises a number of thorny evidence issues like this. Examiners have access to lots of prior art databases of original content. The inclusion or exclusion of Wikipedia is not a meaningful contributor to search and examination quality. The primary contributing factors are poor English language skills in the Examiner corps and lack of proper motivation.

    Hope that helps.

  • Everything you wrote above makes sense. What doesn't make sense is granting a patent on the concept or implementation of a doubly-linked list.

  • Don't you mean "UCSD Pascal?"

  • Guest

    Thanks, Steve. I can't disagree with you. It looks like this patent issued in 2006, before KSR. If it's any consolation it is almost certainly invalid after KSR. I doubt anyone would bother to assert it today.

    The PTO is staffed with humans, and like any organization or process that relies on humans it makes mistakes. They get about 500,000 applications per year. All in all they do a pretty good job of separating the wheat from the chaff. Sometimes things fall through the cracks.

    Companies will typically apply a pretty strong reality check before asserting a patent. Patent litigation is expensive, distracting, and generally bad for publicity. A patent like this one would be unlikely ever to pass the reality check of a pre-assertion due diligence. I suspect the economic consequence of the existence of this patent will be zero.

  • Bill Mosby

    From the patents I have read in the area of 3D graphics editing and manipulation, it seems they have not used any ACM publications or other scholarly publications for research either.

  • Bill Mosby

    That could be true now for all I know. But there are a whole slew of bad patents dating from several years ago. As long as it takes lots of money to defend against a bad patent, the problem will persist and anybody who starts to make money on a piece of software which incorporates even only techniques well known to programmers for a couple of generations is liable to be subject to great expense if somebody holding one of those bad patents wants to make an issue out of it.

  • Yup – that would be late night dyslexia kicking in.

  • DaveJ

    There should be an option for the defendant to file a summary judgment motion, such that if even one instance of valid overlapping prior art is presented, not only is the case over but the patent is immediately invalidated and the plaintiff is liable for defendant's legal fees. This way if the case is a no-brainer (which many prior art situations are), the judge can throw it out without a long and expensive process.

    That is, if we keep software patents at all, which we shouldn't.

  • DaveJ

    Wikipedia is not a source, it's a route to sources. The examiners should use Wikipedia to find sources, because it is a darn good way to do so. Once the actual sources are identified, these can be used as more than hearsay.

  • Bill Mosby

    Sounds good. I wonder if we should recognize that in some cases the PTO might be at fault for granting the patent? Although I think that really the "inventors" probably know that their inventions may not really be valid in most cases.

  • Guest

    Same patent attorney here, Dave. Defendants can file a motion for summary judgment based on one or more pieces of prior art that might render the patent invalid for obviousness or anticipation. If the defendants win the case is over and the patent is immediately invalidated. This is happening with increasing frequency in the wake of KSR.

    So the situation is exactly as you would have it with the exception of attorney fees, which are awarded only in exceptional cases.

    Defendants can also have the patent reexamined at the PTO, which is much cheaper than litigation. Courts are mixed on whether they will stay litigation pending the outcome of a reexamination. The trend is toward staying litigation pending the outcome of reexamination, which is a good thing.

  • As a patent attorney I imagine you know all of the problems surrounding this especially if a mistake is made by the court (as it often is) and the patent is not invalidated by the prior art.Furthermore the lack of quick and straightforward summary judgments on patent invalidation just makes things all that more of a mess.

  • Actually I wouldn't expect them to use Wikipedia as the direct reference. Rather, I'd expect them them to use Wikipedia to ge a better understanding of historical context and – more importantly – use the footnotes referenced in the wikipedia article to get to actual source publications that can be used.

  • Mike Greczyn

    Has anyone considered giving patent trolls a taste of their own medicine by trying to get a business method patent around the concept of an NPE? I know this sounds vaguely ridiculous and I'm not a patent expert so I have no idea if it would be possible or effective. But it sure would be funny!

  • Mike Grecyzn

    Has anyone tried patenting the various business methods of a patent troll? Might be a profitable enterprise. I doubt any patent trolls have had the guts to bluntly describe how they make their money.

  • Yup – there is at least one patent “in the system” (filed, not granted) that covers this.

  • Hans

    A bit late, I know, but I'm surprised that no one has pointed out that the patent really isn't on doubly-linked lists per-se, but rather on a singly-liked list with one or more "auxiliary" pointers to traverse the list in alternate sequences. I think the standard notion for doubly-linked lists is that the the second pointer always points to the previous item.

    One view is that the patent is a more general concept allowing any number of alternate sequences, whereas the doubly-linked list is limited to only forward and backward. Another view is that the doubly-linked list allows removal from any point in the list, while this would be quite difficult using the patent invention.

    • Araybould

      The doubly-linked list is a special case of what is claimed in this patent, and so would be covered by it, if it is valid.

  • I violated this patent for the first time in the mid 90s when I took "Introduction to C programming" at a local college.

  • Araybould

    I'm not a lawyer, but an English-language reading of claim 4 suggests the scope of this patent includes every computer system capable of operating on these lists in the prescribed manner, regardless of whether it is actually used to do so – i.e. every general-purpose digital computing system ever created!

  • Pingback:

  • Pingback: cheap online auto insurance()

  • Pingback: Sayreville()