Data Structure

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 fold and arrange their cloth. However that make it easy to find a specific T-shirt. It’s always a balance between the computation time and the coding time.

Keywords

This is meant for some kind of flash card keywords. I used to remind myself of the important concepts.

Binary Tree

  1. Tree; Binary tree
  2. Traverse a tree:
    1. Pre-order traversal: parent->left->right
    2. In-orer traversal: left->parent->right
    3. Post-order traversal: left->right->parent
    4. Level-order traversal: top->bottom, by each level from left to right of the whole tree

Some Useful Data Structures

Array

Array is accessed with indices.

Linked List

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.

../_images/Singly-linked-list.svg

Fig. 1 Singly linked list illustration from Wikipedia.

Suppose we are solving the Josephus problem. Linked list is good for deletion, however it is computation consuming when it comes to the counting. On the other hand, array structure is good for determining which on to delete, but the deletion involves rearrangement of index the array which is time consuming.

Stack

Stack is good for adding new items and removing the most recent-added item. (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.

../_images/Lifo_stack.png

Fig. 2 Stack from Wikipedia

Queue

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.

../_images/Data_Queue.svg

Fig. 3 Queue from Wikipedia

References and Notes

  1. I learned some of these in enki app.

Back to top

© 2016-2018, Lei Ma | Created with Sphinx and . | On GitHub | Physics Notebook Statistical Mechanics Notebook Neutrino Physics Notes Intelligence | Index | Page Source