Data Structures Flashcards
The most common data structures in dev
What is the concept of a Binary Search tree?
BST is a data structure that organizes the data in a tree structure. The rule for each parent node in the tree is that all the children to the left should be less than the parent and all the children nodes to the right should be greater. The root node is where the search starts.
What is a Data structure?
It is a format for organizing, managing and storing data such that the computer can efficiently search and find data.
What is a Hash Table and how does it work?
Another data structure that maps keys to the relevant values when storing data. The two main components: the hash function and the hash table.
The hash function is used to map the data to an index that can be stored in the hash table. The reason why this is useful is because data can be of different size, so easier to convert it to an index for storing. The hash function is determined by the programmer and depends on the data, etc. We want a hash function that will separate the data for efficient searching. So if all data points get the same index then they are just stored in a list, which will take O(n) to search where n is number of data points. Thus it would be better to separate them in different indices (aka different hash value), i.e. switch out the hash function.
In the hash table the output from the hash function (i.e. the hash values) are stored, if there are collisions then the most common approach is to use a linked list to store the data under the same hash values.
