DS Implementing a Map and Set with a List

Section 6.3 Implementing a Map and Set with a List

Subsection 6.3.1 Implementing a Map with a List

One of the simplest way to implement a map is with a list. This is not an efficient approach, but it’s a good one to start with so we can use it for comparison purposes. We can use one of our own custom-built list classes, or we can use the built-in Kotlin mutable list. We’ll use a mutable list for simplicity, and store an Entry object, which will store a key and a value within. For each of our methods, we will loop over the list in order to perform the necessary action. Code for this is shown in Listing 6.3.2.

🔗

Listing 6.3.1. Map Implemented with a List

🔗

class ListMap<K, V>: MapADT<K, V> {
    data class Entry<K,V>(val key: K, var value: V)

    private val list = mutableListOf<Entry<K, V>>()

    // Adds the key/value pair to the map.
    // If the key is already in the map, it replaces the old value with the new one.
    override fun put(key: K, value: V) {
        // Look for key in list
        for (entry in list) {
            if (entry.key == key) {
                entry.value = value
                return
            }
        }
        // Key must not have been found
        list.add(Entry(key, value))
    }

    // Returns the value matching the provided key, or null otherwise.
    override fun get(key: K): V? {
        for (entry in list) {
            if (entry.key == key) {
                return entry.value
            }
        }
        // Key must not have been found
        return null
    }

    // Removes the key from the map.
    // Returns the matching value stored in the map, or null otherwise.
    override fun remove(key: K): V? {
        for (index in 0 ..< list.count()) {
            if (list[index].key == key) {
                val value = list[index].value
                list.removeAt(index)
                return value
            }
        }
        // Key must not have been found
        return null
    }

    // Returns true if the key is in the map, false otherwise.
    override fun containsKey(key: K): Boolean {
        for (entry in list) {
            if (entry.key == key) {
                return true
            }
        }
        // Key must not have been found
        return false
    }

    // Returns the number of key/value pairs stored in the map
    override fun size(): Int {
        return list.count()
    }

    override fun toString(): String {
        return list.toString()
    }
}

fun main() {
    val map = ListMap<Int, String>()

    map.put(61820, "Champaign IL")
    map.put(48658, "Stanidsh MI")
    map.put(18222, "Drums PA")
    map.put(75394, "Dallas TX")
    map.put(83344, "Murtaugh ID")
    map.put(32157, "Lake Como FL")
    map.put(25101, "Cumberland MD")
    map.put(74457, "Proctor OK")
    map.put(24002, "Roanoke VA")
    map.put(46957, "Matthews IN")
    println(map)
    println()

    // Access and modify elements in the table
    println("key 32157, value " + map.get(32157)) // Lake Como
    println("key 61820, value " + map.get(61820)) // Champaign
    println("key 95135, value " + map.get(95135)) // null

    map.put(48658, "Standish MI") // correct a misspelling
    println("key 48658, value " + map.get(48658)) // Standish
}

This approach is notable for its simplicity, but let’s consider it’s efficiency. Every one of our methods (except for size performs a sequential search over the list to look for a key. In each case, this is \(O(n)\) in the worst case. We can do a lot better than that, which we will in the following sections.

🔗

Subsection 6.3.2 Implementing a Set with a List

We had indicated in Subsection 6.2.1 that the implementation of a map and a set are nearly identical. The only difference is that a map stores a pair of items: a key and a value. All of the map operations use the key in the same way that a set uses its element. Below, we provide a ListSet implementation. Notice how similar it is to ListMap; the only notable changes (apart from some method names) is that in the set version we don’t need to bother with the value, only the key (referred to as an element).

🔗

Listing 6.3.2. Set Implemented with a List

🔗

class ListSet<E>: SetADT<E> {
    private val list = mutableListOf<E>()

    // Adds the element to the set.
    override fun add(element: E) {
        for (item in list) {
            if (item == element) {
                return   // already there
            }
        }
        // Element must not have been found
        list.add(element)
    }

    // Returns true if the element is in the set, false otherwise.
    override fun contains(element: E): Boolean {
        for (item in list) {
            if (item == element) {
                return true  // found it
            }
        }
        // Element must not have been found
        return false
    }

    // Removes the element from the set.
    // Returns true if the element was in the set; false otherwise.
    override fun remove(element: E): Boolean {
        for (index in 0 ..< list.count()) {
            if (list[index] == element) {
                list.removeAt(index)
                return true
            }
        }
        // Element must not have been found
        return false
    }

    // Returns the number of elements stored in the set
    override fun size(): Int {
        return list.count()
    }

    override fun toString(): String {
        return list.toString()
    }
}

fun main() {
    val set = ListSet<String>()
    set.add("emu")
    set.add("elephant")
    set.add("emu")
    set.add("dolphin")
    println(set)
    println(set.contains("emu"))    // true
    println(set.contains("horse"))  // false
}

This set implementation also has \(O(n)\) performance for all methods except for size. In the next sections, we’ll explore how to improve that.

🔗

You have attempted of activities on this page.

🔗

Prev Top Next