5 ms·

At first I thought that too. But within 1 or 2s, I remembered that linked lists have never been limited to single linked lists (except maybe in poor quality cou

by xilun0 15y ago

At first I thought that too. But within 1 or 2s, I remembered that linked lists have never been limited to single linked lists (except maybe in poor quality courses), multiple linked lists have been around since Unix and very very probably before, have nothing inherently special, so it's absolutely all right to both simply call them "linked list" (like the patent properly does in its title) and to consider them as CS 101. The patent is both obviously invalid and properly named "Linked List". That it is does not cover the single linked list special case does not changes this fact. The title is neutral, and you are inferring an anti-patent tendency from a neutral reporting (from which crowd btw?). I would be hugely curious to hear on which base you inferred that.

dpark 15y ago
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&diff=284781514&oldid=284772880 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 15y ago
  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 15y ago
    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.
    - deleted 15y ago
      [deleted]
- ldar15 15y ago
  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 15y ago
    > 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?

by xilun0 15y ago

dpark 15y ago

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&diff=284781514&oldid=284772880 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 15y ago
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 15y ago
  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.
  - deleted 15y ago
    [deleted]
ldar15 15y ago
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 15y ago
  > 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?