Using a Linked List to Implement a Map

We will implement the Map interface with a linked list (LinkedMap) and an array (ArrayMap), starting with the linked list.

Representation

As in LinkedSet, we use a singly linked list with a head reference and a size field. The difference is that each node holds two data fields, a key and a value.

          ┌───────┬───────┬──────┐
head ───▶ │  key  │ value │ next │ ──▶ ...
          └───────┴───────┴──────┘
          one node: two data fields and a link to the next

Operations and Complexity

size(), containsKey(key), and remove(key) work as in LinkedSet: size is $O(1)$, containsKey is a linear search in $O(n)$, and remove is an $O(n)$ search followed by an $O(1)$ unlink.

get(key): The same linear search as containsKey, but it returns the matching node’s value. $O(n)$.

put(key, value): First search for the key. If it is already present, replace that node’s value, which is $O(1)$ once found. If it is not present, link a new node in at the head, which is $O(1)$. Either way the search comes first, so the whole operation is $O(n)$.

As with LinkedSet, a doubly linked list or a tail reference would not help, because finding a key still takes a linear search.