Linked Implementation of OrderedSet
We want to efficiently implement the OrderedSet ADT with an underlying linked list.
Exercise Complete the following table.
| Operation | How? | Runtime |
|---|---|---|
has | ||
insert | ||
remove | ||
size |
Solution
All operations, except for size, require a helper find method to check if an element exists. We cannot do better than Linear Search for find. (Performing Binary Search on a linked list is futile as its cost is $O(n)$ while its implementation is more complex than Linear Search.)
| Operation | How? | Runtime |
|---|---|---|
has | return find(t) != null; | $O(n)$ |
insert | Find where to insert, then insert! | $O(n)$ |
remove | remove(find(t)); | $O(n)$ |
size | return numElements; | $O(1)$ |
find | Linear search | $O(n)$ |
We can come up with clever implementation so the find method would return the previous node of the target (instead of the target node itself). This will make it easier for the insert method to use the same find operation as the one used by other operations. We leave this as an (unsolved) exercise to you, to implement the operations of OrderedSet using a linked list.