This isn't exactly about a doubly-linked list, but rather about an object that contains two “next” pointers that let it be included in two unrelated linked lists. While a doubly-linked list is a special case of that, you'd need to argue that the generalization is obvious (and I don't think it is) or find prior art for it anyway. So let's look for prior art for nodes that can be included in two linked lists.
I'm sure that this is about as old as linked lists themselves. However, I'll stick to a more recent (but still prior) example that I found by googling “two next pointers”.
In the source code of Gcc 3.0, released on June 18, 2001 (hence prior art), such a data structure is used in the file gcc/conflict.c
.
Quoting from a comment in that file:
the arc data structures are threaded by a set of linked lists by single reg number. Since each arc references two regs, there are two next pointers, one for the smaller-numbered reg and one for the larger-numbered reg. This permits the quick enumeration of conflicts for a single register.
The rest of the file, and the code, describe the data structure and demonstrate its use. Checking the patent's claims:
a plurality of items that are contained in said computerized list
The arc data structures.
a primary pointer and an auxiliary pointer for each of said items of said computerized list such that each of said items has an associated primary pointer and an associated auxiliary pointer,
smaller_next
and larger_next
said primary pointer functioning as a primary linked list to direct a computer program to a first following item and defining a first sequence to traverse said computerized list,
said auxiliary pointer functioning as an auxiliary linked list to direct said computer program to a second following item and defining a second sequence to traverse said computerized list.
This is the use of the two next pointers as described in the comment above.
This Gcc prior art does not teach claim 2 (with the addition of tertiary pointers), but once the leap to two lists has been made, allowing for more is obvious (it is well-known that programmers count “0, 1, 2, many”).
Claims 3 and 4 define the method to traverse the two lists and a system capable of performing the method, they are not inventive in their own right.