CODEWITHSUNDEEP
pythonlinked-list
Ashwin Kambli
Ashwin Kambli

Reputation: 21

Python - Linked List node comparision requires additional dereferencing

I am using Python 3.6.3. I am trying to write a simple Linked List in Python. Here is my code: 

    class Node(object):
    """Represents a node within a linked list"""
    def __init__(self, data, next=None):
        self.stuff = data
        self.next = next

    def __str__(self):
        return str(self.stuff)

class LinkedList(object): 
    def __init__(self):
        self.head = None
        self.size=0

    def append(self, data):
        if not self.head:
            self.head = Node(data)
            return
        else:
            n=self.head
            while n.next:
                n = n.next

            new_node = Node(data)
            n.next = new_node
            return

    def insertAfter(self, data, newNode):
        if not self.head:
            return
        else:
            n=self.head
            while n and n.stuff != data:
                n = n.next

            if not n:
                return
            else:
                newNode.next = n.next
                n.next = newNode
                return

    def printlist(self):
        if not self.head:
            print("List is empty")
            return
        else:
            n = self.head
            while n:
                print(str(n))
                n = n.next
        return

ll = LinkedList()
ll.append(Node("1"))
ll.append(Node("2"))
ll.append(Node("3"))
ll.insertAfter("2", Node("2.5"))
ll.printlist()

I expect it to print: 

1
2
2.5
3

But, instead it prints: 

1
2
3

After debugging, I realized that changing this line in the insertAfter method: 

while n and n.stuff != data:

to:

while n and n.stuff.stuff != data:

prints the expected output. I don't understand why it is doing this. Please help. Thank you

Upvotes: 2

Views: 225

Answers (1)

ubadub
ubadub

Reputation: 3880

The problem is you are not adding 1, 2, 3 to the LinkedList and letting it create a Node to wrap each. You are adding a Node whose stuff variable is 1, 2, and 3. When you call the append method to add each Node, they get wrapped in another Node by the append method. Therefore you need to call Node.stuff.stuff to access the actual element that is stored.

Look at what your append method is actually doing. It accepts some parameter data and then creates a Node with either the line self.head = Node(data) or the line new_node = Node(data), depending on if the LinkedList already has a head Node or not.

Change ll.append(Node("1")) to just ll.append("1"). Alternatively, change your append method to assume it is being passed a Node object. The first solution is much more preferable as the Node class has little use outside the context of the LinkedList class and the LinkedList doesn't work unless it is populated with Nodes anyways; it seems like extra work to make the user of the LinkedList class have to create a Node every single time.

EDIT: Also what is the reason you are passing in numbers as strings? You don't need to put 1, 2, 2.5, and 3 in quotes unless you specifically want them to be strings- but if so, why?

Upvotes: 3

Related Questions