6
\$\begingroup\$
class Node:

    def __init__(self, data):
        self.data = data
        self.next = None


class LinkedList:

  def __init__(self):
      self.head = None
def insert(self, data):
    self.head = self.insertHelper(self.head, data)

def insertHelper(self, head, data):
    if(head == None):
        return Node(data)
    else:
        head.next = self.insertHelper(head.next, data)
    return head

or

def insertR(self, data):
    self.insertRHelper(self.head, data)

def insertRHelper(self, head, data):
        if(head == None):
            self.head = Node(data)
        elif(head.next == None):
            head.next = Node(data)
        else:
            self.insertRHelper(head.next, data)

Any reason why one of these implementations would be better? Personally think the insertR version is easier to look at.

\$\endgroup\$
2
  • 5
    \$\begingroup\$ Welcome to Code Review. Did you write both? \$\endgroup\$ – Mast Apr 24 '20 at 19:58
  • \$\begingroup\$ insertR() is purely mine. insert() was inspired by geeksforgeeks. \$\endgroup\$ – eazyXL Apr 24 '20 at 20:17
15
\$\begingroup\$

Both of these implementations are bad.

The first is probably worse.

  • every node in the linked list, from self.head to the last node's head.next is unconditionally written to, which makes every cache-line/cache-page/virtual-memory-page the linked list touches "dirty" and need to be flushed/written.
  • self.head is passed to insertHelper(), which recursively calls itself N times, eventually (assuming N > 1) returning the value that it was given self.head, to be stored back into the self.head member. This is a LONG critical section. If any threading support was added, locks would need to be held way longer than necessary.

Recursion

Both use recursion, and Python does not do tail-call-optimization. This means that if your linked-list is very long, you will get a stack overflow. There are manual ways to make your function behave in a tail-call-optimized fashion, even if Python won't do it for you, but they are complex and it is by far simpler to just use a loop.

PEP-8

  • Both insertHelper and insertRHelper are helper functions, which should not be exposed a public methods. They should begin with a leading underscore to indicate they are not part of the public interface.
  • The members next, head, and probably data should also not be public, so should be named with a leading underscore.
  • Classes are named using BumpyWords; functions, members and variables should all be snake_case. These means insertHelper should be named _insert_helper, and so on.
  • if(...): is not Pythonic. The parenthesis are unnecessary.

Tail

The best solution would be to maintain a ._tail member in the LinkedList:

class LinkedList:
    """Description of class here"""

    def __init__(self):
        self._head = None
        self._tail = None

    def insert(self, data: Node) -> None:
        """Description of the insert function here"""

        if self._tail:
            self._tail._next = Node(data)
            self._tail = self._tail._next
        else:
            self._head = self._tail = Node(data)

Now, insertions at the tail of the LinkedList are \$O(1)\$.

Naming

As mentioned by Matthieu M. in the comments:

I would also consider renaming here: insert should be append, to make it clear where the insert occurs, and offer a path to proposing different insertions such as prepend, or insert with an index.

\$\endgroup\$
5
  • 2
    \$\begingroup\$ I think you forgot to update self._tail in the case where it already exists. \$\endgroup\$ – ovs Apr 25 '20 at 8:06
  • \$\begingroup\$ @ovs Good catch. Fixed. \$\endgroup\$ – AJNeufeld Apr 25 '20 at 14:35
  • 4
    \$\begingroup\$ I would also consider renaming here: insert should be append, to make it clear where the insert occur, and offer a path to proposing different insertions such as prepend, or insert with an index. \$\endgroup\$ – Matthieu M. Apr 25 '20 at 15:20
  • \$\begingroup\$ @AJNeufeld: I'd honestly prefer if you added it to your answer. I find reading a bunch of short disconnected answer less interesting as the ordering by vote is just not as good as one well-structured answer. \$\endgroup\$ – Matthieu M. Apr 25 '20 at 18:02
  • \$\begingroup\$ Not that I think you’re wrong, but sources or data to back the claim on cache lines would be useful here. There’s enough layers between python code and cpu execution that knowing that off-hand is, well, dubious \$\endgroup\$ – D. Ben Knoble Apr 26 '20 at 0:15

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.