4.7. Implementing Maps using Lists¶

It is not difficult to implement a Map using a list. The problem is that all the operations – searching for a key, updating the value for a key, and removing a key – will be linear in the number of entries, $O(n)$ .

In later chapters we will see how to improve the efficiency, by using

Balanced search trees, which bring down the complexity of the operations to $O(\log n)$ .
Hash tables, which make the operations constant time, $O(1)$ .

But some times it is enough to use a simple list-based implementation. And in fact, the separate chaining hash map requires an underlying simpler map implementation – and there a linked list works very fine!

4.7.1. Using a list of key-value pairs¶

A very simple way of implementing a Map using a list, is to use key-value pairs.

Java
Python
class KVPair<K, V> {
    K key;
    V value;
    KVPair(K key, V value) {
        this.key = key;
        this.value = value;
    }
}
class KVPair:
    def __init__(self, key, value):
        self.key = key
        self.value = value

H0 | Class: class KVPair<K, V> 
 H1 | Code Block
 H1 | Method: KVPair(K key, V value) 
   H2 | Code Block

Now we can create a Map class that uses an underlying List of KVPair. So the only thing we need is really an internal variable referring to the underlying list.

Java
Python
class ListMap<K, V> implements Map<K, V> {
    private List<KVPair<K,V>> internalList;

    ListMap() {
        // This could also be a DynamicArrayList.
        internalList = new LinkedList<>();
    }
class LinkedMap(Map):
    def __init__(self):
        # This could also be a DynamicArrayList.
        self._internalList = LinkedList()

H0 | Class: class ListMap<K, V> implements Map<K, V> 
 H1 | Code Block
 H1 | Method: ListMap() 
   H2 | Code Block

Finding the value for a certain key is easy. We just iterate through all entries and stop whenever we find a matching key.

Java
Python
    public V get(K key) {
        for (KVPair<K,V> entry : internalList)
            if (key.equals(entry.key))
                return entry.value;
        return null;
    }
    def get(self, key):
        for entry in self._internalList:
            if key == entry.key:
                return entry.value
        return None

H0 | Method: public V get(K key) 
 H1 | Method: for (KVPair<K,V> entry : internalList)            if (key.equals(entry.key))                return entry.value;
 H1 | Code Block

Setting a value for a given key means to search the list for a matching key, and then updating the value. If we cannot find the key, we add a new KVPair to the list.

Java
Python
    public V put(K key, V value) {
        for (KVPair<K,V> entry : internalList) {
            if (key.equals(entry.key)) {
                V oldValue = entry.value;
                entry.value = value;
                return oldValue;
            }
        }
        // If we're using a DynamicArrayList we should add at the end of the list instead.
        internalList.add(0, new KVPair<>(key, value));
        return null;
    }
    def put(self, key, value):
        for entry in self._internalList:
            if key == entry.key:
                oldValue = entry.value
                entry.value = value
                return oldValue
        # If we're using a DynamicArrayList we should add at the end of the list instead.
        self._internalList.add(0, KVPair(key, value))
        return None

H0 | Method: public V put(K key, V value) 
 H1 | Loop: for (KVPair<K,V> entry : internalList) 
   H2 | If: if (key.equals(entry.key)) 
     H3 | Code Block
 H1 | Code Block

In this example we’re using a linked list, but we could equally well have used a dynamic array list. The only thing we have to think about is to add new pairs at the right location (beginning or end of the list) – because linked lists prefer adding at the front, while array lists rather add to the back of the list.

Other methods can be deferred to the underlying list.

Java
Python
    public boolean isEmpty() {
        return internalList.isEmpty();
    }

    public int size() {
        return internalList.size();
    }
    def isEmpty(self):
        return self._internalList.isEmpty()

    def size(self):
        return self._internalList.size()

H0 | Method: public boolean isEmpty() 
 H1 | Code Block
H0 | Method: public int size() 
 H1 | Code Block

4.7.1.1. How to remove keys from the map¶

There is one problem with this simple map implementation – how to remove keys from it. One possibility would be to first search for the index where the key is located, and then remove that index from the list.

But this would be slightly inefficient, because removing an element from a certain position takes $O(n)$ time in the worst case. So, first we find the position (which takes $O(n)$ time), and then we remove it (which takes another $O(n)$ time). This is double the work than it should be, which is unnecessary.

Java
Python
    // This method is sub-optimal, because it makes two passes:
    // First a search to find the index, and then a loop delete that index.
    public V remove(K key) {
        int i = 0;
        for (KVPair<K,V> entry : internalList) {
            if (key.equals(entry.key)) {
                V removed = entry.value;
                internalList.remove(i);
                return removed;
            }
            i++;
        }
        return null;
    }
    # This method is sub-optimal, because it makes two passes:
    # First a search to find the index, and then a loop delete that index.
    def remove(self, key):
        for i, entry in enumerate(self._internalList):
            if key == entry.key:
                removed = entry.value
                self._internalList.remove(i)
                return removed
        return None

H0 | Method: public V remove(K key) 
 H1 | Code Block
 H1 | Loop: for (KVPair<K,V> entry : internalList) 
   H2 | If: if (key.equals(entry.key)) 
     H3 | Code Block
   H2 | Code Block
 H1 | Code Block

If the Iterator interface would include a method for removing the “current” element from a list, it would be possible to improve the method. Our simple API doesn’t have that possibility, so we have to stick with the slightly slower version. However, in the “real” Java API, iterators have a “remove-the-current” method, so it is possible to optimise removal a little bit. Implementing the remove method using teh delete method of Java Iterators is left as an exercise to the reader.

4.7.2. Using linked key-value nodes¶

An alternative to using an underlying list of key-value pairs, which is also very easy to implement, is to modify the implementation of linked lists just slightly. The advantage of this solution is that deletion becomes more efficient.

Instead of using nodes with just one value, we used key-value nodes.

Java
Python
    private class KVNode {
        K key;
        V value;
        KVNode next;
        KVNode(K key, V value, KVNode next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }
# Python does not have internal classes, so we have to make the list node standalone.
class KVNode:
    def __init__(self, key, value, next):
        self.key = key       # Key for this node
        self.value = value   # Value for this node
        self.next = next     # Pointer to next node in list

H0 | Class: private class KVNode 
 H1 | Code Block
 H1 | Method: KVNode(K key, V value, KVNode next) 
   H2 | Code Block

Then the internal structure is very much like our previous linked lists implementation. The private variables are the same (except we use a KVNode instead of a Node).

Java
Python
class LinkedMap<K, V> implements Map<K, V> {
    private KVNode head;    // Pointer to list header
    private int listSize;   // Size of list

    LinkedMap() {
        head = null;
        listSize = 0;
    }
class LinkedMap(Map):
    def __init__(self):
        self._head = None    # Pointer to list header
        self._listSize = 0   # Size of list

H0 | Class: class LinkedMap<K, V> implements Map<K, V> 
 H1 | Code Block
 H1 | Method: LinkedMap() 
   H2 | Code Block

Searching for a key simply means to iterating through the key-value node until we find a matching key.

Java
Python
    public V get(K key) {
        KVNode current = head;
        while (current != null) {
            if (key.equals(current.key))
                return current.value;
            current = current.next;
        }
        return null;
    }
    def get(self, key):
        current = self._head
        while current is not None:
            if key == current.key:
                return current.value
            current = current.next
        return None

H0 | Method: public V get(K key) 
 H1 | Code Block
 H1 | Loop: while (current != null) 
   H2 | Method: if (key.equals(current.key))                return current.value;
   H2 | Code Block
 H1 | Code Block

Setting a value for a key is similar: If the key is in the list, we upate the associated value. If the key is not in the list, we add a new KVNode and increase the list size.

4.7.2.1. Removing keys¶

To remove a key-value node, we use the same trick as we did for linked lists: We iterate through the previous node instead of the current one. This is to be able to reassign the pointers from the previous node to the following node.

So, we use two nodes – the one to be removed, and the previous one. The loop searches through the nodes until the one to be removed is found, and then reassigns the pointer for the previous node to the following one.

Java
Python
    public V remove(K key) {
        KVNode prev = null;
        KVNode removed = head;
        while (removed != null) {
            if (key.equals(removed.key)) {
                if (prev == null)
                    head = removed.next;
                else
                    prev.next = removed.next;
                removed.next = null;   // For garbage collection
                listSize--;
                return removed.value;
            }
            prev = removed;
            removed = removed.next;
        }
        return null;
    }
    def remove(self, key):
        prev = None
        removed = self._head
        while removed is not None:
            if key == removed.key:
                if prev is None:
                    self._head = removed.next
                else:
                    prev.next = removed.next
                removed.next = None   # For garbage collection
                self._listSize -= 1
                return removed.value
            prev = removed
            removed = removed.next
        return None

H0 | Method: public V remove(K key) 
 H1 | Code Block
 H1 | Loop: while (removed != null) 
   H2 | If: if (key.equals(removed.key)) 
     H3 | Method: if (prev == null)                    head = removed.next;
     H3 | Code Block
   H2 | Code Block
 H1 | Code Block

4.7.3. Linked Maps: Full code¶

Finally, here is the full source code for the class LinkedMap.

Java
Python
class LinkedMap<K, V> implements Map<K, V> {
    private KVNode head;    // Pointer to list header
    private int listSize;   // Size of list

    LinkedMap() {
        head = null;
        listSize = 0;
    }

    private class KVNode {
        K key;
        V value;
        KVNode next;
        KVNode(K key, V value, KVNode next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }

    public V put(K key, V value) {
        KVNode current = head;
        while (current != null) {
            if (key.equals(current.key)) {
                V oldValue = current.value;
                current.value = value;
                return oldValue;
            }
            current = current.next;
        }
        head = new KVNode(key, value, head);
        listSize++;
        return null;
    }

    public V get(K key) {
        KVNode current = head;
        while (current != null) {
            if (key.equals(current.key))
                return current.value;
            current = current.next;
        }
        return null;
    }

    public V remove(K key) {
        KVNode prev = null;
        KVNode removed = head;
        while (removed != null) {
            if (key.equals(removed.key)) {
                if (prev == null)
                    head = removed.next;
                else
                    prev.next = removed.next;
                removed.next = null;   // For garbage collection
                listSize--;
                return removed.value;
            }
            prev = removed;
            removed = removed.next;
        }
        return null;
    }

    public boolean containsKey(K key) {
        return get(key) != null;
    }

    public boolean isEmpty() {
        return listSize == 0;
    }

    public int size() {
        return listSize;
    }

    public Iterator<K> iterator() {
        return new LinkedMapIterator();
    }

    private class LinkedMapIterator implements Iterator<K> {
        private KVNode current;
        LinkedMapIterator() {
            current = head;
        }
        public boolean hasNext() {
            return current != null;
        }
        public K next() {
            K k = current.key;
            current = current.next;
            return k;
        }
    }
}
class LinkedMap(Map):
    def __init__(self):
        self._head = None    # Pointer to list header
        self._listSize = 0   # Size of list

    def put(self, key, value):
        current = self._head
        while current is not None:
            if key == current.key:
                oldValue = current.value
                current.value = value
                return oldValue
            current = current.next
        self._head = KVNode(key, value, self._head)
        self._listSize += 1
        return None

    def get(self, key):
        current = self._head
        while current is not None:
            if key == current.key:
                return current.value
            current = current.next
        return None

    def remove(self, key):
        prev = None
        removed = self._head
        while removed is not None:
            if key == removed.key:
                if prev is None:
                    self._head = removed.next
                else:
                    prev.next = removed.next
                removed.next = None   # For garbage collection
                self._listSize -= 1
                return removed.value
            prev = removed
            removed = removed.next
        return None

    def containsKey(self, key):
        return self.get(key) is not None

    def isEmpty(self):
        return self._listSize == 0

    def size(self):
        return self._listSize

    def __iter__(self):
        current = self._head
        while current is not None:
            yield current.key
            current = current.next


# Python does not have internal classes, so we have to make the list node standalone.
class KVNode:
    def __init__(self, key, value, next):
        self.key = key       # Key for this node
        self.value = value   # Value for this node
        self.next = next     # Pointer to next node in list

H0 | Class: class LinkedMap<K, V> implements Map<K, V> 
 H1 | Code Block
 H1 | Method: LinkedMap() 
   H2 | Code Block
 H1 | Class: private class KVNode 
   H2 | Code Block
   H2 | Method: KVNode(K key, V value, KVNode next) 
     H3 | Code Block
 H1 | Method: public V put(K key, V value) 
   H2 | Code Block
   H2 | Loop: while (current != null) 
     H3 | If: if (key.equals(current.key)) 
       H4 | Code Block
     H3 | Code Block
   H2 | Code Block
 H1 | Method: public V get(K key) 
   H2 | Code Block
   H2 | Loop: while (current != null) 
     H3 | If: if (key.equals(current.key))                return current.value;            current = current.next;        }        return null;    }    public V remove(K key) 
       H4 | Code Block
       H4 | Loop: while (removed != null) 
         H5 | If: if (key.equals(removed.key)) 
           H6 | If: if (prev == null)                    head = removed.next;                else                    prev.next = removed.next;                removed.next = null;   // For garbage collection                listSize--;                return removed.value;            }            prev = removed;            removed = removed.next;        }        return null;    }    public boolean containsKey(K key) 
             H7 | Code Block
           H6 | Method: public boolean isEmpty() 
             H7 | Code Block
           H6 | Method: public int size() 
             H7 | Code Block
           H6 | Method: public Iterator<K> iterator() 
             H7 | Code Block
           H6 | Class: private class LinkedMapIterator implements Iterator<K> 
             H7 | Code Block
             H7 | Method: LinkedMapIterator() 
               H8 | Code Block
             H7 | Method: public boolean hasNext() 
               H8 | Code Block
             H7 | Method: public K next() 
               H8 | Code Block

Data Structures and Algorithms

Chapter 4 Linear Structures