5 ms·
The claims are very closely aligned with the title. Claim 1 - Linked list with two traversal orders Claim 2 - Linked list with three traversal orders Claim 3 -
by mancaus 15y ago
The claims are very closely aligned with the title.
Claim 1 - Linked list with two traversal orders
Claim 2 - Linked list with three traversal orders
Claim 3 - Method of traversing the lists in claim 1 and 2
Claim 4 - A device (computer) to traverse the lists in claim 1 and 2
- monochromatic 15y agoWhat is claimed is very clearly not just a standard linked list. We can argue about whether this patent should have been granted, and whether its claims are invalid... but there can be no dispute about whether this person has "patented a [scratch that, the] linked list."
- fjh 15y agoBut they have patented "a linked list". They haven't patented all linked lists and they haven't patented the standard trivial singly-linked list, but "a linked list" is what they seem to have a patent on.
- monochromatic 15y agoThat's pretty pedantic, and I can't imagine a single person actually understood my comment to mean what you said. But I've edited it, just the same.
- fjh 15y agoIt's not pedantic, because I think you are misrepresenting the author. You're edited "quote" is not actually what he said, but you justify not reading the article using your misreading of the sentence you quoted.
- monochromatic 15y agoI don't think so. Every patented invention is also an instance of a broader, unpatentable class. Patent a novel electric motor that gets better efficiency than anything ever made before? Well, obviously the examiners don't know what they're doing, because you just patented an electric motor. See what I mean?
- rtperson 15y agoVery clearly my ass. From the patent: > The present invention overcomes the disadvantages and limitations of the prior art by providing a system and method for traversing a list using auxiliary pointers that indicate the next item in a sequence. The "invention" here is called a sentinel, and have been used in conjunction with linked lists since time immemorial. For "prior art" I would refer you to CLRS. Go ahead and downvote me. Please.
- monochromatic 15y agoLike I said, we can argue about prior art. But are you really saying that these claims cover a standard linked list? Also, > Go ahead and downvote me. Please. Yawn. And you can't downvote someone's reply to your own post, btw.
- rtperson 15y ago> But are you really saying that these claims cover a standard linked list? That's exactly what I'm saying. For all the patent's talk of primary, tertiary, and secondary pointers, the "invention" here is a standard linked list with sentinels. If I hired a patent attorney to write patents against the programs I wrote for my freshman-year data structures course, the results would be much the same.
- monochromatic 15y agoI don't read these claims as referring to a sentinel node. Could you explain how you got there? (Note: I'm not really a programmer... I just tinker a little bit. So I could be wrong about that.) And I don't have any agenda here, other than to promote intelligent discussion about patents in a place where that happens too little.
- gjm11 15y agoNo, the invention here is not a sentinel. It's having a bunch of things each of which has two or more next-item pointers so that you can traverse the list in two or more different orders. For instance, this would cover any doubly-linked list. ... Which is pretty strange, actually, since the patent itself references prior art involving doubly-linked lists. Maybe that's why they had a separate claim for a list with three "next" pointers in each node. I have no idea why claims 1, 3 add 4 weren't thrown out by the examiner given that everything they describe is done by every doubly-linked list implementation anywhere ever. (Claim 2 looks obviously not novel to me, but it's not quite such a slam-dunk as the others.) So, anyway. The patent is preposterous. It isn't a patent on The Linked List. It doesn't involve sentinels. It doesn't cover any singly-linked list. It does cover any doubly-linked list (which is one reason why it's preposterous). The author of the OP is right about the patent's preposterousness but wrong to describe it as "patent[ing] a linked list". monochromatic is right that the patent isn't a patent on the linked list, but arguably wrong to think this proves the original author is a twit (perhaps s/he knows perfectly well what the patent purports to cover, but preferred terseness to precision). rtperson is wrong to say that the patent is about "a standard linked list with sentinels", wrong to be obnoxious about it, but probably right that there's prior art in CLRS at least for claims 1,3,4.
- harshreality 15y agoIt patents a multiply-linked list, for 2 and 3 links. I don't think most programmers would make the distinction because it's a natural extension to the linked list. The idea is trivial, and theoretical computer science literature is full of much more complicated graph-based data structures, of the form node + n pointers, each pointer having a different type/color/characteristic. There is no functional difference between the patented data structure and 2 or 3 separate linked lists, other than storage space and ease of altering node data that's shared between lists. No mention is made of traversal using varying types of link/edge depending on internal state; the patent describes traversal using [one set of] the auxiliary pointers exclusively. Although you may have a point that this patent does not cover the canonical 1-pointer linked list, LSI nevertheless patented a very small subset of common graph structures, which were well known (not novel), trivial, and which I think most programmers still call "linked lists".