[dpark]

Never (before you) have I heard someone talk about multiply-linked lists as simply being "linked lists". That term is generally reserved for the "standard" linked list types. Skip lists are also a variant of linked lists, but very few would generally refer to them simply as "linked lists".

Singly-linked and doubly-linked lists are taught as standard linked lists. Multiply-linked lists are not, because they are not especially useful in most cases. With a doubly-linked list (perhaps more clearly called a bidirectional linked list), all the standard algorithms work with minor or no modifications. With multiply-linked lists, even just inserting an element becomes much more complex. You're now traversing m lists for insertion instead of 1. I would question the quality of your CS101 course if your professor taught you about multiply-linked lists. It's a rather specialized data structure that is generally not beneficial. That time would have been better spent covering a more useful data structure.

I don't have an intro data structures textbook anymore, but I just checked "Introduction to Algorithms, 2nd Ed." and they do not seem to mention multiply-linked lists. "A list may have one of several forms. It may be either singly or doubly linked, it may be sorted or not, and it may be circular or not." For further evidence that multiply-linked lists are not widely considered simply "linked lists", I'll note that Wikipedia didn't mention multiply-linked lists as a variant until 2009. http://en.wikipedia.org/w/index.php?title=Linked_list&di...

As I've already said, I agree that the patent is invalid. It's not novel. But I do not agree that it's simply a "linked list". That term is far more generic and its usage without further clarification implies a much broader claim than the patent makes. Out of curiosity, where in the original Unix were these multiply-linked lists used?

As for why I infer anti-patent tendency, why post this at all except as an example of how the patent system is broken? And why assign it the very broad title "Someone patented linked lists" instead of, say, the more accurate (or at least more specific) "Someone patented a variation of linked lists"? Maybe because the former is more inflammatory?

[smussman]

Correct me if I'm wrong, but wouldn't a doubly-linked list be covered by this patent? If I understand the claims correctly, the backwards traversal would fall under claim 1.[1] It definitely provides a second sequence to traverse said list, even if it's stretching 'following' a little bit.

[1] The relevant part of claim 1 is:

  said auxiliary pointer being adapted to direct said 
  computer program to a second following item and defining
  a second sequence to traverse said list.

[dpark]

Sure. That alone probably wouldn't invalidate the patent, though. The claim is for a more generic capability.

Of course the patent is obvious and there's (almost certainly) prior art for the multiply-linked list anyway.

[xilun0]

I agree there is a risk of misinterpretation as in "all kind all linked lists have been patented, here is the patent" and for this reason, it maybe would have been better to get an even more precise title. By i'm technically still fine with the current one. The claims (both in the application and in the granted patent) barely talk about traversing the "primary" or the "auxiliary" list which provide another sequence (well, providing the same would be... useless), not any kind of tricky algorithm like efficient multiple simultaneous sorting or i don't know what, not even a plain and boring insertion is covered!

This is a special case of traversing multiple linked lists, which is a basic technique. I actually even hesitate to say it is a technique, or at least to distinguish this technique from the very same technique of using a single linked list, because I don't think I could ever come up with a plausible justification for why anybody previously knowing how to use one would not be able to use two. The restriction making this a special case is that all lists contain the same set of elements. Given the claims, that restriction is unnecessarily narrow and have no technical effect. So the only thing that distinguish this patent from a patent on a particular (but still 100% basic) use of single linked lists, is the phrasing, and the empty (still given the context) emphasis on the fact there are not one, but two, or even three lists.

So despite the fact that basic singly-linked lists + limited to one list by element would not be covered by this patent even in the parallel universe where it would be considered valid (and while we can note that on the contrary, prev/next linked list would), given that it only claims (with many more sentences) that if you have two lists, you can traverse one, or you can traverse the other, i will continue to argue that it covers linked lists, maybe under certain conditions, all right, but those conditions are insufficient to mandate the precision that this is a modification of linked lists, because it is not a modification, it is just about the basic traversal of multiple plain classical linked lists.

(Also, one a side note, I found it cute how the claims are structured, like if the author thought there was a possibility that prior art could be found for two pointers but not three.)

Edit: About the inflammatory part, it might as well have been even more inflammatory by being even more descriptive. Somebody has patented traversal of linked lists.

[dpark]

Someone else explained my problem with the title better than I managed. http://news.ycombinator.com/item?id=2875082

Imagine the headline read, "Gas up to $8.23 a gallon" and only upon reading the article did you discover that the "gas" they're talking about is 110 octane race gas. Yes, race gas is a type of gas(oline), but the headline is still quite misleading, as the common definition, without qualifiers, is the pump variety.

As for claims of the patent, it does really cover traversing at all. It mentions it, but the meat of the patent is the data structure having two or three pointers built in for traversing and choosing between those pointers for different traversals. This is all very obvious and frivolous, but it's not claiming the basics of traversing a linked list.

(As for your side note, I found that really strange as well. I can't imagine why thy specifically called out the cases of 2 and 3 pointers. Were they planning on filing later for 4 and 5 when they figured it out?)

[xilun0]

I argue that it's claiming the traversal of linked lists, provided you have a choice between at least two linked lists containing the same set of elements. I argue that this restriction is meaningless, because it has no technical impact in this patent. Even when the patent seems to try to be a little more broad, by trying to describe the data structure itself, this description also depends on traversal and nothing else: "[claim 1 ...] said primary function pointer functioning as a primary linked list to direct a computer program to a first sequence to _traverse_ said computerized list [...]" (x2 because the same thing is written for the "auxiliary" list, then x3 in claim 2 for the "tertiary" one).

There is never any interaction described between one list and the other -- so from the point of view of patenting I don't see anything difference between this patent and a mere description of basic single linked lists, description centered on its traversal (the various enumerations are to be considered as irrelevant in themselves, and are not supplemented by anything else).

That reason alone would be one of the major angle of attack of the patent, would it not be already even more basically invalid because of triviality and prior art. The only challenge would be to present those formal concepts using casual language clearly enough so that nobody would mistake this description as the description of a new structure (even in the hypothetical alternate universe where nobody ever previously used two lists at a times for ordering the same sets of elements)

There is no meat.

[ldar15]

Your appeal to "authority" doesn't change the fact that many of us have written data structures involving multiple traversal paths, that these paths are all lists, and that they are all linked, and further that in conversation with peers we have referred to them as Linked Lists.

Your appeal to "authority" requires the admission that Wikipedia actually supports the counter argument, while an Introduction to anything is hardly an appropriate authority for whether or not something is novel enough to be patented.

I'm glad you are responding to every single person claiming that their experience is wrong, because that provides ample opportunity to reduce your karma.

[dpark]

> Your appeal to "authority" doesn't change the fact that many of us have written data structures involving multiple traversal paths, that these paths are all lists, and that they are all linked, and further that in conversation with peers we have referred to them as Linked Lists.

Your argument doesn't change the fact that it's misleading to refer to any arbitrary linked data structure as a "linked list". You can call a skip list a linked list if you want, but that does't make it appropriate, and it doesn't redefine the language for the more general audience. Go ask your coworkers to draw a linked list on the board and see how many draw a multiply-linked list, or a skip list, or any number of other things that could be pedantically considered "linked lists".

Even if we were to accept the argument that "linked list" is just a generic term for data structures involving linked traversal paths, that would not make the HN title appropriate. If the term "linked list" were that generic, then it would be misleading to apply it to this patent, which clearly does not cover everything that would fall unto the generic "linked list" term.

> Your appeal to "authority" requires the admission that Wikipedia actually supports the counter argument,

Are you seriously trying to criticize my "appeal to authority" by making one of your own?

Nevermind the fact that Wikipedia didn't include the term "multiply-linked" until three years after this patent was granted...

> while an Introduction to anything is hardly an appropriate authority for whether or not something is novel enough to be patented.

Are you really that oblivious? I've said a dozen times that this is not a valid patent. That's not the point.

And an intro book is quite appropriate for establishing what a term covers to the general audience. If something is specialized enough that it's not covered in an intro book, then it's specialized enough that it should not be referred to by the generic term.

> I'm glad you are responding to every single person claiming that their experience is wrong, because that provides ample opportunity to reduce your karma.

Do you really think I care if you or someone else is childish enough to downvote all my comments?

[nitrogen]

I'm glad you are responding to every single person claiming that their experience is wrong, because that provides ample opportunity to reduce your karma.

Meta: Since your account is relatively new: I was ready to upvote your comment to try to bring it out of the gray text region (i.e. <=0), until I got to this paragraph. It's okay to think these things, but actually typing them out is considered bad form here. While we're on the subject, the rest of the comment does come across as a bit inflammatory.

Hope this helps.