Lists Introduction Introduction

Ah, summer. A time of staying up late to watch your favorite infomercials, sleeping in to dream about that perfect set of kiwi tweezers, and eating breakfast in your pajamas while you wait for that pint-sized package to arrive in the mail. There's just one little problem: when you open the cupboard to grab some Shmoopy Os, you find an empty shelf.

All those perfect plans of not leaving the house for three months foiled by Past You. You might have to leave the house today, but that doesn't mean you have to wear actual pants. So there's that.

Once you reach the store, you notice a sign taped to the sliding door that says, "In honor of Alan Turing's 104th birthday, store checkout will run in stacks instead of queues for today only." If you weren't such an anglophile (read: Whovian), you might not know they mean line when they say queues, but you have no idea why they'd stack customers on top of each other.

Maybe it's some type of performance art?

You shrug and head to the aisle with Shmoopy Os, loading as many of them as possible into your basket. Can't let the same mistake force you out of the house twice in one summer.

As you head to the checkout, you see three people are already in line at Register 4. Normal enough, but then when another person arrives the checker waves them to the front of the line. The customers behind them give bone-chilling glares, but they only have a carton of milk. Maybe the checker wanted to save them from the line. Once they're gone, the next person steps up.

Now at Register 2 another person shows up, this time with a cart heaping filled with months' worth of groceries. Despite the clearly much longer time it'll take them to check out, they're also waved in front of the person with a bag of Kit-Kats. That can't be fair.

More glares. Things are getting pretty tense in that checkout line.

Just as the grocery hoarder's about to be rung up, another person, this time with two shopping carts filled with cat food (now that's dedication to staying inside all summer), heads to Lane 2 before the person with the entire store's inventory can be rung up. The person with a thousand cats (not that you're judging or anything, but…), actually gets waved ahead and checks out first.

Are you in The Twilight Zone? Eh, not really. All the queues were stacks. In your pride of remembering some random time when Rose Tyler mentioned queuing, you didn't think about what it would mean to become a stack.

It's kind-of a big deal—both in totally invented scenarios like this one and in computer science.

Even if choosing to implement stacks instead of queues is a terrible strategy for building customer loyalty, stacks—along with queues and other types of lists—are great in computer science. These are the most common data structures you'll see to help you organize your programs, but you need to know the places where one makes sense more than the other. By picking the right kind of list, you can be sure your computer runs smoothly.

And you won't even need Time Lord intervention to do it.

 

Why Should I Care?

Like ants, arrays, linked lists, stacks, and queues are all both simple and incredibly powerful. Also: they can ruin even the best-planned picnics (probably).

They're fundamental data structures of computer science, meaning that you need to know them before your programs start getting anywhere near complex.

At the core of all these different types of implementations is the concept of a list: the place where you can store similar information all together. All that changes is the way you can access and change that information. Picking the right type can be the difference between an optimal program and one that takes weeks to run.

Some data structures are better for specific operations. Inserting at the bottom of a stack or top of a queue can be tough, but doing either in a linked list takes no time at all. Arrays, meanwhile, are best to be left alone once they're created: both insertion and deletion can be compared to having a root canal without Novocain. The more you know about data structures (and lists) in general, the more informed decisions you can make about which type to use in a specific situation.

But no pressure.