educative.io

Length attribute in linked list

Courses
,
#1

A reader asked us the following:

Just a recommendation: Add a “length” attribute to the linked list that updates every time a node is added or removed instead of going through the entire linked list just to return the length. It’s more efficient to keep track of the length than to go through the entire linked list to calculate the length. Keeping track of the length is O(1) vs going through it, which is O(n). Thank you for this amazing course.

The author of the course Vincent Russo replied:

Sure, one could do this. How/why one implements the length function will differ based on one’s use cases and requirements. Doing what the student suggested does allow one to obtain the length of the list in constant time with the (small) drawback of keeping track of the length. This may be disadvantageous in the event where the list rarely changes and the cost of calculating the list offsets the space cost of keeping the variable. These are arbitrary requirements and not exclusive to being the only ones, but they could exist.
But sure, if the user was optimizing for time vs. space in this case, they could simply make this a class variable and update every time a node is removed/added.

1 Like
#3

Even if the list rarely changes, calculating the size without using an instance variable is still going to take time, this is why I believe that implementing a length variable is the best choice.

I tried using sys.getsizeof to determine the size difference between the linked lists, but sys.getsizeof only returns the size of the class (56 bytes always, no matter the number of nodes).

So for comparison, I decided to compare the self.length variable versus the methods that @Vincent_Russo implemented to calculate the length of the linked list.

These methods are:

  • len_iterative
  • len_recursive

using the sys.getsizeof function we can see that using a length attribute in a linked list reduces its size than implementing a method to calculate the length of the list:

llst_len_iter = LinkedList_len_iter()
llst_len_recur = LinkedList_len_recur()
llst_len_var = LinkedList_len_var()

print(getsizeof(llst_len_iter.len_iterative))
print(getsizeof(llst_len_recur.len_recursive))
print(getsizeof(llst_len_var.length))

Results:

64
64
24

However, the size of length when length equals 2^270 is 64. Only then does the “cost of calculating the list offsets the space cost of keeping the variable” (Mr. Russo), but at such a length, it is better to use the length variable to retrieve the length because it is constant time than to use an iterative or recursive solution, a recursive solution fails to retrieve the length around 1000 nodes. Not to mention that it also takes up more levels in the call stack.

1 Like
#4

Hi Carlos,

Thanks for the comment.

Indeed, it will often be advantageous to keep a variable. The “best choice” though is often dependent on the context, where the context may be a technical interview. There are certain systems and scenarios where it would actually make sense to make this sacrifice for a number of reasons.

2 Likes