3 ms·
"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, line
by droz 15y 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 15y 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 15y 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 15y agoA reverse directory (sorted by phone number) probably defeats frequency knowledge.
- jws 15y 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 15y 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 15y agoYes, I was going to say chain. Each chain link points to (or touches) the next.