The efficiency of a collection refers to its ability to perform operations quickly and efficiently, minimizing the time and resources used.
When evaluating the efficiency of a collection, it is important to consider the runtime of key operations, such as reading, inserting, deleting, and searching for elements.
These operations vary depending on the type of collection and its internal implementation.
Efficiency Comparison Table
Let’s take a look at a summary table of the efficiencies of the collections we have seen in the course, for different operations:
| Operation | Array | List | LinkedList | Stack | Queue | Set | Dict |
|---|---|---|---|---|---|---|---|
| Sequential Access | 🟢 | 🟢 | 🟢 | ⚫ | ⚫ | ⚫ | ⚫ |
| Random Access | 🟢 | 🟢 | 🔴 | ⚫ | ⚫ | 🟢 | 🟢 |
| Add at the beginning | ⚫ | 🔴 | 🟢 | ⚫ | 🟢 | ⚫ | ⚫ |
| Delete at the beginning | ⚫ | 🔴 | 🟢 | ⚫ | ⚫ | ⚫ | ⚫ |
| Add at the end | 🟢 | 🟡 | 🟢 | 🟢 | ⚫ | ⚫ | ⚫ |
| Delete at the end | 🟢 | 🟢 | 🟢 | 🟢 | 🟢 | ⚫ | ⚫ |
| Random Insertion | ⚫ | 🔴 | 🟢 | ⚫ | ⚫ | 🟡 | 🟡 |
| Random Deletion | ⚫ | 🔴 | 🟢 | ⚫ | ⚫ | 🟢 | 🟢 |
| Search | 🔴 | 🔴 | 🔴 | ⚫ | ⚫ | 🟢 | 🟢 |
Where the meaning of each symbol is,
- 🟢O(1): Constant runtime.
- 🟡O(1)-O(n): Constant runtime in the best case, but linear in the worst case.
- 🔴O(n): Linear runtime, proportional to the size of the collection.
- ⚫N/A: The operation is not applicable or does not make sense for that particular collection.
Description of operations
Here is a description of each of the operations mentioned in the table:
Sequential Access: Refers to the ability to access the elements of the collection in sequence, one after another, regardless of their position.
Random Access: Means the ability to directly access an element at a specific position in the collection, without the need to sequentially traverse from the beginning.
Add at the beginning: The operation of adding a new element at the beginning of the collection.
Delete at the beginning: It is the operation of deleting the first element of the collection.
Add at the end: Adding a new element at the end of the collection.
Delete at the end: Refers to the operation of deleting the last element of the collection.
Random Insertion: Means adding a new element at an arbitrary position in the collection.
Random Deletion: It is the operation of deleting an element at an arbitrary position in the collection.
Search: Means finding a specific element in the collection.