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.