If you want to explain this to a nontechnical person…
Let's say Aunt Marge clips coupons. She clips a lot of coupons, so she keeps them in one of those index files with a slot for each letter of the alphabet, by product name. When she goes looking for a coupon, say for coca cola, she goes to the "C" slot and flips through the slot looking for a coca-cola coupon. If while flipping through she pitches out expired coupons then she has infringed this patent. (if she does it "with a computer")
Edit: This is just claim #1, there are more variations claimed.
For the average layperson, you are correct and I'll probably use this analogy myself in conversation. Legally, however, your analogy doesn't hold water. Yes, it's an analogy and many times they aren't 100% analogous, but I feel it's worth pointing out the legalistic differences.
And here's the reason: Aunt Marge isn't using a linked list. That is, each coupon doesn't point to the next coupon in the list. It's simply a collection (or array) of coupons.
Now, let's bring this back to a point that's somewhat more relevant. If you did implement something more analogous to Aunt Marge's coupon collection (say an array), and trimmed out items as the code noticed they were expired, would you infringe this patent? Maybe not. I haven't tried reading the details of the patent, but if the article is correct and if, as in every other case, every detail of the patent matters, then I'd wager your array-with-expiring-items would not infringe.
And that is what's wrong with software patents. Maybe we've been expiring items from collections, dictionaries and arrays for a long time. But suddenly, apply it to a linked list and you've infringed the patent. Nonsense.
A linked list of course has no direct analogy in the physical world, but I think the analogy has a workable definition of "next(couponX)" which is "put your finger on the back of couponX, move your finger away from yourself, if you touch the face of another coupon, that is the next coupon".
The slot is not an array, it is not directly accessible by index number or key. It is close to a doubly linked list with a head and tail pointer, but it has more operations than a linked list though. You can flip through by "a bunch" and easily start at a randomish middle point which doesn't map back to linked lists, but also isn't important for this example.
"A linked list of course has no direct analogy in the physical world"
First few that come to mind: conga line, necklace, bike chain and DNA. Tangentially, lines of people forming a queue or a push down stack of dishes or the number you pick at the deli counter for your turn forming a circular buffer. All of these are examples of physical world linked lists.
I like these. You can embody the "link" nature, but the physical analogies also gain operations that make them not match linked list[1], such as:
• The examples all seem to include back links as well.
• Most of them you can access an interior element in constant time.
• Most of them you can get a size estimate without traversing.
• The dishes are more stack like. Traversal is destructive, but it doesn't add operations. (I think)
• The deli numbers give you a constant time "distance between" operator (unless the deli has lost a lot of the tags), and require a global method dispatch to find "next". 37? 37?… 38?
[1] Somewhere in the '80s, Dr. Roman[2] was explaining binary search to a class of 'us' and started to use a phone book analogy, until he realized that people have more information than just alphabetic letter position to work with, they have an idea about frequency in names as well. That's stuck with me as a caution of the difficulty of analogy.
[2] Oh look, he is department chair now. Well done! (Warning to students: if you are having trouble in CSE425S (formerly CS 455) with the programming-language-of-the-week being prolog, and you figure out how to build yourself variables, he will see through you and give you a bad grade, my poor little grid bugs.)
Then you get uniform distribution problems. If I know the first few digits are 980 I can make a leap well to the back of the book. It really does become an interesting problem.
You can force it by not letting the person see the key, only the results of the comparison, but that is a little silly.
Maybe some of the mismatch comes from the human heuristic being so much faster than the physical turnpage-readname-compare operation. In a computer the compares are so fast that there isn't really a point to building a heuristic to optimize away the first few.
If the comparison finding were slow on a computer you would not use binary search, so in a sense you are forcing the human to use the wrong algorithm.
What you're describing is an interpolated binary search (where you don't divide in two, you pick a point based on a guesstimate of where the key will lie).
It turns out that interpolated binary searches are useful in computers, in cases where the structure being searched has a significant overhead for each read - for example, seeking in variable-bitrate-encoded video streams is such an application.
Its an old one but filing cabinet document index sheets would be a linked list. Those were lists of the contents in a cabinet/drawer, some of which were lists not in the order of the contents, but in an alternate order for finding documents.
I'd think of it more like, if you kept all the coupons in numbered cubbyholes, and each coupon had a post it note with the location of the cubbyhole where the next ordered coupon was.
Project A contains a generic collection. Project B contains an abstraction of objects with expiry times. Project C instantiates A's collection for B's objects.
Now assuming A implements the collection using linked lists and C uses A and B as black box, linked libraries, does anyone infringe on the patent?
No, because the key point of this patent appears to be removing expired objects as a side-effect of searching the linked list for an unrelated object.
So unless Project A's generic collection implements an optional callback that is called on every object seen while searching the collection, project C uses that callback to delete expired objects, you'd seem to be in the clear.
> If you want to explain this to a nontechnical person…
It would be interesting to get the materials from the trial and see how both sides explained the patent to the judge and the jury. During pretrial both sides will have made a technology presentation to the judge to explain their take on the background of the patent and what it does, and then during the trial both sides will try to explain to the jury what the patent means.
Some of these presentations can be very good content-wise and very well produced and presented.
Let's say Aunt Marge clips coupons. She clips a lot of coupons, so she keeps them in one of those index files with a slot for each letter of the alphabet, by product name. When she goes looking for a coupon, say for coca cola, she goes to the "C" slot and flips through the slot looking for a coca-cola coupon. If while flipping through she pitches out expired coupons then she has infringed this patent. (if she does it "with a computer")
Edit: This is just claim #1, there are more variations claimed.