Monday, March 19, 2007

Good job, US Patent and Trademark office...

...you've just given someone a patent for a Doubly-linked list.

From Patent 7,028,023:
"SUMMARY OF THE INVENTION

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 sequential list may be created in one sequence, but used in a second sequence without having to resort the list.

The present invention may therefore comprise a computerized list that may be traversed in at least two sequences comprising: a first sequence of items that comprise the list; and a primary pointer and an auxiliary pointer for each of the items of the list, the primary pointer being adapted to direct a computer program to a first following item and defining a first sequence to traverse the list, the auxiliary pointer being adapted to direct the computer program to a second following item and defining a second sequence to traverse the list.

The present invention may further comprise a method of traversing a list having at least two sequential pointers comprising: providing the list to be traversed, the list comprising a plurality of items; for each of the items of the list, providing at least a primary pointer and a secondary pointer, the primary pointer being adapted to point to a first sequential item and defining a first sequence to traverse the list, the secondary pointer being adapted to point to a second sequential item and defining a second sequence to traverse the list; determining to use the second sequence to traverse the list; determining a starting item for traversing the list, the item being the current item; performing an operation on the current item; traversing the list to a new item indicated by the secondary pointer, the new item replacing the current item as the current item; and repeating the previous two steps at least one time to traverse the list.

The present invention may further comprise a computer system capable of traversing a list having at least two sequential pointers comprising: the list to be traversed, the list comprising a plurality of items; at least a primary pointer and a secondary pointer for each of the items of the list, the primary pointer being adapted to point to a first sequential item and defining a first sequence to traverse the list, the secondary pointer being adapted to point to a second sequential item and defining a second sequence to traverse the list; the ability to determine to use the second sequence to traverse the list; the ability to determine a starting item for traversing the list, the item being the current item; the ability to perform an operation on the current item; the ability to traverse the list to a new item indicated by the secondary pointer, the new item replacing the current item as the current item; and the ability to repeat the previous two steps at least one time to traverse the list.

The advantages of the present invention are that a list may be traversed in different sequences without resorting or sequentially traversing the list."

From Wikipedia:
"In computer science, a linked list is one of the fundamental data structures used in computer programming. It consists of a sequence of nodes, each containing arbitrary data fields and one or two references ("links") pointing to the next and/or previous nodes. A linked list is a self-referential datatype because it contains a pointer or link to another data of the same type. Linked lists permit insertion and removal of nodes at any point in the list in constant time, but do not allow random access. Several different types of linked list exist: singly-linked lists, doubly-linked lists, and circularly-linked lists."

Various emphases are mine.

2 comments:

Anonymous said...

As stupid as it sounds to give someone a patent for the most basic useful structure of programming, it sounds like they may really be getting the patent for linking a list alphabetically and by order of entry or something like that, rather than forward and backward. I still don't think it's a new idea, but I could be wrong.

~Christine

Beltonius said...

I concur that they didn't specifically patent the linked list, but they've patented the generalized n-linked list which includes the prototypical single and doubly-linked lists.

While their idea has merit, I don't see it as being patent-worthy; I mean, what if someone tried to patent a number 8 sentence or whatever. You can probably write a novel without it (I don't really remember what it is specifically, but whatever) but you would never let someone copyright or patent it.