Mailinglist Archive: opensuse (3354 mails)

< Previous Next >
RE: [opensuse] Double Linked List patented in 2006
  • From: (Ted Harding) <efh@xxxxxxxxxxxxxxxx>
  • Date: Mon, 19 Mar 2007 20:37:58 -0000 (GMT)
  • Message-id: <XFMail.070319203758.efh@xxxxxxxxxxxxxxxx>
On 19-Mar-07 17:50:12, M Harris wrote:
> Double Linked List Patented in 2006
> see Slashdot today,
> Well, well. If this doesn't prove that the United States
> Patent Office (not to mention the clucks at Cochran Freund
> & Young LLP) are absolutely and completely incompetent with
> regard to issuing software patents.

Seeking some clarification here.

What is commonly known as a "double linked list" or more
correctly a "doubly linked list" consists of a set of nodes
where at each node a data element is stored, along with
a pointer to the next element in the list and also a pointer
to the preceding element in the list. This allows the list
to be traversed in both directions.

If you read the patent description at the above URL, you find
that what it describes is a generalisation of this, namely a
set of nodes at which (as before) a data element is stored,
along with two or more linkage nodes in each direction, thus
allowing two or more different traversal sequences. For example:

   A[->B][->D] B[->C][->A] C[->D][->B] D[->A][->C]

is a standard circular double linked list over data elements
A, B, C, D:

   A <-> B <-> C <-> D <-> A

What they are talking about is on the lines of

   A[->B][->D] B[->C][->A] C[->D][->B] D[->A][->C]
    [->C][->D]  [->D][->C]  [->B][->A]  [->A][->B]

coerresponding to the "double linked list"

   A <-> B <-> C <-> D <-> A
   A <-> C <-> B <-> D <-> A

i.e. it is effectively two linked lists, but over the same
data, and is implemented by using only one copy of the data
elements but providing each element with two sets of pointers.

Now, while the standard "doubl{e|y} linked list described
at [1] above has been around since the year dot (or shortly
thereafter), and is found everywhere, the second kind described
at [2] above (though it has undoubtedly been implemented many
times) could conceivably be considered sufficiently novel to
provoke a patent application!

So my question, for clarification, is: Can anyone supply any
reference of sufficiently long standing to demonstrate that
the second kind of "double linked list" at [2] above is well
established prior art?

For example, does it occur in standard textboooks on computer
programming and data structures? Is there long-standing open
source software in which it may be found?


E-Mail: (Ted Harding) <efh@xxxxxxxxxxxxxxxx>
Fax-to-email: +44 (0)870 094 0861
Date: 19-Mar-07                                       Time: 20:37:53
------------------------------ XFMail ------------------------------
To unsubscribe, e-mail: opensuse+unsubscribe@xxxxxxxxxxxx
For additional commands, e-mail: opensuse+help@xxxxxxxxxxxx

< Previous Next >