Linked Implementation of Set
We want to efficiently implement the Set ADT with an underlying linked list. (Go for the simplest choice, singly linked list, unless efficiently demands more complex structures.)
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.
| Operation | How? | Runtime |
|---|---|---|
has | return find(t) != null; | $O(n)$ |
insert | if (find(t) == null), prepend(t); | $O(n)$ |
remove | remove(find(t)); | $O(n)$ |
size | return numElements; | $O(1)$ |
find | Linear search | $O(n)$ |
We can use a doubly linked list so once the "node to be removed" is found, we can remove it in constant time (we need access to the previous node). Or we can have a findPrevious method to get hold of the node before the one "to be removed" in a singly linked list, in linear time, and then remove the "next" node (the target node) in constant time.