Terminology
Abstract Data Type vs. Data Structure
An abstract data type is an idea, a data structure is building that idea. If you have plans for a building, you can talk about how that building will have a certain number of bathrooms, how tall each floor will be, what it will be made out of. You can guarantee, in theory, that the building will be able to perform different functions with a certain amount of efficiency. This is an abstract data type.
In reality, the building gets built out of wood, there is only 1 bathroom in a 6 story building, and all of the businesses go under in the first year. That is a data structure. It is possible for a data structure to accomplish tasks in similar run times to an abstract data type, but you have to know what you are doing, and we have established, that is never going to happen.
Hashing
If I wanted to give you some stuff, but I wanted each thing to be stored in its own, individual box, how would you do it? For a small enough number of things, you could just label each box, 1..2..3..etc. But what if I wanted you to be able to quickly find whatever was in each box? Well, then you would need to find a way to input the name, description, or some other characteristic of the item, and assign it to a box. This is what a hashing function does.
It takes input and runs it through an equation, assigning the unique value that is given to a box. For a more indepth idea of how this works read the "Hash Functions" source below. The idea basically is that if you put in "Hello" and "Help", two different values would come out, and these values would then be mapped to a specific box, making it easy to find these values again. Sometimes, values may get mapped to the same box which is called a collision. I will cover more on that later.
Nodes
A node is like an egg. It contains some data, might have parents, or children. Generally, nodes are used when we talk about graphs and linked lists. If a node has no parent, it is generally called the root (in a tree), or the head (in a linked list, or a tree, depending). If a node has no children it is called a leaf (in a tree), or the tail (in a linked list). We will discuss more about trees (which are types of graphs), and linked lists in this chapter.
Cycles
A graph is a series of connected nodes. Nodes can be connected in many ways. Cycles are relevant to this, because it can tell us if we are dealing with a graph, or a tree. A graph with a cycle, is not a tree. Let me repeat that, IF A GRAPH HAS A CYCLE IT IS NOT A TREE. That is important to remember, and very easy. So remember it.
A cycle looks like this. I have a friend, Janice, Janice has a friend Tommy, Tommy has a friend, me. That is a cycle. If Tommy was not friends with me, then the only way for you to get from Tommy to me would be to go through Janice. Detecting cycles is a common question in programming interviews, so it is good to know about.
Balanced Tree
A balanced tree guarentees that data is evenly distributed. When we talk about trees, we care about their depth. If we continued to add values to a tree that were higher than average, we would be adding elements to the right side. If we continued to to do this, the tree would become unbalanced, since the right side would be longer.
Balanced trees rotate, and move data so that the depth of both sides
remain within certain limitations. This means that the maximum
height of a balanced tree is lg n, rounded down. Need a refresher on
logarthims?
Logarthims And exponenets
Logarthims basics
Khan Logarithms
RAM
Random Access Memory(RAM) is a smaller version of memory. Your computer has a limited amount of memory, it is partitioned into different places, which I will get into in seciton 5. RAM is smaller than your normal hard disk, which stores the files on your computer. RAM does not truly store any data, it temporarily holds onto information that you want, but as soon as power is lost, RAM loses everything.
You can imagine ram is like a series of boxes, each labeled with what it is inside. As soon as you unplug your computer, someone comes over and dumps those boxes into the trash. If your data was saved to your hard disk, then say goodbye.