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.