Dealing with data structure is like dealing with your cloth. Some people simply randomly drop their cloth somewhere without thinking. But it takes time to retrieve a specific T-shirt. Some poeple spend some time folding and arranging their cloth. However this process makes it easy to find a specific T-shirt. There is always a balance between the computation time and the coding time.
This is meant for some kind of flash card keywords. I am using this to remind myself some of the important concepts.
- Tree; Binary tree
- Traverse a tree: a. Pre-order traversal: parent->left->right b. In-orer traversal: left->parent->right c. Post-order traversal: left->right->parent d. Level-order traversal: top->bottom, by each level from left to right of the whole tree
Some Useful Data Structures
Array is accessed with indices.
The first element is head while the last element is tail.
Elements can be linked through two different ways, Signly Linked List or Doubly Linked List.
Each node of the singly linked list is assigned two fields, the first field is the value of the node, which stores the information we need, the second field is the link to the next node.
Suppose we are solving the Josephus problem. Linked list is good for deletion, however it is computation expensive when it comes to the counting. On the other hand, array structure is good for determining which one to delete, but the deletion involves rearrangement of index the array which requires some computation power.
Stack is good for adding new items and removing the most recent-added item. (Card on Enki)
Stack data structure is Last in First out, aka LIFO. There are only two ways to change the stack, which are adding item to the stack and removing the item at the top.
Queue is First in First out, aka FIFO. The name Queue explains itself quite well. In a line of queue, the first one in the line would be the first one served and removed from the queue. To add into the queue, we have the put the new guy at the end of the queue.