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".
> 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.
Also,
> Go ahead and downvote me. Please.
Yawn. And you can't downvote someone's reply to your own post, btw.
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.
And I don't have any agenda here, other than to promote intelligent discussion about patents in a place where that happens too little.
... 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.
See what I mean?