Set
Overview
A Set is an abstract data type that stores a collection of unique elements. Unlike lists, sets do not allow duplicates and usually do not emphasize ordering.
Sets are designed around the idea of membership rather than position.
What Is a Set?
A set:
- Contains no duplicate elements
- Supports efficient membership checks
- May be ordered or unordered (implementation dependent)
Core Set Operations
| Operation | Description |
|---|---|
| Add | Insert an element |
| Remove | Delete an element |
| Contains | Membership test |
| Union | Combine two sets |
| Intersection | Common elements |
| Difference | Elements in one but not the other |
How It Works
Sets are abstract and typically implemented using:
- Hash tables
- Balanced trees
- Bitsets
Each choice affects ordering and performance.
Example
Pseudocode
set = {1, 2, 3}
set.add(2) // no effect
set.add(4)
Real-world Analogy
A set is like a guest list. Each name appears once, no matter how many times it’s suggested 📝🚪.
Time Complexity (Typical)
| Implementation | Add | Remove | Contains |
|---|---|---|---|
| Hash set | O(1) avg | O(1) avg | O(1) avg |
| Tree set | O(log n) | O(log n) | O(log n) |
Use Cases
- Removing duplicates
- Membership testing
- Mathematical set operations
- Tag systems
- Access control lists
Advantages
- Guarantees uniqueness
- Fast lookups
- Clean mathematical semantics
Limitations
- No positional access
- Ordering not guaranteed
- Higher memory overhead than arrays