Take the 2-minute tour ×
Ask Patents is a question and answer site for people interested in improving and participating in the patent system. It's 100% free, no registration required.

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?

share|improve this question
add comment

9 Answers

up vote 34 down vote accepted

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.

share|improve this answer
1  
An anonymous visitor suggests to look for prior art in sparse matrix representations. –  Gilles Oct 17 '12 at 17:21
    
@JerryCoffin Ah, yes, this US oddity. Good point. This actually doesn't matter, because that code and comments had been written and released in gcc 3.0, more than a year before. –  Gilles Oct 17 '12 at 20:50
    
Well, it's obvious to me. It's just a mundane generalization of a doubly-linked list. Nothing novel to see here, move along. –  Robert Harvey Oct 18 '12 at 6:20
2  
or a specialization of a directed graph? –  jk. Oct 18 '12 at 8:58
1  
in fact a DAWG would fit very well here I think as it also has the concept of a first node –  jk. Oct 18 '12 at 12:18
add comment

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.

share|improve this answer
    
What page? Any chance you can scan in or refer us to this diagram? –  SamtheBrand Dec 10 '12 at 21:23
    
No, unfortunately. My copies of Knuth vols 1-3 are currently boxed up in climate-controlled storage, pending a move to larger digs that may not happen any time soon. Any good library should be able to lay hands on a copy, through interlibrary loan if necessary. –  John R. Strohm Jun 7 '13 at 3:06
add comment

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

share|improve this answer
add comment

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

share|improve this answer
add comment

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).

share|improve this answer
    
It's a pretty simple modification to add another pointer in order to traverse every other item. –  Alex Chamberlain Oct 17 '12 at 14:52
    
@AlexChamberlain It covers alternate traversals in any order, not just every other item. See the flow of arrows in figures 1 and 2 for a quick idea. –  kinkfisher Oct 17 '12 at 16:31
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

This pdf file: http://arxiv.org/pdf/cs.DS/0011047.pdf

titled: Dancing Links

by Donald E. Knuth, Stanford University.

Journal: Millenial Perspectives in Computer Science, 2000, 187--214

It specifically mentions doubly-linked lists and traversing them to seach and backtrack.

I also have the Knuth Fundamental Algorithms - second edition from 1978, which describes doubly linked list and traversals. Section 2.2.5 - Pages 278 - 293.

Hope this helps

share|improve this answer
    
The question has to do with a patent for lists that can be traversed in a more than one "dimension". Maybe the same elements are linked by create date and by last name alphabetically. –  George White Aug 4 '13 at 23:08
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.