[Tutor] =Linked List Using Map

[Steven D'Aprano]

Hello Ni'Yana, and welcome!

On Fri, Apr 17, 2015 at 06:11:00PM +0000, 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. May someone work with me?

We will not do your homework, but perhaps we can guide you.

Thank you for showing your code. It looks like you have already made a 
lot of progress.

Unfortunately, the one thing you did not tell us is what part of the 
assignment you are having problems with! It looks like you have done 
most of the work correctly so far, so what part is giving you trouble?

A few comments on your code below:


> 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

Your Node class looks straightforward, but it doesn't match the 
requirements. The requirement for the Map is that it must have key:value 
pairs. But your Node doesn't have two data fields, it only has one! So 
you cannot give the Node both a key and a value.

Your Node class needs to start like this:

class Node:
    def __init__(self, key, value, next=None):
        self.key = key
        self.value = value
        self.next = next


That will help get the Map class right. See my comments below.


> class Map:
>     def __init__( self, contents = []) :
>         self.first = LinkedList.Node(None, None)

First problem: you have added code which is not part of the 
specifications. The assignment says that calling Map() returns a new 
empty map. It says nothing about Map([1, 2, 3]). Get rid of the 
"contents" argument, it is not required. Once you get rid of that, the 
"for e in contents" loop is not required. Get rid of it!

Second problem: LinkedList is not defined anywhere. What is it?

The easiest way for this to work is to put the None class and the Map 
class in the same file, and then you can just say:

        self.first = Node(None, None)

without worrying about the name of the file. Java has a rule that each 
class, no matter how tiny, must go in its own file, but Python does not
have such a rule. Related classes may go in the same file.

Third problem: your assignment to self.first is wrong! That gives 
the Map a single item, not zero items!

An empty linked list will be represented here by just None alone.

        self.first = None

You then traverse the linked list like this:


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

which will print all the keys and values in the map.

To add a new node to the end, you do this:

    node = self.first
    # The empty Map case is special.
    if node is None:
        self.first = Node("the key", "some value")
    else:
        while node.next is not None:
            node = node.next
        # Now we are at the end of the linked list.
        # Add a new node.
        node.next = Node("the key", "some value")

>         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

I don't think that this will do what your assignment asks. 

The first problem is that your assignment says that your Map must have a 
method called `length` which returns the number of items. Your Map class 
has no method called `length`, instead it uses the Python special 
__len__ method.

I think you need to change the name of this __len__ method to length. It 
is still be buggy (have you tested it?) but at least it will do what the 
assignment says.

Let us think about how to implement this length method. It is actually 
very easy! Your Map class already has a counter which tell you how many 
items are in the map, and it is initialised with:

        self.numItems = 0

so length is easy:

def length(self):
    return self.numItems


Now all you need to do is make sure that every time you add a node to 
the Map, add 1 to numItems, and every time you delete a node, you 
subtract 1.


>     def contains() :
>         pass

I assume this is just a stub which is not finished yet.

The contains method just needs to walk the linked list and look for the 
key. I showed you code above that walks the linked list printing keys 
and values. Instead of printing, you compare the node's key to the key 
you are looking for, and if they are equal, return True:

        while node is not None:
            if node.key == key:
                return True


If you reach the end of the linked list without finding the key, you 
have to return False.


Both your __setitem__ and __getitem__ methods also ignore what the 
assignment says. The assignment wants methods called `setitem` and 
`getitem`, not the special Python double-underscore methods. So you need 
to change their names, then test them.

Also, they fail to do what the assignment says. Read the requirements:

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

Does your __getitem__ method take a key as argument? No it does not, it 
takes an index!

getitem needs to take a single argument, the key. It then walks the 
linked list (as I showed you above), comparing the node's key to the 
wanted key. If they are equal, you then return node.value. If they are 
not equal, go on to the next node.

If you run out of nodes before finding the key, that is an error.

setitem needs to take two arguments, a key and a value. You then walk 
the linked list (again!) and compare the node's key to the wanted key. 
If they are equal, you set the node's value to the new value:

    node.value = value

and return.

If you run out of nodes, you add a new node at the end.

Remember what I said about incrementing the counter!

By this time, you should see a pattern. Nearly all these methods 
demonstrate the same sort of procedure: you walk the linked list, 
looking at each node in turn:

    node = self.first
    while node is not None:
        do_something_with(node)



-- 
Steve