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.