Tuesday, June 7, 2011

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.

No comments:

Post a Comment

Note: Only a member of this blog may post a comment.