CODEWITHSUNDEEP
pythonpython-3.xlinked-list
Brijesh Kalkani
Brijesh Kalkani

Reputation: 851

Linked list implementation in python 3

I am still a beginner in programming. I learned the basics in Python. Right now I'm learning data structures and algorithms.

I have implemented a linked list. But there is a problem inside it. My size is 0 after removing one element. I do not know where the error comes from.

This code was tested in Python 3.7.4.

class Node(object):
    def __init__(self, data):
        self.data = data
        self.nextNode = None


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

    # O(1)
    def insertStart(self, data):  # insert data at beginnning of the list
        self.size += 1
        newNode = Node(data)
        if not self.head:  # the head is None
            self.head = newNode
        else:  # the head is not None
            newNode.nextNode = self.head
            self.head = newNode

    def remove(self,data):
        if self.head is None:
            return

        self.size-=self.size

        currentNode=self.head
        previousNode=None

        while currentNode.data != data:
            previousNode=currentNode
            currentNode=currentNode.nextNode

        if previousNode is None:
            self.head = currentNode.nextNode
        else:
            previousNode.nextNode=currentNode.nextNode

    # O(1)
    def size1(self):
        return self.size

    # O(N)
    def size2(self):
        actualNode = self.head
        size = 0

        while actualNode is not None:
            size += 1
            actualNode = actualNode.nextNode
        return size

    # O(N)
    def insertEnd(self, data):
        self.size += 1
        newNode = Node(data)
        actualNode = self.head
        while actualNode.nextNode is not None:
            actualNode = actualNode.nextNode
        actualNode.nextNode = newNode

    def traverseList(self):
        actualNode = self.head
        while actualNode is not None:
            print("%d " % actualNode.data)
            actualNode = actualNode.nextNode

a=LinkedList()
a.insertStart(3)
a.insertStart(4)
a.insertEnd(5)

#a.remove(3)
#a.remove(4)
a.remove(5)
print(a.traverseList())
print(a.size1())

Upvotes: 1

Views: 308

Answers (1)

TerryA
TerryA

Reputation: 60024

You're subtracting self.size from self.size, which will obviously return 0. You just want to remove 1 (self.size -= 1)

Also, you have another bug. What happens if you try to remove a node which doesn't exist? Your condition while currentNode.data != data: will raise a NoneType error, because it will eventually reach the end of the list (None) without having found the node.

Upvotes: 1

Related Questions