5
\$\begingroup\$

I have implemented a Singly linked list. It works well. But if you think something needs to be improved, say it. 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):

        self.size = self.size + 1
        newNode = Node(data)

        if not self.head:
            self.head = newNode
        else:
            newNode.nextNode = self.head
            self.head = newNode

    def remove(self, data):

        if self.head is None:
            return

        self.size = self.size - 1

        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 insertEnd(self, data):

        self.size = 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(actualNode.data)
            actualNode = actualNode.nextNode
\$\endgroup\$
  • 5
    \$\begingroup\$ You added the unit-testing tag, but I cannot see any unit tests in your code. \$\endgroup\$ – AlexV Oct 9 at 13:24
4
\$\begingroup\$

You are missing several important things for this code:

Type Annotations

Python 3.7 supports type annotations. Especially for a container class like this, you should fully use them.

Initializer parameters

Python containers generally all provide builder methods or class initializer functions that take other containers and use their contents. Consider:

If you're writing a Python container, you need to conform to expectations. I expect to be able to initialize the container when I create it.

Protocols & Magic methods

Python has a well-established set of protocols for implementing containers. You just have to decide what kind of container you're writing.

I would suggest that a singly-linked list is an Iterable, a Sequence, a MutableSequence and possibly a Set type.

\$\endgroup\$
  • 1
    \$\begingroup\$ The type annotations comment is certainly true, but a more direct reference to documentation is important for the uninitiated, if not an example applied to the code. \$\endgroup\$ – Reinderien Oct 10 at 0:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.