[Tutor] =Linked List Using Map

[Alan Gauld]

On 17/04/15 19:11, niyanaxx95 at gmail.com wrote:

> Hello I need guidance trying to solve my assignment.
 > I am completely lost when using maps with linked lists.
 > I understand linked lists though.

Unfortunately we do not. Linked lists aren't really
a native Python type and maps are a native type - the
dictionary. So implementing the equivalent of a
native type using a non-native type is kind of a
bizarre situation.

Without knowing how your linked list is built we can't
tell you anything about how to build a map(dictionary)
from it.

> 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.

That's a pretty hefty API for an assignment of this type!

> My Code (so far):

I assume that your Node is in a separate file called LinkedList.py?

> 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

That all seems fairly normal.

> 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)

Where does append() come from? Its not a method of Map.


>      def __len__( self ) :
>          count = 0
>          while self != None:
>              count +=1
>              self = self.next
>          return count

Notice you were asked to provide a length() method so
presumably your __len__() operator should just call
self.length(). And if you update self.numItems
correctly isn't length() just returning self.numItems?

>      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()

you seem to have the setItem and getItem actions reversed?

>
>      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

I suggest you go and have a think about how you will store the key/value 
pairs needed for a map in your list. Then think about
how you find a node by key. Then think about how to get the
value or set a new value on that node.

<rant>
I hate when teachers ask students to do stupid stuff like this.
It encourages so many bad practices it's positively dangerous!
If they must have them reinvent the wheel at least let them
use the native Python list to do it!
</rant>

-- 
Alan G
Author of the Learn to Program web site
http://www.alan-g.me.uk/
http://www.amazon.com/author/alan_gauld
Follow my photo-blog on Flickr at:
http://www.flickr.com/photos/alangauldphotos