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.