One need to understand how data structures differ from each other in the way stored data is arranged in memory.
| Python Name | Generic Name | Mutable | Ordered | Contiguous | Homogeneous | Indexable | Average Time Complexity |
|---|---|---|---|---|---|---|---|
| List | Dynamic Array | Yes | Yes | No | No | Yes | Access: O(1) |
| / | Search: O(n) | ||||||
| / | Insert/Delete at end: O(1)* | ||||||
| / | Insert/Delete at beginning: O(n) | ||||||
| Tuple | Fixed Array | No | Yes | No | No | Yes | Access: O(1) |
| / | Search: O(n) | ||||||
| Set | Hash Set | Yes | No | No | No | No | Add/Remove/Contains: O(1) average, O(n) worst |
| / | Iteration: O(n) | ||||||
| Dict | Hash Table / Hash Map | Yes | No** | No | No | Yes*** | Access/Insert/Delete: O(1) average, O(n) worst |
| NumPy Array | Multi-dimensional Array | Yes | Yes | Yes | Yes | Yes | Access: O(1) |
| / | Vectorized operations: O(n) but very fast |
*Amortized O(1) for append operations due to occasional resizing.
**As of Python 3.7, dicts maintain insertion order, but this is considered an implementation detail.
***Indexable by keys, not by numeric indices.
Also, important notes : python lists are not ‘linked lists’ but ‘dynamic arrays’. hashing is a way to allocate a unique identifier for identical objects, enabling fast and efficient data retrieval, typically with constant time complexity O(1).
There are other structures of interest (deque, heap, …) but they are more for ‘niche’ usage.
Also a remark, skiplists are not implemented in python, while they could be useful for several performance improvement cases.
→ if you need an ordered data structure, you need something else than a set, this is not depending on how python is implemented.