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.

Amoebas Having Boring Family Trees

Trees are computational data structures used for storing and searching data. Data is stored at tree nodes. Each node can also contain a link to zero or more "children" nodes. These links can be used in a search algorithm to traverse the tree. Correspondingly, each node may have up to one "parent" node. Only one node in the tree, the "root" node, does not have a parent node.

Abby's class project was due tomorrow morning, and she was still not sure what she was doing wrong. As she looked at her paper, panic began to set in.

The example family tree that her teacher had given her showed a clear network of nodes. There were levels for grandparents, parents, and siblings. But, Abby's tree did not look anything like that. Sometimes, being the only amoeba in her second grade class made life complicated.

Being an amoeba, Abby's family worked differently from those of her classmates. Instead of having two biological parents, she had exactly one. She was born through mitosis, when her parent had literally split in half to form her and her sister Venn. So, Abby's tree started at a single grandparent and branched out as it went down. Each parent could have exactly zero or two children, and each child had exactly one parent node. It was a perfect binary tree. Unfortunately, it looked nothing like what the teacher would be expecting.

On the plus side, Abby found it remarkably easy to trace her lineage back for centuries. Each amoeba on her family tree could have only one parent. Thus, she could follow her family all the way back to her great, great, great grandfather, "Sir Edward the Adventurous", who had been the first amoeba to colonize this particular petri dish. And starting at her great great grandfather, she could search down through the layers and find out how she was related to any other amoeba in the whole dish. But, none of that helped on this class project.

Abby carefully finished labeling her tree. She had one grandfather who had two children: her father and her aunt. Her father then had two children: her and Venn. And her aunt also had two children. All three generations formed only seven nodes on the tree.

Discouraged, Abby gave a bubbly sigh of despair as only amoebas can. She only hoped that her teacher would understand.

Epilogue: Abby actually received double credit for her assignment after she launched into a impromptu 30 minute monologue on the wonderful computational properties of her family tree. First, she described how she could determine the exact relationship to anyone in her family in O(log N) time regardless of the number of generations included. Then, seizing the moment of inspiration, she noted that her family tree was in fact a heap sorted by age. Each amoeba in the tree could have up to two children and the ages of both children were strictly less than that of their parent. Her descriptions were so inspiring that the entire class gave her a standing ovation.

.

Binary Search Trees and Speck the Spider

Binary search trees (BST) organize data to allow efficient searches by value. Data is stored in tree nodes. Each tree node also maintains pointers at most two children nodes: a left child and right child. The tree maintains the property that at each node values in the left subtree are less than the value of the current node. In contrast, values in the right subtree are greater than (or equal to) the values in the current node. This structure allows an efficient search by walking down the tree and branching in the direction of the value for which you are looking. A balanced binary search tree allows O(log N) search.

Speck was a spider. As such, he lived a typical spider lifestyle. He built webs, ate flies, and enjoyed discussing the weather with his neighbors. In fact, for those who had never been to visit his web, he seemed like a perfectly normal spider.

However, the truth was, Speck was not a typical spider. He was obsessive about his food choices and demanded a level of variety that was unheard of for other arachnids. Speck insisted on keeping a supply of at least 25 different types of bugs in his web.

Speck also insisted on absolute organization in his food supply. What good was 25 varieties of bugs, if he could not quickly find the one that he wanted? While most spiders kept their bugs distributed randomly throughout their webs, that prospect seemed absurd to Speck. He loathed such disorganization. Instead, like any rational chef, Speck organized his food choices in alphabetical order.

The result of these preferences was a new type of web design that Speck developed through long days of trial and error. He called it a binary search web. The web consisted of nodes, clusters of webbing that stored his bugs, and strings of web between the nodes. The whole thing was organized vertically. At the top was a single "root" node attached to an old storm gutter. Each node in the web could have at most two "children" nodes below them. These nodes were attached securely to their parent node above using a strong strand of webbing. As a result, the web branched out wider as it progressed downwards, taking on a vaguely triangular shape.

In order to maintain his organizational structure, Speck insisted that the bugs stored at each node obeyed a particular alphabetical ordering. Specifically, the bugs in all of the nodes down the left-hand path from a given node had to be BEFORE the current node's bug in alphabetical order. Similarly, all of the bugs in all of the nodes down the right-hand path from a given node had to be AFTER the current node's bug in alphabetical order. This way, Speck could quickly find any bug that he was looking for by simply descending the web.

For example, one morning Speck decided that he wanted a fly for breakfast. He started at the top of his web, where he slept, and examined the bug there. It was a lady bug. Since flies come before lady bugs, Speck sleepily walked down the thread on the left-hand side of the node. On his way he paused for a drink of dew that had collected during the night. At the next node, Speck found a beetle. Since flies come after beetles, Speck now chose the right-hand path. There he found the three day old fly. Speck happily ate his breakfast and then decided to take a mid-morning nap.

The advantage of the branching structure of the web is that, as long as he kept the structure well balanced, Speck could find any bug that he was looking for in O(log N) time. What this meant was that Speck could double his inventory of bugs while only adding one additional step to his search! Given that Speck only did his searches when he was very hungry, this efficiency was important. He had heard his friends claim that they just ate whatever bug was closest. Imagine that!

The web also leant itself to the addition and removal of bugs. Adding a new bug simply consisted of walking the bug down the web (while making the correct alphabetical branches) until he hit a dead end. Then he would add a new child node, with the new bug, to the correct side of the current node. Adding a new node just meant spinning some webs, and Speck enjoyed that part of being a spider a lot. As he saw it, making webs was definitely the best part of being a spider.

Sadly, despite the obvious advantages of the binary web structure, Speck never managed to encourage wide adoption. Instead, his friends stuck with the classic circular patterns, citing their ascetic value.

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

For more information on tree data structures, see why amoebas have boring family trees.