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 execution time 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 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 beginning | ⚫ | 🔴 | 🟢 | ⚫ | 🟢 | ⚫ | ⚫ |
| Remove at beginning | ⚫ | 🔴 | 🟢 | ⚫ | ⚫ | ⚫ | ⚫ |
| Add at end | 🟢 | 🟡 | 🟢 | 🟢 | ⚫ | ⚫ | ⚫ |
| Remove at end | 🟢 | 🟢 | 🟢 | 🟢 | 🟢 | ⚫ | ⚫ |
| Random Insertion | ⚫ | 🔴 | 🟢 | ⚫ | ⚫ | 🟡 | 🟡 |
| Random Removal | ⚫ | 🔴 | 🟢 | ⚫ | ⚫ | 🟢 | 🟢 |
| Search | 🔴 | 🔴 | 🔴 | ⚫ | ⚫ | 🟢 | 🟢 |
Where the meaning of each symbol is,
- 🟢O(1): Constant execution time.
- 🟡O(1)-O(n): Constant execution time in the best case, but linear in the worst case.
- 🔴O(n): Linear execution time, 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 the other, regardless of their position.
Random Access: Means the ability to directly access an element at a specific position in the collection, without needing to traverse sequentially from the beginning.
Add at beginning: The operation of adding a new element to the beginning of the collection.
Remove at beginning: The operation of removing the first element from the collection.
Add at end: Adding a new element to the end of the collection.
Remove at end: Refers to the operation of removing the last element from the collection.
Random Insertion: Means adding a new element at an arbitrary position in the collection.
Random Removal: Is the operation of removing an element at an arbitrary position in the collection.
Search: Means finding a specific element in the collection.
