Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Singly_Linked_List: extra O(n) time complexity while getting length of the list #5315

Closed
jssparas opened this issue Oct 15, 2021 · 3 comments

Comments

@jssparas
Copy link

While getting the length of the linked list, code will take O(n) of unnecessary time as it executes -
len(tuple(iter(self)))
This also takes up O(n) of extra space as it is creating a tuple first.

This can be easily avoided by maintaining an instance variable len, increment/decrement it while inserting/deleting elements.

@jssparas
Copy link
Author

@cclauss I can fix this, please have a look at it.

@symabbas
Copy link

In theory, that statement only adds O(n) time, which if you insert length+=1 / -=1 while adding or removing elements will incur the same extra time i.e the Overall complexity doesn't change. But you're right the creation of a tuple is definitely unnecessary in terms of space. I've made a pull request for the same, check it out: #5320

@cclauss
Copy link
Member

cclauss commented Oct 15, 2021

As discussed in #5320, maintaining an instance variable may be a minor optimization but it has also proven to be a source of bugs. It is pythonic to call len(object) instead of object.length. This is true of Python's builtin lists, dicts, sets, str, tuples, etc. https://docs.python.org/3/reference/datamodel.html#object.__len__ This approach also enables the pythonic if my_linked_list: test to see if the list has content.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
3 participants