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}