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)
        head.next = self.insertHelper(head.next, data)
    return head


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)
            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.

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

1 Answer 1


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.


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.


  • 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.


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
            self._head = self._tail = Node(data)

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


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.

  • 2
    \$\begingroup\$ I think you forgot to update self._tail in the case where it already exists. \$\endgroup\$
    – ovs
    Apr 25, 2020 at 8:06
  • \$\begingroup\$ @ovs Good catch. Fixed. \$\endgroup\$
    – AJNeufeld
    Apr 25, 2020 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\$ Apr 25, 2020 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\$ Apr 25, 2020 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\$ Apr 26, 2020 at 0:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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