

In [ ]:

    
%%HTML
<style>
.container { width: 100% }
</style>

Implementing Maps as Lists of Key-Value-Pairs

The class ListNode implements a node of a linked lists of key-value pairs. Every node has three member variables:

mKey stores the key,
mValue stores the value associated with this key, and
mNextPtr stores a reference to the next node. If there is no next node, then mNextPtr is None.

Objects of class ListNode are used to represent linked lists.

The constructor of the class ListNode creates a single node that stores the given key and its associated value.



In [ ]:

    
class ListNode:
    def __init__(self, key, value):
        self.mKey     = key
        self.mValue   = value
        self.mNextPtr = None

Given a key, the method find traverses the given list until it finds a node that stores the given key. In this case, it returns the associated value. Otherwise, None is returned.



In [ ]:

    
def find(self, key):
    ptr = self
    while True:
        if ptr.mKey == key:
            return ptr.mValue
        if ptr.mNextPtr != None:
            ptr = ptr.mNextPtr
        else:
            return
    
ListNode.find = find
del find

Given the first node of a linked list $L$, the function $L.\texttt{insert}(k, v)$ inserts the key-value pair $(k, v)$ into the list $L$. If there is already a key value pair in $L$ that has the same key, then the old value is overwritten. It returns a boolean that is true if a new node has been allocated.



In [ ]:

    
def insert(self, key, value):
    while True:
        if self.mKey == key:
            self.mValue = value
            return False
        elif self.mNextPtr != None:
            self = self.mNextPtr
        else:
            self.mNextPtr = ListNode(key, value)
            return True

ListNode.insert = insert
del insert

Given the first node of a linked list $L$, the function $L.\texttt{delete}(k)$ deletes the first key-value pair of the form $(k, v)$ from the list $L$. If there is no such pair, the list $L$ is unchanged. It returns a pair.

The first component of this pair is a pointer to the changed list.
If the list becomes empty, the first component is None.
The second component is a Boolean that is True if a node has been deleted.



In [ ]:

    
def delete(self, key):
    previous = None
    ptr      = self
    while True:
        if ptr.mKey == key:
            if previous == None:
                return ptr.mNextPtr, True
            else:
                previous.mNextPtr = ptr.mNextPtr
                return self, True
        elif ptr.mNextPtr != None:
            previous = ptr
            ptr      = ptr.mNextPtr
        else:
            break
    return self, False

ListNode.delete = delete
del delete

Given the first node of a linked list $L$, the function $L.\texttt{toString}()$ returns a string representing $L$.



In [ ]:

    
def toString(self):
    if self.mNextPtr != None:
        return f'{self.mKey} ↦ {self.mValue}, ' + self.mNextPtr.__str__()
    else:
        return f'{self.mKey} ↦ {self.mValue}'

ListNode.__str__ = toString
del toString

The class ListMap implements a map using a linked list of key-value pairs. Basically, it is a wrapper for the class ListNode. Furthermore, an object of type ListMap is iterable.



In [ ]:

    
class ListMap:
    def __init__(self):
        self.mPtr = None
        
    def find(self, key):
        if self.mPtr != None:
            return self.mPtr.find(key)
        
    def insert(self, key, value):
        if self.mPtr != None:
            return self.mPtr.insert(key, value)
        else:
            self.mPtr = ListNode(key, value)
            return True
            
    def delete(self, key):
        if self.mPtr != None:
            newPtr, flag = self.mPtr.delete(key)
            self.mPtr    = newPtr
            return flag
        return False
            
    def __iter__(self):
        return MapIterator(self.mPtr)
            
    def __str__(self):
        if self.mPtr != None:
            return '{' + self.mPtr.__str__() + '}'
        else:
            return '{}'
    
    def __repr__(self):
        return self.__str__()

A MapIterator is an iterator that iterates over the elements of a linked list.



In [ ]:

    
class MapIterator:
    def __init__(self, ptr):
        self.mPtr = ptr
    
    def __next__(self):
        if self.mPtr == None:
            raise StopIteration
        key   = self.mPtr.mKey
        value = self.mPtr.mValue
        self.mPtr = self.mPtr.mNextPtr
        return key, value



In [ ]:

    
def main(n = 100):
    S = ListMap()
    for i in range(2, n + 1):
        S.insert(i, True)
    for i in range(2, n // 2 + 1):
        for j in range(i, n // i + 1):
            S.delete(i * j)
    print([p for p, _ in S])
    print(S.find(83))
    print(S.find(99))



In [ ]:

    
main()



In [ ]: