4 ms·
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 fin
by jws 16y ago
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.
- droz 16y ago"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.
- jws 16y agoI 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.)
- cpeterso 16y ago> people have more information than just alphabetic letter position to work with, they have an idea about frequency in names as well. Perhaps a better analogy would be binary searching in a phone book or dictionary for a foreign language.
- arghnoname 16y agoA reverse directory (sorted by phone number) probably defeats frequency knowledge.
- jws 16y agoThen 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.
- caf 16y agoWhat 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.
- 16s 16y agoYes, I was going to say chain. Each chain link points to (or touches) the next.
- phaylon 16y agoHow about "Document A (succeeded by Doc B)", "Doc B (succeeded by Doc C)", "Doc C (current)"?
- LarryA 16y agoIts 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.
- runningdogx 16y agoScavenger hunts are set up as linked lists.
- techtalsky 16y agoI'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.