How to choose an appropriate data structure
The correct choice of a data structure is crucial to ensure efficiency. In this Answer, we'll look at some common data structures and the operations they are best suited for along with any conditions that may be required for this.
Arrays
- Fast
random access Accessing any element given its index/address - Insertions: If the order of elements doesn't need to be maintained and if the maximum number of elements to be stored is known beforehand. To achieve this, elements could simply be appended at the end of the array after the element at the highest index.
Linked lists
- Insertions: If the order of elements doesn't need to be maintained and if the maximum number of elements to be stored isn't known beforehand (i.e., the data will grow dynamically). To achieve this, elements could simply be inserted at the head of the list. Alternatively, if a tail pointer is used, elements could also be inserted at the tail of the list.
Note: To learn more about linked lists, refer to this link.
Binary search trees
- Insertions: If the order of elements needs to be maintained.
- Searching for a particular element: If there is an order to the elements and if the maximum number of elements to be stored is unknown beforehand.
Note: More specifically, AVL trees should be used for this purpose since they are guaranteed to be balanced.
To learn more about AVL trees, refer to this link.
To learn more about binary search trees, refer to this link.
Hash tables
- Searching for a particular element: If the order of elements needs to be maintained and if the maximum number of elements to be stored is known beforehand.
- Deleting any given element: To delete a given element, it first needs to be found (by searching for it) and is then removed. Thus, a hash table is optimal for this purpose since it allows for the fastest searching.
Note: If the data structure is chosen keeping in mind the fact that the maximum number of elements to be stored is not known beforehand, then using an AVL Tree is more sensible to ensure fast deletions of any given element.
Note: To learn more about hash tables, refer to this link.
Heaps
- Insertions: If the order of elements needs to be maintained.
- Accessing and Deleting: If the element with the smallest value needs to be accessed/deleted each time, it is best to use a min-heap. Similarly, if the element with the largest value needs to be accessed/deleted each time, it is best to use a max-heap.
Note: To learn more about heaps (min-heaps and max-heaps), refer to this link.
Stack
- Accessing and Deleting: If the most recently inserted element needs to be accessed/deleted each time.
Free Resources