Prior art for linked list (secondary and tertiary traversal)?

Question

This is the first I've heard of this patent for linked lists and traversals filed in 2002. Note that the claim is not a patent on a linked list itself (discussion on Hacker News), but apparently on a doubly linked list, or a secondary traversal pointer.

A computerized list that may be traversed in at least two sequences comprising:

• a plurality of items that are contained in said computerized list; and
• 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,
  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.

Can we collate some verifiable prior art for this patent?

Answer 1

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.

Answer 2

Knuth, "The Art of Computer Programming", vol. 1 "Fundamental Algorithms", first edition, ca. 1970, shows a diagram of a sparse matrix implementation that uses precisely this technique. Each cell contains two links, one to the next nonzero element in the row, one to the next nonzero element in the column.

That would seem to constitute Prior Art, seeing as how that book is one of the Fundamental Texts of computing.

Answer 3

Philip Erdelsky's public domain "Linked-List Memory Sort" http://www.efgh.com/software/llmsort.htm, dated July 31, 1998, gives an example of a single data structure linked into two separate lists. Each element contains two "next" pointers. One chain of next pointers orders the elements alphabetically, the other numerically:

struct element
{
  struct element *next_in_alphabetical_order;
  struct element *next_in_numerical_order;
  char name[9];
  int number;
  /* other members, if any */
};

The page goes on to apply a function to sort the same set of elements according to the two different ordering criteria:

first_in_alphabetical_order =
  sort_linked_list(first, 0, compare_names, NULL);
first_in_numerical_order =
  sort_linked_list(first, 1, compare_numbers, NULL);

I believe that this example matches the claims rather closely.

EDIT: An earlier version dated February 23, 1996 was posted by the same author on their Caltech alumni account: http://alumnus.caltech.edu/~pje/llmsort.html

Answer 4

This also sounds similar to skip lists. In that case, though, you can have many pointers for a single object, not just two.

Answer 5

From a link from a previous HN discussion: http://www.reddit.com/r/programming/comments/1bbb3/congratulations_mingjen_wang_on_patenting_the/c1bc13

Unfortunately, some of the links in that comment itself are broken.

Note that while the claims only include a second "auxiliary pointer," it can be interpreted to include third, fourth or more auxiliary pointers. (It's kind of like the principle of induction in mathematics; you claim for n = 1 and n = 2, and by "induction", n = 3, 4... can be covered as well.) As such, the patent is really on having multi-pointer linked lists enabling multiple, different traversal orders (whereas a doubly linked list only enables traversing back and forth along the same order, which is a special case of this patent.)

However, according to the Reddit link above, apparently "Taming C++", published in 1994, clearly describes this method. (Disclaimer: I have not read the book myself and am only going by the Reddit comment.) (edit note: the google books link only offers snippet views).

Answer 6

In many Window management systems I've seen, a Window object has a point to a number of other related Window objects such as 'Next Sibling', 'Previous Sibling', Parent, 'First Child', Owned windows. This is a clear example of an object being on a list (every Window has a Parent) and also have an auxiliary pointer to some other object possibly on the same list.

I'm pretty sure this was in the internals of Microsoft Windows when I was there in 1999, but clearly I can't post the source code. It's highly likely there's similar examples in X Windows, but it's probably in the kernel-side representation - user space has Handles or References rather than pointers.

Answer 7

Another potential example of prior art is given in Wirth's classic textbook "Algorithms + Data Structures = Programs" (1976). In section 4.4.3 a data structure for topological sorting is described, wherein a list of nodes is maintained using next pointers, and an additional ("secondary") link provides the ability to traverse the nodes according to a partial order. This is on page 182 of my print edition. In a more recent pdf the same example is given on page 124: http://www.ethoberon.ethz.ch/WirthPubl/AD.pdf

Answer 8

I believe the concept of two-pointers in a list goes back to the works of Newell and Simon at Carnegie Institute of Technology or Rand Corp. in 1957. This is probably the first time the term "lists" as a data-structure description is used. This is a bit before LISP was invented.

Newell, Allen; Simon, H.A., The logic theory machine -- A complex information processing system.

Source: http://www.textfiles.com/bitsavers/pdf/rand/ipl/P-954_Programming_The_Logic_Theory_Machine_Jan57.pdf

Lists

Page 5

There should be no restriction on the nature of the items in a list. These might range from a single symbol or number to an arbitrary list. Thus it should be possible to make lists, lists of lists and lists of lists of lists, etc.

Pages 11/12

Lists are the general units of information in the memory. A list consists of an ordered set of items of information. Any item on a list may be either a list or an element, and these are fundamentally different types of units as we shall see later (the difference arises mostly from the fact that an element is contained in a single JOHNNIAC word) . Since a list is itself an ordered set of items which may themselves he lists, we obtain most of the flexibility we desire in the memory structure. There is no limit to the complexity of the structures that can be built up--provided that one knows how to use them - except the total memory space available. Also, there is no restriction to the number of lists on which an item can appear. For example, if we have a list of items, we can construct one or more indexes (lists) on each of which an arbitrary subset of the items of the original list appears. With each item located in a given list we may associate descriptive information without disturbing the general structure of the lists. That is, each item can'have a list of description elements associated with it. As many descriptions may be put on the list as desired, and, since they are self-identifying (by means of the description names they contain) they may be put on in any order. Descriptions are associated with the item on a given list; hence, if an item is on several lists, it can have several distinct description lists.

IPL-V Implementation

http://www.rand.org/content/dam/rand/pubs/research_memoranda/2008/RM3739.pdf

Page 4 (IPL-V Coding Sheet)

I've table-merged it with the data from the patent image.

Name    | SYMB    | LINK      IPL-V - Instruction Structure List / Coding Sheet 
--------+---------+----------
L1      | 9-1     | 100
100     | S4      | 101
101     | S5      | 0
9-1     | 0       | 200
200     | A1      | 201
201     | V1      | 202
202     | A2      | 203
203     | V2      | 0
---------------------------- The following items are from the patent image.
PtrAux  | Item    | PtrNext  Using their field names.
----------------------------
112     | 102     | 114
110     | 104     | 106
104     | 106     | 108
..down  | 108     | 110
108     | 110     | ..down  Down = downwards arrow, indicating more items.

Somehow, magically, it's the same structure. This might constitute Prior Art for the Claim "two pointers next/aux".

The implementation has additional fields PQ next to Name, Symb, Link, but they are only used as indicators or command flags, not used as pointers. This is not applicable for the "tertiary aux pointer" claim.

The claim of "tertiary aux pointers" is not covered here. Does something like this exist in LISP?

Answer 9

This structure could be used not only as a linked list, but also as a binary tree. Most naive implementations of a binary tree use a pair of child pointers like this, and sometimes also a parent pointer.

A more direct example which satisfies the claim would be a circular double-linked list. In this case the "first sequence" would be the forward traversal of the list, and the "second sequence" would be the reverse traversal.

I found such a structure quite easily in Linux 2.0 from 1996, as part of struct vm_area_struct which is defined in include/linux/mm.h. Specifically, the vm_next_share and vm_prev_share pointers are used to form a circular double-linked list which keeps track of shared memory pages.

The same structure also contains other pointers which are used to keep track of a straight single-linked list and a binary tree.