Using a Linked List to Implement a Set

We will implement the Set interface with a linked list (LinkedSet) and an array (ArraySet). We start with the linked list. As usual, we design before we code.

Representation

We start with a singly linked list, accessed through a head reference, and see whether we can keep this simple structure and still implement the set operations efficiently. We can use the same Node class we used in earlier chapters, and add a size field to the set to keep track of how many items it holds.

Operations and Complexity

size(): Return the stored size. $O(1)$.

contains(item): Perform a linear search. $O(n)$.

add(item): A set has no order, so we can add new items at the head of the list, which is $O(1)$. However, a set holds no duplicates, so before inserting we check whether the item is already present, which is the same linear search that contains performs. This makes the whole operation $O(n)$.

remove(item): We need to find the item first, which is $O(n)$, and then unlink it from the list, which is $O(1)$. The whole operation is $O(n)$.

Why the Operations Stay $O(n)$

Three of the four operations are $O(n)$, and they are $O(n)$ for the same reason: the only way to locate an element is linear search. Turning the singly linked list into a doubly linked list and adding a tail reference does not help, because we still have no way to search for an element other than by scanning through the list.

This is the opposite of what we saw with the stack and the queue. There, narrowing the interface let us make every operation $O(1)$. The set interface is just as narrow, since it has no positions, only membership and a count. But the main thing a set does is answer is this item present, and that is a search. A narrow interface does not make a search any cheaper.

We will see in future chapters how to get around this problem by using different structures that are designed to support fast search.