Medium Structures
Dictionary/Hash- Teachers in a Room
A new data structure means a new example, isn’t this fun? No? Well no one asked for your opinion anyway. Since, the school example from the previous section went over so well, we are going to continue to use it. There is a difference between dictionaries and hashes, tehcnically, read about it here:
Dictionaries/hashes, I will be referring to them as hashes. Imagine that you have a bunch of teachers, each of whom is given a room. All of the room assignments are on a directory. Finding out if a given room has been assigned would be an easy task, just look in the directory. If it is there, it has been assigned, if not, then it hasn’t.
That is how hashes work. So, finding a room would be easy, it is either on the directory or not. So that would take no time at all.
Searching depends on what you are looking for. Imagine if the directory just had room assignments, but not who was assigned there. You would have to go to each room to check. But if you were just searching for the rooms, then it would still be simple.
Removing or adding people to a room would be easy. If a room is unused, add a teacher to it. If it is in use, then you just remove it. Simple as pie. There is a more complex example, called collisions. It is not super important, but worth knowing about, so read about it in the complex section.
So what is the Big O for accessing, inserting, and deleting from a
hash?
Insertion - O(1)
Deletion - O(1)
Access - O(1)
Searching - O(1) [As long as you assign keys and values correctly]
Linked Lists- People Call Their Neighbors
Let’s say you are the principal at a school, and you want to talk to every teacher, and you are in an office. However, we know you. You are a lazy person, and an even lazier principal, so you don’t want to call every teacher, you want to call one (or maybe two) teachers, and then have them call the rest. So you assign the first teacher to call the second one, the second one to call the third, and so on.
This is how a linked list works. Data is held in nodes, which have a head, a tail, and can either be singly linked (1-> 2–> 3) or doubly linked (1-> 2–> 3 AND 3-> 2–> 1). Now, imagine you wanted to find a teacher with a particular name using this scheme, there is only one way to do it. Call the first teacher, and then go through each one until you find them.
Hiring a new teacher would be easy, since all you would have to do
is tell the last teacher that they have to call in another teacher.
And so too would firing them. You just call in the teacher before
the one you are firing, and tell them to call the person after the
teacher you are firing.
That might be slightly confusing so let’s
use an example:
Ms. Crab calls Mr. Scwalksky
Mr. Scwalksky calls Dr. Urchin
We all know we have to fire Mr. Scwalksky, and we know why too. He has been mean to Jimmy. We cannot hold it against Jimmy, doesn't need to show up to school. And so what if he doesn't do homework? Jimmy doesn't need to, he's the best. When you fire Mr. Scwalksky, you call in Ms. Crab and tell her she is going to start calling Dr. Urchin instead.
In a system where you had teachers who called two people (the person after them, and the person before them) then this task is still simple. You still tell Ms. Crab to call Dr. Urchin, then you tell Dr. Urchin to start calling Ms. Crab. Easy as Suday Morning.
So what are the Big O notations of these operations?
Access - O(N)
Insertion - O(1)
Deletion - O(1)
Searching- O(N)
Graphs- Human Interactions
Graphs are a hard data structure to imagine. I mean, not for anyone over the age of two, except for you. I am trying to be patronizing…or….helpful? I always get those two mixed up.
Graphs are like relationships, horrible. Now imagine all relationships were treated as equal. You either have a relationship with someone (your parent, your lover, your tax attorney) or you don’t. Your connections have relationships with other people (surprise! You are not the center of the universe). Think about how you would send a message to someone, without sending it to them directly. Like if you wanted to passively aggressively tell Bernard he looked fat in a pair of jeans. You could send that message to your friend, who would then tell their friend, who would then tell them.
Now, unlike you, they are not afraid of telling you that you suck
directly to your face. This is exactly what a cycle is!
You—> Your friend —> Their Friend —> Them —> You (bad person)
Cycles are very important for graph theory, since they determine if a graph is a tree or not (as does direction). What is a tree? And directed graphs? It’s very rude to ask questions while I am typing this. You either trust that I will get to it, or you don’t. I know you, you don’t trust me. That’s because you are a bitter and lonely person.
Big O is complex, so we will talk about that in the complex section. There are a few other important things, one of which is directed or undirected graphs. Keeping with the friendship example. Imagine you called someone your friend, but they didn't feel the same way about you (not hard to imagine), or you both call each other friends. That is the difference between a directed and undirected graph. Undirected, you are both friends, directed, only one of you considers the other a friend. There are also sometimes weights, which is to say certain connections have higher/lower values. You can think of this as the difference between your relationship with your parents, your enemies, your significant other, etc. Some are more important than others. My girlfriend, for example, looks just like God to me.
Imaginary.
Another important note is that a graph is made up of nodes (think of
them as people). A person can have many friends, or a few. A graph
is said to be sparse when there are few nodes, and dense when there
are many. For more on graphs, look at the complex page.