Why Real Programmers Don't Take The USPTO Seriously: Doubly-Linked List Patented

from the oh-come-on dept

It's pretty difficult to find software engineers who take the patent system seriously. There are a few, but it's still pretty difficult. For the most part, they recognize that code is just a tool: you can make it do all sorts of things, given enough time and resources, but that doesn't mean that doing any particular thing in code is an "invention" that no one else should be able to do. And then, sometimes, they discover that something pretty basic and old has suddenly been given a patent. Brad Feld discusses his discovery that doubly linked lists were apparently patented in 2006 (patent number 7,028,023):
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.

Another day, another reason to question why software is patentable at all -- and to question who approves these kinds of patents.

Filed Under: doubly-linked lists, patents, prior art, uspto

Reader Comments

Subscribe: RSS

View by: Time | Thread

  1. identicon
    Pseudonym, 23 Mar 2010 @ 5:46pm

    Re: Not doubly-linked list!

    Gah, posted before I finished.

    I looked through some old source code, and I did find an example of a general subset/reordering problem from the 4.3BSD source code circa 1986. Each process belongs to two doubly-linked list:

    • The run queue or sleep queue (depending if it's runnable or sleeping).
    • The list of all active or all zombie processes (depending if it's active or zombie).

    Linux today maintains no fewer than 14 pointers per task, and the code to do this predates 2006 by quite a while.

    While that's the oldest source code I could find, it's not the oldest reference to the technique in the literature. The original paper on the DLX algorithm, popularised by Knuth in 2000 or so, was submitted for publication in 1978 by Hitotumatu and Noshita.

    And, of course, compilers have been using multiply-linked lists for symbol table management essentially forever, since back in the day, you had to maintain both links to manage the hash table and links to manage nested namespaces. I have a book written in 1979 by Richard Bornat which describes a symbol table organisation which uses five pointers per node. The technique was considered to be well-known even then. I seem to recall, for example, the BLISS/11 monograph talking about multi-pointer lists for various tasks; that was written in 1974 about code written in 1971.

    I think it'd be hard to find an earlier published reference than that for a very simple reason: Programmers don't like wasting time stating the obvious. And this is as obvious as it gets.

Add Your Comment

Have a Techdirt Account? Sign in now. Want one? Register here

Subscribe to the Techdirt Daily newsletter

Comment Options:

  • Use markdown. Use plain text.
  • Remember name/email/url (set a cookie)

Follow Techdirt
Insider Shop - Show Your Support!

Report this ad  |  Hide Techdirt ads
Essential Reading
Techdirt Deals
Report this ad  |  Hide Techdirt ads
Techdirt Insider Chat
Report this ad  |  Hide Techdirt ads
Recent Stories
Report this ad  |  Hide Techdirt ads


Email This

This feature is only available to registered users. Register or sign in to use it.