Simple Structures- AKA Lines
Array- A Single File Line
Let’s start simple. Imagine you had a bunch of people standing in a line and each person had a chalk number in front of them. There is one other important point, and that is they are all standing inside giant cardboard boxes. This will become important later, so remember it. The first person would have a number 0 (the 0th element), the next would be a 1, etc.
That is how an array works. Usually declared inside brackets ->[]. Now, imagine you had to find the 12th person (#11), how long would that take you? Well, let’s not say you, because it would take you a whole day. But let’s say an average person. No time at all. They walk up to the number 11, and you have it! Simple as that. How about removing a person from the line? Well, you can’t have #11 be empty, you silly goose. So you have to have #12 fill that person’s spot. And #13 fill #12, and so on, for the whole line. That would take a while.
Now what about adding a person. Let’s again assume spot #11. You need to move the person from spot #11 to #12, since you are evicting them, you heartless criminal. The person in spot #12 up one as well, and so on. Think of all the people you have displaced. Are you happy now?
And lastly, what if we were to look for a person in line? Well, if you were smart, you would have organized the line. You weren’t though, and no one is surprised. So now you have to go through the entire line of people until you find them. I can hear you now: “But…but. I can just look through the line.”
Remember the thing about cardboard boxes? In the first paragraph? I told you it was important. And you didn’t listen. You have to go up to each person, and open the box until you find Jimmy Borgensen.
So in Big O notation, what is the run time of searching, inserting, and deleting from an array?
Access (Finding the person at spot #11)- O(1)
Insertion - O(N)
Deletion - O(N)
Searching- O(N)
Queues- Just Like a Cafeteria Line
I can see that you are really enjoying this school example, so I will keep it up. Even though I hate it as much as I hate horses.
Did you know that the last four letters of queue are not silent?
They're just waiting their turn.
Don't believe me? Well look I read that, here:
Queue Fact
We are all familiar with cafeterias. The long lines, the relentlessly being picked on by other kids. What a wonderful place. So imagine you had a line of kids. That is exactly how a queue works. People get in line, at the back, and in order (the first person who gets in line goes first, the second person who gets in line goes second, etc.)
Imagine you are the cafeteria worker in this situation. You can always see who is at the front of the line by peeking through the door. But if you had a favorite kid, Jimmy Borgensen…because let’s be honest that kid is the best, you would have to wait until he was at the front of the line.
Adding people is easy, they go to the back of the line, and removing kids happens when you serve them the disgusting slop that you have for them. Let's hold off a moment before we talk about Big O.
Stacks- Privilege, the Data Structure
Now let’s imagine my school, where cafeteria’s where more like “privilege the data structure” or, as they are known in programming, stacks.
At my school, only the nerds got in line first. Except for me, I was first because I am punctual. Then, the next kid to get in line would always push me and take my spot. But he was always super tough, so I never messed with him. Also, I have a breathing condition so…you know. Like. I can’t. But I would, if I ever needed to. Anyway, it would go on like this. New kids pushing the kids already in the line, the nerds and people who have conditions, until there was never any gruel left for me. But I am thin, and they have diabetes, so who is laughing now?
Not me. Diabetes is no laughing matter, you psychopath.
So you see how the person who got in line last was served first. Because he pushed everyone else down the line. Now, imagine what is different. Not a lot right? The cafeteria workers still served disgusting slop, they could still see who was in the front by peeking out of the door, adding and removing kids remained the same (except being added to the front, not the back). And if they wanted to search for their favorite kids, they had to go through them all until they found Jimmy.
So what does this look like in Big O terms? This is for both stacks
and queues.
Access- O(1)
Insertion - O(1)
Deletion - O(1)
Searching- O(N)