News for hackers. Stuff that matters.
Re:Linked List Patent by ramchip on Wednesday March 03, 2010 @04:50PM (#1165291)
It's not a skip-list. It's a single-linked list, except that it may contain more than one "next" pointer per item. This way you could traverse it by either one of the next pointers, so you could keep the list ordered by 2 predicates at the same time.

Doesn't sound very useful in practice to me though. The interface would be complicated, error-prone, slow in many use cases, and this functionality can be much more simply be achieved by keeping two lists of pointers/references. It's also more or less obvious, so I'd be surprised if no one had done that before.

Re:Linked List Patent by pmjordan on Wednesday March 03, 2010 @04:54PM (#1165309)
Actually, it's an old idea and very useful for exactly that: different orderings. It's used extensively in the Linux kernel, for example, where structs contain multiple list_head members.
Re:Linked List Patent by ramchip on Wednesday March 03, 2010 @05:07PM (#1165344)
Interesting! I found a good explanation at http://locklessinc.com/articles/flexible_lists_in_cpp/

I do wonder how they could have missed the obviousness of it. Or maybe it's just the shotgun approach to patent trolling.

Re:Linked List Patent by showerst on Wednesday March 03, 2010 @05:05PM (#1165341)
Whoops, you're right.

Doesn't really change the fact that this is in no way novel, and likely has published prior art going back to at least the 70s.

I just don't see how anyone with any significant knowledge of computer science could think this was a new idea.

Re:Linked List Patent by pmjordan on Wednesday March 03, 2010 @04:53PM (#1165300)
It looks like a doubly linked list actually is covered by that - a doubly linked list just happens to use opposite orderings on the two references. I'm going to go out on a limb and claim that we had doubly linked lists before 2006... or 2004 (is that the filing date?).

Other prior art: about a gazillion structs with multiple list_head members in the Linux kernel.

I'm guessing they don't have actual programmers review software patents?

Re:Linked List Patent by CoryMathews on Wednesday March 03, 2010 @04:23PM (#1165210)
Seems like I have been saying this a lot lately but regardless I'm going to say it once again.

It's amazing what you can patent.

Re:Linked List Patent by fizx on Wednesday March 03, 2010 @04:53PM (#1165302)
This feels like Reddit to me. It's a quick laugh, and lets us feel smug in our shared values. Not informative, insightful, or hacker news. Flagged.
Re:Linked List Patent by showerst on Wednesday March 03, 2010 @05:10PM (#1165350)
I thought that it might get a decent software patents discussion going again, or that maybe there was something that I'd missed about this particularly implementation that someone could provide some insight on.

I know it's nothing particularly new for HN if you've been around a while, but new people join all the time, and recently at least one IP lawyer has seems to have joined, so I thought I'd submit it and see if there was any interest.

No cheap karma intended, I don't care about whuffie.

Re:Linked List Patent by srogers on Wednesday March 03, 2010 @06:04PM (#1165503)
I like to think this was a joint effort between the patent office and "inventor" to undermine the legitimacy of software patents.
Re:Linked List Patent by OmniLarry on Wednesday March 03, 2010 @04:22PM (#1165206)
I don't think this is quite a skiplist, but it is amusing that someone's trying..
Re:Linked List Patent by kzhcytwsl on Wednesday March 03, 2010 @06:38PM (#1165594)
A skiplist is just a specific case of this, though - as is a doubly-linked list...
Re:Linked List Patent by dasil003 on Wednesday March 03, 2010 @04:16PM (#1165187)
Looks like someone accidentally added a digit to the date...