Definition
Stores a unique collection of elements with no defined ordering - no duplicates
Main operations
addandremovecheckIfExists- Optional: set operations, e.g.:
union,intersection,difference
Implementation
| Implementation | Time Complexity | Space Complexity | Advantages | Disadvantages |
|---|---|---|---|---|
| Array-based | Insert: O(n) Delete: O(n) Search: O(n) | O(n) | Simple and straightforward | Not efficient for large sets |
| Linked list-based | Insert: O(n) Delete: O(n) Search: O(n) | O(n) | Efficient for large sets Easy to implement | Slower than hash table or binary search tree for search operations |
| Binary search tree-based | Insert: O(log n) Delete: O(log n) Search: O(log n) | O(n) | Efficient for large sets Sorted values | Worst case time complexity can be O(n) if the tree is unbalanced |
| Hash table-based | Insert: O(1) Delete: O(1) Search: O(1) | O(n) | Very efficient for large sets Constant-time operations on average | Hash collisions must be handled Resizing can be expensive |
- Naive Array
- Inefficient due to membership and element search/deletion being
- If sortable, could sort the array and use binary search for O(logn), but insertion will be O(n)
- hash tables
- O(1) insertion, deletion and search on average
- Tree
- Store set as BST or AVL/RBT
- Searching for an element in a balanced tree takes logarithmic time
- task Flesh out implementation details for Set ADT implementations