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.

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.