[Tutor] =Linked List Using Map

[Alan Gauld]

On 19/04/15 16:25, niyanaxx95 at gmail.com wrote:

> May you take a look and let me know what needs to be changed? Thank you in advance.

The node code looks OK.

> class Map:
>

Read through your init method, remembering that it only gets calledv 
once when the Map is created.

>      def __init__( self, contents = []) :
>          self.first = None
>          self.last = self.first
>          self.numItems = 0

So far so good.

>           # traverse the linked list

But there is no list at this point. You just set it to None.

>          node = self.first
>          while node is not None:
>              print("key = %s, value = %s" % (node.key, node.value))
>              node = node.next

So that block does nothing.

>          # Add new node to the end
>          node = self.first
>          if node is None:

And you know the node is NBone so you don;t need a test

>              self.first = Node("the key", "some value")

This is the only meaningful line in the method so far.
Although I suspect the key and value need to be fetched
from somewhere so that they are useful.

Also shouldn't you increment the numItems counter
about now?

>          else:
>              while node.next is not None:
>                  node = node.next
 >              node.next = Node("the key", "some value")

This else block never gets executed either since
the node is always None.

Most of the init method can be deleted.



>      def length( self ) :
>          if node.next == Node("the key", "some value"):
>              self.numItems = self.numItems + 1
>          else:
>              self.numItems = self.numItems - 1
>          return self.numItems

This is just wrong. You keep incrementing numItems but never reset it.
Also you keep creating a new Node then throwing it away.
If you keep numItems up to date as you add and delete
items all you need do is return nnumItems.

>      def contains() :
>          node = self.first
>          while node is not None:
>              if node.key == key:
>                  return True

where does key come from? I assume it should be a
parameter of the method?

>              else:
>                  return False

Thids returns False after the first test. What if the node
you are looking for is further down the list? You need to
exdent (dedent?) this section till its outside the while loop.

>      def setitem( self, key, value ) :
>          node = self.first
>          while node is not None:
>              if key in self.key :

Where does self.key come from? Its not set in the init() method.
Also if its a collection shouldn't it be called keys?

>                          pos = self.key.index(key)
>                          node.value[pos] = value
>                          return

If pos is the index into the list of keys I assume valyue should be a 
corresponding list of values? In which case call it values not value.
But if you are using a ppair of lists to hold the keys and values what 
is the linked list of nodes for? They seem pointless.
But the value(s) dseem to be attached to the node? But the keys are 
attached tgto the Maop(self)? I'm not sure what you are trying to do here.

>              else:
>                          node = node.next
>
>      def getitem( self, key ) :
>          node = self.first
>          while node is not None:
>              assert key in self.key
>              keypos = self.key.index(key)
>              return node.value[keypos]

The while loop only goes as far as the first node.
Does every node contain a list of all the values?
That seems a bit wasteful?

>      # Clears or empties the map by removing all key/value pairs
>      def clear( self ):
>          return self.first == None

This returns a boolean result. Which is not what the
comment says it does.

>      # Returns a list containing the keys stored in the map.
>      def keys( self ):
>          return self.key
>
>      # Returns a list contain the values stored in the map.
>      def values( self ):
>          return self.value

But the values were attacheed to the nodes not self?

>      # Returns a string representation of the map in the following format:{k1:v1, k2:v2, ..., kN:vN}
>      def __repr__( self ):
>          return "{%s}" % (", ".join(["%s:%s" % (k,v) for k, v in zip(self._key, self._value)]))
>
>
>      # Returns the minimum key in the map. The map cannot be empty.
>      def min(self, key ):
>          node = self.first
>          while node is not None and self.first == None:
>              pass

If you set node to be self.first how can they be different
as required by your while loop test?

>      # Returns the maxiumum key in the map. The map cannot be empty.
>      def max( self, key ):
>          node =  self.first
>          while node is not None and self.first == None:
>              pass

As above

>      # Create a new linked list that contains the same entries as the origninal
>      def copy( self ):
>          if self.next is None:
>              return self.value
>          else:
>              return self.value, self.next.copy()

This is returning a tuple not a copy of the original.

Can I suggest you try running your code before posting it. That
way you either have a set of error messages that you don't
understand how to fix, or you fix things so they run but it
doesn't quite do what you want.

We call this testing in the trade and it's a really good idea.
In fact its a good idea to build your classes one method at
a time and test it until that one works before even trying to
write the other methods. That way you know where the
faults lie - in the code you just wrote!

There are all sorts of fancy testing tools you can use, but just 
starting the >>> interactive prompt, importing your class file,
creating some instances and calling the methods with different
values is a great starting point!

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