Choose Your Own Adventure Stories Are Not Linked Lists

A linked list is a simple data structure. It is composed of a series of nodes, each of which contains data and a pointer to the next node in the list. You can traverse the list (and thus read the data inside it), by following each node's pointer to the next node in the list.

When he was a young boy, Goork had written a series of Choose Your Own Adventure Stories. To this day, they still hold the record as the absolute worst choose your own adventure stories ever written. They were awful in every possible way. None of Goork's stories used punctuation, and a full seventy percent of the words were misspelled. But even worse than that, Goork simply did not understand the concept of a choose your own adventure novel.

Instead of providing the reader choices to move through the story, each novel had a single narrative thread. There were no branches -- no choices. The only thing that the story had in common with a real choose your own adventure novel was the little note at the bottom of the page telling you which page was next. On page 55 it stated, "Go to page 12" for no reason other than having the reader flip through the book. Goork loved writing that part of the page the most.

The entire novel was like a linked list. Each page contained both data, in the form of three incomprehensible paragraphs, and a link to the next "node" in the story.

Admittedly, the structure of the novel made it easy for Goork to add to any part of his story. And, since he never thought out his stories ahead of time, this was an important consideration. He could always add new material to the end and simply update the correct "go to" sections. For example, if Goork thought of the perfect dialogue to add after the romance scene on page 100, he would create a new page (500) at the end of the story. Then he would change the note on the page 100 to read "Go to Page 500", and thus it would point to this new material. Similarly, he would add a note on page 500 to point back to the correct location in the story. He could even copy that directly from where page 100 had been pointing before. He only needed to change two lines of "go to" text, and everything was in order.

Of course, finding the correct preceding page for the insertion was not easy. Goork always had to start at the beginning of the story. He would trace back through the story until he found the correct insertion point. But, that did not bother Goork. He enjoyed rereading his stories.

Goork's best friend constantly pointed out the problems with using linked lists for these types of stories. "Goork!" Simon pleaded. "The whole idea behind choose your own adventure novels is to give the reader choices. They should be structured like a tree, not a linked list. Each story node should branch off toward different plot lines. You should have statements like 'If you want to turn right, go to page 83. If you want to go left, turn to page 99." But, Goork refused to listen.

While Goork never mastered the art of choose your own adventure novels, he certainly had a lot of fun writing them. He finished his one hundredth novel shortly before graduating high school. The epic adventure of "Linked Lists verses Binary Trees" provided a gut wrenching tale of the dark history of different computational data structures. It never became a best seller.

-------------------

For more information on linked lists, check out the following stories: Linked Lists, Kindergarten and Ocean Voyages or Arrays, Linked Lists, and Zed's Coffee Shop.

For more information on trees, check out the following stories: Amoeba's Have Boring Family Trees or Binary Search Trees and Speck the Spider.

Choices. It is just like a choose your own adventure story should be.

Arrays, Linked Lists, and Zed's Coffee Shop

Arrays and linked lists are simple data structures that store multiple values in memory. Where these data structures differ is in how they store and allow access to the data. Arrays are like a set of bins with a fixed number of slots. Their structure makes it easy to read from or write to an arbitrary element in the array. In contrast, linked lists are easily extensible chains of data. However, you must scan to the correct location in the chain to read or modify a piece of data in that node.

One year after Zed opened his coffee shop, business was great. Zed had a devoted set of regulars who bought coffee every morning on their way to the castle. They were mostly bureaucrats, specializing in such jobs as counting the kingdom's cattle or copying maps. They loved their coffee.

Then, one day, a competitor opened shop across the street. Zed started losing business to MegaCup’s low prices and flashy signs. Zed knew he had to expand.

Looking over the books, Zed noticed that he sold a lot of coffee in the morning but almost none at night. None of his customers wanted to be jittery as they headed home and went to sleep. Zed needed a new product -- something he could sell at night.

His supplier told him about a new type of coffee coming from the southern region of the kingdom: “Low Jitter Coffee”. Immediately, Zed knew this coffee would solve his evening sales slump. He ordered eight cases.

Zed needed a way to market his new coffee. The sign outside his store read “Coffee” and did not have room for anything else. After a week of intense thought, Zed ordered a new ArrayDesignBoard menu board for outside his shop. The board had four slots where you could slide in menu items to display. He slid in “Coffee” and “Low Jitter Coffee” tags.

The new coffee was a huge success. Zed's business doubled in a week. He added four baristas to the evening shift.

However, Zed’s competition soon caught on. A week later, Zed noticed a new shingle on MegaCup’s sign: “Low Jitter Coffee”. The war was on.

Then his supplier told him about another type of coffee. It was called “Double Bold Coffee”, and it was significantly stronger than the normal brew. A single cup could keep you awake all night. Zed ordered eight cases and a the new menu tag for the ArrayDesignBoard menu.

The coffee was a huge success. His morning crowd loved it. He also started attracting new customers from the castle’s night guards. They needed something strong to keep them awake during their watch.

Alas, it was not long before MegaCup added a new shingle to the end their sign.

The next time his supplier visited, Zed grilled him on the other types of coffee available. After obsessing over the supply lists, Zed decided to try a novel approach. He order one case each of ten different flavors. He put these flavors into a rotation, constantly offering new variety. This approach worked particularly well with Zed’s sign. Every time he switched a flavor, he would remove one tag and slide a new one in. Sometimes he changed the menu a few times in one day, such as replacing “Double Bold” with “Low Jitter” after noon.

MegaCup took a different approach. The manager quickly found that, while adding new shingles to the end of the list was easy, removing them was frustrating. In order to remove a shingle, he had to: unlink it from both the shingles above and below, then reattach the shingle below to the one above. It was a time consuming process. He decided to take advantage of the ability to easily expand offerings. He offered six different coffees on a semi-permanent basis. On rare occasions, he would grudgingly spend fifteen minutes to unlink a shingle on his sign and add a new one.

The two coffee shops operated in that mode for years. Zed’s coffee shop rotated through different options, and MegaCup offered a more constant, but larger, selection.

Both businesses thrived as the market for coffee grew. Eventually, Zed's Coffee House became one of the largest businesses in the kingdom with over a hundred different locations. Zed continued to expand aggressively until the great sugar famine hit. With business dropping due to the lack of sugar, Zed decided to leave the world of coffee and speculate in coconut sales.

----------------

Interested in learning more about linked lists? See why choose your own adventure stories should never be linked lists. Or, read about Ann's ocean voyage and her insights into linked lists.

Linked Lists, Kindergarten, and Ocean Voyages

Linked lists are simple data structures that store a list of items. Each node in the list consists of a few pieces of data: the information being stored at that node (or a pointer to it), a pointer to the next node in the list, and (optionally) a pointer to the previous node in the list. An algorithm can traverse the items in a list by simply following the pointer out of each node to the next. However, random access of nodes is not possible, unless additional pointers to the nodes are stored in an outside data structure. Linked lists support easy insertion and deletion of elements, by simply changing where appropriate nodes' pointers are pointing.

Ann had been excited about her ocean voyage to New Atlantis for approximately twenty minutes. She had stood at the ships railing, watching the shoreline move away and feeling the sea breeze on her face. The ship's sails had made a pleasant flapping noise as they caught the wind. It had been exhilarating. Then, much to her dismay, the ship had started a nauseating series of sways and lurches. That had been three days ago and the movement had not ceased for a moment.

Bundled up against the (now remarkably frigid) breeze, Ann sat on the ship's deck and watched the three ships following silently after them. The first was only four hundred meters behind, the second four hundred meters after that, and the third another four hundred. In addition, Ann knew there was another ship leading the way four hundred meters in front of them. Together the five ships made a convoy that stretched out in a mile-long line across the ocean.

Ann had found the arrangement of the convoy fascinating. When she had interrogated the captain to the convoy's linear arrangement, he had happily explained the line's functionality in exquisite detail. The convoy consisted of a chain of ships, navigating along the same route. The head ship led the convoy. Supposedly, this arrangement facilitated both navigation and safety.

Communication among the ships was also fascinating. Each ship had two crew members called pointers, whose job it was to communicate with the other ships. When someone on ship #2 wanted to pass a message to ship #5, the Pointer at the back of ship #2 would signal the message out to ship #3. Similarly, ship #3 would relay it to ship #4 and ship #4 to ship #5. It was a completely linear system, with the message passing through each ship on its way.

The whole arrangement reminded Ann of her days as a young kindergartener when the class would be forced to hold hands as they went on field trips. Each kid would maintain contact with exactly two classmates, assuring the full string of students stayed completely connected. The teachers would walk down the line carefully comparing the students to a list of names and ensuring that everyone was present.

But in Ann's mind, the best thing about the kindergarten lines were their ability to be dynamic. When one student had to visit the restroom, they would leave the line by simply making sure that the students on either side of them held hands with each other. This operation was usually marked with a careful shuffling of grips, but always resulted in the class maintaining its line (minus the kid running to the restroom). And, when the student returned, they would: pick a point to insert themselves in the line, break the line at that point, and make sure they reformed the connections by holding hands of the correct two people. This line concept had made such an impression, that Ann had spent years marveling at the power of pointers and dynamic data structures.

"Captain, do your convoys ever get additions or removals?" Ann asked one morning. "Or is the convoy fixed once it departs?"

"Of course the convoy changes." the captain answered. "In fact, later today we have three ships joining us from North Patagonia." He gestured vaguely toward the direction of North Patagonia as if to illustrate his point.

"Will they join the end of the line?" asked Ann, eager to understand the convoy's dynamics. It would make sense to simply append the new ships to the end of the line. That way only the first ship of the new arrivals and the last ship of the current convoy would need to connect. That is how they had merged lines in kindergarten.

"No, no." insisted the captain. "They will join between ships #4 and #5. Ship #5 is a special warship with extra rear facing cannons. It always has to be in the back. One by one the ships will insert themselves into the chain, coordinating through their pointers. Good sailors, those pointers."

"But how?" asked Ann. For the first time in days she had forgotten her sea sickness. She was distracted by the beauty of dynamic structures.

"All very simply, I assure you. The new ship, let's call it D, will pull up next to our head ship (A) and then slow down. It will slowly work its way down the convoy until it finds a location to be inserted: let's say after ship A. Then the D's pointer coordinates with B's pointer to say 'You are now behind us.' and ship B moves back to let D in. At the same time D's other pointer coordinates with ship A's pointer to say 'We are now behind you.' It is all very organized."

(Ship D joins convoy between ships A and B)

Ann was thrilled. When the ships arrived that afternoon, she watched their coordinated dance with glee. The simplicity of it amazed her. Inserting new ship into the line was only a matter of four pointers, two in each direction. In her excitement over the dynamic operations of the convoy, Ann even managed to forget about her seasickness.

---------------------

Interested in learning more about linked lists? See why choose your own adventure stories should never be linked lists or how Zed used linked lists while expanding his coffee shop.