Tell me more ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.
up vote 9 down vote favorite
4

Linked list

Ming-Jen Wang
Patent number: 7028023
Filing date: Sep 26, 2002
Issue date: Apr 11, 2006
Application number: 10/260,471

A computerized list is provided with auxiliary pointers for traversing the list in different sequences. One or more auxiliary pointers enable a fast, sequential traversal of the list with a minimum of computational time. Such lists may be used in any application where lists may be reordered for various purposes.

Does this mean that I need to acquire permission before using a linked list in my code? What about the code I write from my previous apps that uses a linked list? What about the framework that implements the linked list?

share|improve this question
14  
patent.SE already has a question about it – ratchet freak Oct 18 '12 at 6:19
20  
The patent system is seriously, seriously broken. BRB while I file a patent about a human input device utilizing small plastic pieces with letters on them that you can press. – Robert Harvey Oct 18 '12 at 6:21
5  
@RobertHarvey Just wait until I file a patent about a document that describes a set of exclusive rights granted by a sovereign state to an inventor or their assignee for a limited period of time in exchange for the public disclosure of an invention – JohnL Oct 18 '12 at 14:57
3  
@JohnL: Now that would be novel. – Robert Harvey Oct 18 '12 at 15:01
1  
Based on @Gilles description in his answer, there's a fairly old non-code version: TV shows, which have both a production order and a release order. – Izkata Oct 18 '12 at 18:11

closed as off topic by Jim G., MainMa, World Engineer♦, Matthieu, GlenH7 Oct 22 '12 at 18:12

Questions on Programmers Stack Exchange are expected to relate to software development within the scope defined in the FAQ. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about closed questions here.

5 Answers

up vote 8 down vote

First, that patent doesn't claimed linked lists in general. Note that when reading a patent, the title and abstract give you some vague idea of the context, but are usually worthless to know what the patent claims, i.e. what the applicant declares is new and expects a monopoly on. For that, you have to read the actual claim section, and decode the legalese back into something comprehensible (often, for algorithm patents like this one, the figures contain some flow diagrams that can help you figure it out; keep in mind that some figures might refer to the state of the art while others refer to the invented technique).

The patent claims a data structure which is a little more elaborate than a textbook linked list: the claimed data structure uses elements which are nodes in two separate linked lists. That is, there are two “next” pointers in each element; if you traverse the data structure by following next1 pointers, you get one linked list, and if you traverse it by following next2 pointers, you get another linked list which may consist of the same elements in a different order, or of different elements.

The claimed data structure is nowhere new. I haven't traced down who proposed it first, but I'm pretty sure it's only barely less old than linked lists themselves. See Prior art for linked list (secondary and tertiary traversal)? for some examples of prior art — description of the claimed method that existed before the patent application.

On that thread, someone suggested sparse matrices as a common case where these data structures are commonly used — one linked list structure for the rows and one for the columns.

If you want to be absolutely sure not to infringe on any of the myriad patents that may or may not be held up in court, your best bet is to scrupulously follow a technique that was published 20 or more years ago (patents expire — the exact rules vary by country but 20 years makes you safe from EU patents and mostly safe from US patents). That way you can be sure that even if someone claims you've infringed on their patent, then their patent would be invalid. That's not a guarantee that you'd win in court, merely that you'd have the right on your side. Of course, that does completely stifle innovation.

share|improve this answer
1  
+1 for actually looking into it. I was ready to comment something like "Isn't it describing a Skip List rather than a Linked List?", but I see now it's something even more different. – Izkata Oct 18 '12 at 18:08
up vote 5 down vote

This is not a simple linked list: rather it is a collection of nodes each holding data and several pointers to other objects, think of it like this:

Node - Data - pointer to next element (next as in was added to the list next) - pointer to next element (next as in holds the next spot were the list to be sorted) - pointer to next element (other walks through the list) - ...

Apart from what is actually described, you can easily find a lot of discussion on the validity of software patents (a quick result from ars:) When is software patentable?

In general, the problem seems to boil down to (in my mind) not-technical-literate people deciding on software patents, basically deciding on them without a good idea on what they actually entail.

Even normal patents seem to go to ridiculous heights: cfr the rounded corner patent.

I will not start the discussion here, there are already a LOT of forum threads anywhere handling this

share|improve this answer
10  
Great, so the patent describes graphs rather than linked lists. That's much better... – Telastyn Oct 18 '12 at 11:35
This answer is correct. Based on the drawings all one has to do to avoid infringing on this patent is to avoid a linked list with 2 pointers, there are many examples within the patent where the number of pointers is declared as "two". The lack of plurality could be grounds to make this patent invalid. Certainly a linked list can contained more then just two aux pointers to each object in the list. This patent could easily be made invalid, I see nothing special about having 2 pointers to each object, the drawing display a very simple process. – Ramhound Oct 18 '12 at 11:38
1  
@Ramhound - I'm pretty sure I've seen this used in a paper published by Siggraph in the '80s. You would think it would have been there just for this purpose. – Rob Oct 18 '12 at 12:57
@Telastyn of course it's better, linked lists are after all graphs, as well as binary trees are, so this patent is far more overarching than just linked lists, thus it's a "better" patent? :( – Jimmy Hoffa Oct 18 '12 at 15:04
1  
@psr - Will do. I moved recently but I think I know which box that was packed in. I'll look for it tonight. – Rob Oct 18 '12 at 18:48
show 3 more comments
up vote 0 down vote

No, that's not really about a linked list but several linked lists embedded in a single linked list like structure. I would just use a collection of linked lists holding references to the same objects in different orders instead.

share|improve this answer
1  
There is very little difference between a Structure and a collection Class ( i.e. an Array ). This isn't a very complete answer and fails on some of the technical details require to make it more complete. – Ramhound Oct 18 '12 at 11:28
up vote 0 down vote

As I recall, the first edition of Knuth vol. 1 contains a figure showing a sparse matrix implementation using exactly this technique.

I'd really enjoy hearing someone try to explain how Knuth vol. 1 first edition does not constitute prior art for a software patent.

share|improve this answer
If you can find the Knuth reference it would be a public service if you posted something about it at patents.stackexchange.com/questions/738/… – psr Oct 18 '12 at 18:21
up vote 0 down vote

Hmmm, a linked list with two links per node... Sounds slightly identical to a binary tree, doesn't it? It reminds me of another linked list actually is patented. It's a doubly linked list, where both pointers are XORed into one pointer. Bidirectional traversals work, but nodes can't find their neighbors, so every delete/insert requires traversal--all to save one memory word per node. Someday, they will patent addition and multiplication, and then we all can just ignore software patents.

share|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.