December 14, 2017 · Computer Science Data Structures

Arrays as Kitchen Drawers

A useful metaphor for the array data structure is a set of kitchen drawers. Imagine that we have a set of drawers numbered from 0 to 9, which makes for a total of 10 drawers. I want to find my keys, and know that they live inside the 5th drawer. And I can get my keys, by opening the drawer that has a label of 4 on it. It's important to note that I didn't have to open the first drawer, then the second drawer, then the third drawer, then the fourth drawer, in order to get to the fifth drawer. I had all the drawers within my line of sight, so I simply opened the one I wanted. If you're thinking this sounds a lot different from the scavenger hunt analogy from last time, you're right!

Granted, I had to know that my keys were in the 5th drawer, in order to find my keys in one step. But without that crucial bit of knowledge, I'd have to open every single drawer until I find my keys. For instance, imagine now that I need to find a cheese grater. I'm not sure which drawer it's in, or if I even have one at all in my house! So I open every single drawer, and check if there's a cheese grater in there. Finally, I get to the last drawer which is sadly cheese grater-less. I can finally confirm that I don't own a cheese grater, and need to go to the store to get one.

kitchen drawers

Arrays work in much the same way. If you know the index position of the item you want, you can always get there in one step. But if you only know the value of the item you want, you're going to have to check every single item in the array until you find what you're looking for.

array

For instance, I can go to index position 3 of the above array in one step. But I can't go directly to "bottle opener" if I don't know that "bottle opener" lives in index position 4.

Inserting an item

What if I want to put a new item into my kitchen drawers? Imagine that the first 9 of my 10 drawers is full. My 10th drawer is empty, and free for use. In this case, I can just put the new item into the 10th drawer. Not too bad.

But what if I want to put the new item into the first drawer specifically? There's already stuff in there. So I need to move the stuff in the 1st drawer to the 2nd drawer, which means I need to move the stuff in the 2nd drawer to the 3rd drawer, which means I need to move the stuff in the 3rd drawer to the 4th drawer, etc. This goes on until I realize I need to move the stuff in the 9th drawer to 10th drawer. (We want to maintain the relative ordering of the items in the array). Finally, after doing all this shuffling around, there's now space in the 1st drawer, and I can put my new item there!

This is all to say that how much work it takes to insert a new item into an array, depends on where you want to insert it. Insertion at the end (if you have room for it) is one step. Easy-peasy. But insertion at the beginning involves shifting over every other item in order to make room for the new item.

array_inserting

In the array above, the first 4 slots are already filled with items, and the 5th slot is empty. And we want to insert "bread knife" into the 1st slot of our array. This involves several steps, since we need to make room for "bread knife":

  1. We shift "coffee filter" one slot to the right.
  2. We shift "spatula" one slot to the right.
  3. We shift "butter knife" one slot to the right.
  4. We shift "cheese grater" one slot to the right.
  5. Finally, we insert "bread knife" into the newly empty 1st slot.

Deleting an item

On the other hand, deleting from an array may involve shifting items to the left. This is because arrays are contiguous, which means that all items in an array have to be next to each other. There can't be any "gaps" between the items in an array.

array_deletion

In the example above, we have an array of 5 items. We want to delete "butter knife" in index position 1, so we do that. However, now we have a gap between "cheese grater" and "spatula". That won't do, so in order to close the gap we need to:

  1. Move "spatula" one slot to the left.
  2. Move "coffee filter" one slot to the left.
  3. And finally, move "bottle opener" one slot to the left.

That's it!

I hope the kichen drawer analogy helps you to better understand what goes on underneath the hood of arrays. Next time, we'll talk about the stack as a data structure.