Abstract Data Types: Sets

What is a set?

A set is a sequential abstract data type where following rules have to be obeyed:

What are the operations a set requires?

Although, as a abstract data type, set comes with no implementation, it requires from data structures that implement it to provide support for a minimal set of operations:

Operation Arguments Returns Description
add VALUE void Adds value to set.
clear   void Clears set of all values.
contains VALUE bool Checks if value exists in set.
find VALUE VALUE Finds and returns value in set.
remove VALUE void Removes element by value.
isEmpty   bool Checks if set is empty
size   ULONG Gets set size

What are the data structures that implement set?

Most common implementations of set are:

This time complexity table using Big O Notation shows advantages and disadvantages of each data structure chosen for each set operation:

Operation Hash Table Linked Hash Table Red Black Tree
add O(1) O(1) O(log(N))
clear O(N) O(N) O(N)
contains O(1) O(1) O(log(N))
find O(1) O(1) O(log(N))
remove O(1) O(1) O(log(N))
isEmpty O(1) O(1) O(1)
size O(1) O(1) O(1)

Conclusion: Hash Table, with its speed/memory efficiency advantages, should be solution of choice unless one specifically desires structure to be predictably iterated or self-ordered!


Share