Data Structure's Summary

Linked list is more dynamic than Array list. It can store/delete unlimited data.
Actually, there are 3 types of linked list in data structures;

1.    Singly Linked List

2.    Doubly Linked List

3.    Circular Doubly Linked List

§  Singly Linked List

§  Simply, here is the example of a singly linked list.

§  Doubly Linked List

§  Doubly linked list is like singly linked list, but it have two direction for each list, so they could go to the head or tail direction.

§  Here is the example of doubly linked list.

Stack Concept

§  Basically, the data are stored like stacked objects. We insert the object to the last, and the last will be taken first. This is also known as LIFO (Last in First Out).

§  Stack Operations:

• push(x) : add an item x to the top of the stack.
• pop() : remove an item from the top of the stack.
• top() : reveal/return the top item from the stack.

Queue Concept

§  Queue concept is just like the stack concept but this time the first one will be taken first. This is also known as  FIFO (First In First Out).

§  Infix, Postfix, Prefix Notations.

§  Based on how operator is written, there are 3 methods in inserting data:

• Infix
• Operator is written between operands.
• Postfix
• Operator is written after operands.
• Prefix
• Operator is written before operands.

Hashing 

§  Hashing is a technique to store retrieve key in a faster way. 

§  It's transforming a string into a shorter length value/key. (hashed key)

Hash Table

§  Hash table is an array that stores the original value of a string.

§  The hash table size is lower than the total number of possible string (some string can have the same key).

Hash Function

§  There are several methods to hash a string into a key:

• Mid-square
• Square the string, then obtain the key from number of bits taken from the middle of the square.
• Division
• This is the most common and simplest method.
• We can obtain the key by dividing the string with modulus operator.
• Folding
• We can obtain the hash key by dividing the key value into parts. Every parts has the same number of digits(except for the last one). Then add every parts except the last one.
• ex: x= 1264 ; then the parts is 12 & 64 ; then the sum is 76(hash value).
• Digit Extraction
• Considering some digits as a hash address from the given number.
• ex: x=15.769 ; If we extract the first, third and fifth digit, we will obtain the hash code which is 179
• Rotating Hash
• Use any hash method to find the hash code. Then rotate the value from front to back.
• ex: hash address=19920 ; then the rotation result is 02991.
• Collision
• There are two ways to handle collision:
• Linear Probing
• Searching for next empty slot and store the string there.
• Chaining
• Inserting string to a slot as chained list.

Tree

§  Tree is a form of non-linear data structure that describes the relationship that is hierarchical between the elements.

§  Tree can be defined as a collection of nodes with a special element called root and other nodes are divided into sets that are not related to each other (called as sub-tree).

Binary Trees

§  A binary tree is made of nodes where each node contains a left pointer and right pointer. The root pointer points to top of tree. 

§  Left and right pointers point to sub-tree smaller than both sides with recursive.