When to use each Data Structure or Algorithm - Eishaaya/GMRDataStructuresTest GitHub Wiki
Now that you know how these structures work, below are complexities of the data structures as well as their possible use cases.
| Data Structures | Array | Linked List | Stack | Queue | Binary Search Tree | AVL Tree | Red-Black Tree |
|---|---|---|---|---|---|---|---|
| Average Access Time | O(1) | O(n) | N/A | N/A | O(log(n)) | O(log(n)) | O(log(n)) |
| Average Search Time | O(n) | O(n) | N/A | N/A | O(log(n)) | O(log(n)) | O(log(n)) |
| Average Insertion Time | O(n) | O(1) | O(1) | O(1) | O(log(n)) | O(log(n)) | O(log(n)) |
| Average Deletion Time | O(n) | O(1) | O(1) | O(1) | O(log(n)) | O(log(n)) | O(log(n)) |
| Worst Access Time | O(n) | O(n) | N/A | N/A | O(n) | O(log(n)) | O(log(n)) |
| Worst Search Time | O(n) | O(n) | N/A | N/A | O(n) | O(log(n)) | O(log(n)) |
| Worst Insertion Time | O(n) | O(n) | O(1) | O(1) | O(n) | O(log(n)) | O(log(n)) |
| Worst Deletion Time | O(n) | O(n) | O(1) | O(1) | O(n) | O(log(n)) | O(log(n)) |
| Worst Space Complexity | O(n) | O(n) | O(n) | O(n) | O(n) | O(n) | O(n) |
| Data Structures and sorts | Pros | Cons | Use Cases |
|---|---|---|---|
| Array | Nothing can beat the simplicity and traversal time of an Array. Seeing as it is stored in memory as sequential memory locations, lookups are extremely fast along with allocation time. For flat data sets, nothing can beat an array. While there may be issues with adding and deleting, search time and access time of an array are unbeatable. If there is a large amount of sorted sequential data you need to store, an array simply is the best choice. | Adding or removing from an array is expensive, especially when there is a larger amount of data. This is due to the "shuffling" of data from when adding or removing from index to compensate for the changes. In addition, the adding or deleting from an array requires an entirely new array to copy from/to. During these operations, it is not memory or time efficient in these areas. It is also important to note that arrays do not allow named access, only by index in the allocated memory location which is problematic when needing to find things. Lastly, an array cannot realistically represent hierarchical information meaningfully. | Use an array whenever you encounter sets that are relatively stable in the number of items they need, nothing can beat the traversal time of an array/List so use math to your advantage when doing sorts, or constant search time complexity |
| Linked List | Linked List insertion is a superior way to add items to a data structure without needing to double the amount of memory allocated for adding elements. Adding and removing from a linked list solves the problem with arrays for memory allocation and the issue with adding and removing elements while maintaining the same Big-O for operations. Also, it is important to note that depending on the size of sequential memory blocks there is an issue with an array, running out of sequential memory or memory that can be allocated next to each other. A Linked List can continue to expand until all memory is filled, unlike an array which will break when sequential memory runs out. | Pros | Pros |
| Stack | |||
| Queue | |||
| Binary Search Tree | |||
| AVL Tree | |||
| Red-Black Tree |