# Maps

A map, dictionary, or associative array is an abstract data type storing a collection of key-value pairs, with each key being unique.

## Common operations

Name Description
size() gets the number of key-value entries in the map
get(k) gets the value mapped to key k, if any
set(k,v) maps key k to value v, replacing any existing mapping
remove(k) removes the mapping for key k, if any

## (Naive) Linked list implementation

A simple implementation of a map can be achieved using a linked list (known as an association list ). This results in an average $\mathcal{O}(n)$-time complexity for access and deletion.

For this reason, maps are usually implemented using either a hash table or a binary search tree .

 1public class LinkedMap<K,V> implements MapADT<K,V> {
2    protected class Node {
3        private final K key;
4        private V value;
5        private Node next;
6
7        public Node(K key, V value, Node next) {
8            this.key = key;
9            this.value = value;
10            this.next = next;
11        }
12    }
13
14    private int size = 0;
15    private Node head;
16
17    public int size() {
18        return size;
19    }
20
21    public boolean isEmpty() {
22        return size == 0;
23    }
24
25    public V get(K key) {
26        for (Node x = head; x != null; x = x.next) {
27            if (key.equals(x.key)) return x.value;
28        }
29        return null;
30    }
31
32    public V set(K key, V value) {
33        for (Node x = head; x != null; x = x.next) {
34            if (key.equals(x.key)) {
35                V result = x.value;
36                x.value = value; // replace the value of the existing key-value pair
37                return result;
38            }
39        }
40        // insert the new key-value pair at the beginning of the list
41        head = new Node(key, value, head);
42        size++;
43        return null;
44    }
45
46    public V remove(K key) {
47        Node prev = null;
48        for (Node x = head; x != null; x = x.next) {
49            if (key.equals(x.key)) {
50                V result = x.value;
51                if (prev == null) {
52                    head = null;
53                } else {
54                    prev.next = x.next;
55                }
56                size--;
57                return result;
58            }
59            prev = x;
60        }
61        return null;
62    }
63
64    public void forEach(BiConsumer<K,V> consumer) {
65        for (Node x = head; x != null; x = x.next)
66            consumer.accept(x.key, x.value);
67    }
68}