Review
Linked List and Double Linked ListLinked List:
Linked list is a method to store information dynamically and also efficiently. It's dynamic because of the fact that we don't reserve a spot in our memory to store our data, but instead reserve a new spot whenever we want to store an information. The reason we would use this structure instead of a static one like an array list, is because it's simply more efficient to reserve a new spot in the memory when adding a new data rather than reserving spots that might not suffice or use more memory than needed.
Visualization:
Double Linked List:
Double linked list has the same concept as the normal linked list. It's called a double linked list due to the fact that instead of storing a single "next" value in a node, we store a "next" value and a "prev"(previous) value in a every single node.
"prev" holds the address of the previous node. This allows the list to be searched through in 2 different directions instead of a single one like the normal linked list.
visualization:
Stack and Queue
Stack
Stack
Stack is the concept of "what you put in last get put out first". This concept can be put metaphorically as a stack of dishes or a tennis ball cylinder. It's not possible to take something out if there is something else above it in the stack.
visualization:
Queue
The concept is actually really similar to the concept of stack. The name "queue" can be taken quite literally since that is basically what it is, a queue. In a queue, the first person that gets in a queue, gets out on the end of the queue first. This is the concept of "What you put in first, get put out first".
visualization:
The rear is the input direction of the queue and holds the last data in the queue. The head, on the other hand, holds the first data that was inputted and is the output direction of the queue.
Hashing and Binary Tree
Hashing
Hashing is basically giving alias that is determined by a hash function to a data. The reason that whenever we are logging in into an account, it didn’t take a long time for our account data to be retrieved is because they didn’t look and search for our account one by one. By using a hash function and turning our login information into a key, the data that is stored within the index of the key can be immediately called accurately.
Here is a diagram that I’ve made to visualize hashing:
Binary Tree
Binary Tree is a tree data structure that has the special condition of having 2 children at most, thus the word “binary” in the name. Classifying a tree as a binary tree is not that difficult since the condition of “having 2 children at most” is literally the only condition of it. This means that a binary tree’s node doesn’t have to have 2 children beneath it. As long as the number of children in a single node is less than two, it is a binary tree.
Some terminologies and types of Binary Tree might be:
- Balanced Binary Tree:
The concept of minimizing the levels in a binary tree or in other words, “Balancing” a binary tree. Since there are operations in binary tree that depends on the height of a tree, the longer a tree is, the longer that operation will take. Thus, minimizing a tree and keep it as dense (Balanced) as possible is an important aspect.
- Complete Binary Tree:
A binary tree will be called a completed one, if it satisfies 2 requirements: There are no missing nodes (only has 1 child), and the nodes are filled mostly on the left side of the tree rather than the right. However, it’s allowed for the last level of the tree to not be filled completely.
- Perfect Binary Tree:
It’s a binary tree which satisfies the fact that every child is filled. that means that it will always use the maximum number of nodes available in every level.
