[Tutor] =Linked List Using Map

[niyanaxx95 at gmail.com]

Sent from Windows Mail





From: Ni'Yana Morgan
Sent: ‎Friday‎, ‎April‎ ‎17‎, ‎2015 ‎2‎:‎06‎ ‎PM
To: tutors at python.org





Hello I need guidance trying to solve my assignment. I am completely lost when using maps with linked lists. I understand linked lists though. May someone work with me?








implement the Map ADT using a singly linked list:


• Map(): Creates a new empty map.

• length(): Returns the number of key/value pairs in the map.

• contains(key): Returns a Boolean indicating if the given key is in the map.

• setitem(key, value): Adds a new key/value pair to the map if the key is not in the map. If the key is in the map, the new value replaces the original value associated with the key. 

• getitem(key): Returns the value associated with the given key, which must exist. 

• clear(): Clears or empties the map by removing all key/value pairs. 

• keys(): Returns a list containing the keys stored in the map. 

• values(): Returns a list containing the values stored in the map. 

• toString(): Returns a string representation of the map in the following format: {k1:v1, k2:v2, ..., kN:vN} 

• min(): Returns the minimum key in the map. The map can not be empty. 

• max(): Returns the maximum key in the map. The map can not be empty. 

• copy(): Creates and returns a new map that is a duplicate copy of this map.




My Code (so far):

class Node:
    def __init__( self, item, next = None ) :
        self.item = item
        self.next = next
    
    def getItem( self ) :
        return self.item
    
    def getNext( self ) :
        return self.next
    
    def setItem( self, item ) :
        self.item = item
        
    def setNext( self, next ) :
        self.next = next




class Map:
    
    def __init__( self, contents = []) :
        self.first = LinkedList.Node(None, None)
        self.last = self.first
        self.numItems = 0
        
        for e in contents:
            self.append(e)
            
    def __len__( self ) :
        count = 0
        while self != None:
            count +=1
            self = self.next
        return count
    
    def contains() :
        pass
    
    def __setitem__( self, index, value ) :
        if index >= 0 and index < self.numItems:
            cursor = self.first.getNext()
            for i in range( index ):
                cursor = cursor.getNext()
            return cursor.getItem()
    
    def __getitem__( self, index, value ) :
        if index >= 0 and index < self.numItems:
            cursor = self.first.getNext()
            for i in range( index ):
                cursor = cursor.getNext()
            cursor.setItem( value )
            return