Linked Lists Have Now Been Patented

I'm just aghast, but it's true. On April 11, 2006, the US Patent Office granted a patent for linked lists. It's mind-boggling.

The only thing conceivably unique? It's triply-linked, thus allowing multiple traversal orders. I'm confused. How is this different from a directed graph?

3 Comments

What is the different from a generic directed graph? 1. Each edge is labelled. 2. Edges with the same label forms a Hamiltonian path.

With out reading the full patent text in depth, just a rapid scan, it looks to me that the same technique is used by the perl parser, though, in that case the primary structure is not a list but a tree.

The B::Concise module can show both views. For instance:

The "main" opcode tree view...

$ perl -MO=Concise,-basic -e 'print "hello" for (1..3)'
g  <@> leave[1 ref] vKP/REFC ->(end)
1     <0> enter ->2
2     <;> nextstate(main 1 -e:1) v:{ ->3
3     <;> nextstate(main 1 -e:1) v:{ ->4
f     <2> leaveloop vK/2 ->g
8        <{> enteriter(next->c last->f redo->9) lKS/8 ->d
-           <0> ex-pushmark s ->4
-           <1> ex-list lK ->7
4              <0> pushmark s ->5
5               const[IV 1] s ->6
6               const[IV 3] s ->7
7           <#> gv[*_] s ->8
-        <1> null vK/1 ->f
e           <|> and(other->9) vK/1 ->f
d              <0> iter s ->e
-              <@> lineseq vK ->-
b                 <@> print vK ->c
9                    <0> pushmark s ->a
a                     const[PV "hello"] s ->b
c                 <0> unstack v ->d

And the "auxiliary pointer" view (representing the execution order of the opcodes)...

$ perl -MO=Concise,-exec -e 'print "hello" for (1..3)'
1  <0> enter 
2  <;> nextstate(main 1 -e:1) v:{
3  <;> nextstate(main 1 -e:1) v:{
4  <0> pushmark s
5   const[IV 1] s
6   const[IV 3] s
7  <#> gv[*_] s
8  <{> enteriter(next->c last->f redo->9) lKS/8
d  <0> iter s
e  <|> and(other->9) vK/1
9      <0> pushmark s
a       const[PV "hello"] s
b      <@> print vK
c      <0> unstack v
           goto d
f  <2> leaveloop vK/2
g  <@> leave[1 ref] vKP/REFC

Ovid, you should submit this story to slashdot, they love these kind of stories over there :)

Leave a comment

About Ovid

user-pic Have Perl; Will Travel. Freelance Perl/Testing/Agile consultant. Photo by http://www.circle23.com/. Warning: that site is not safe for work. The photographer is a good friend of mine, though, and it's appropriate to credit his work.