Length of a circular linked list (python)

Question

Hello and thanks in advance for answering my query.

This is a piece of code from a tutorial for determining the length of a circular linked list.

def __len__(self):
cur = self.head
count = 0
while cur:
    count += 1
    cur = cur.next
    if cur == self.head:
        break
return count

In this code, my query is with 'while cur:'. What is this condition exactly checking? Is it checking if cur = self.head is true? If so, then as cur progresses, in the next iteration, cur will be false and traversing the list should stop. But it goes through till the end.

Does this answer your question? [What is Truthy and Falsy? How is it different from True and False?](https://stackoverflow.com/questions/39983695/what-is-truthy-and-falsy-how-is-it-different-from-true-and-false) — UnholySheep, Aug 19 '20 at 13:05
It's checking that `cur` is truthy. *Initially* that's checking if `self.head` is truthy, but then `cur = cur.next`. — jonrsharpe, Aug 19 '20 at 13:06
It is allowing for the possibility that the linked list might not in fact be circular. (Presumably `item.next` will be `None` if there is nothing after `item`.) — alani, Aug 19 '20 at 13:08
Refer [this](https://docs.python.org/3/library/stdtypes.html#truth-value-testing) — Liju, Aug 19 '20 at 13:19

score 2 · Answer 1 · answered Aug 19 '20 at 14:07

This is a case where you actually want to use is. You don't just want to know if you found a node that is equivalent to the head (since that might just mean you found the same value later in the list), you actually want to know if you have reached the actual same node.

This is also an example of an "infinite" loop. You don't need to check anything in the condition itself; an explicit break in the body of the loop takes care of exiting the loop.

def __len__(self):
    cur = self.head
    count = 0
    while True:
        count += 1
        cur = cur.next
        if cur is self.head:
            break
    return count

rigons99 · Accepted Answer · 2020-08-19T13:24:31.267

Firstly you are checking if your head is different from null after which if that is true you will start moving through the list till you come back again to the head of the list which will mean you are done counting. This is done by doing cur = this.next which means you are going to the next element in the linked list and finally if now cur == this.head it means you have passed through the whole list because you are again at the beginning of it.

score 0 · Answer 3 · answered Sep 07 '20 at 00:58

For a singly linked list, the last node would be None like:

head -> 2nd node -> 3rd node -> 4th node -> None

In the above case, cur will become each of the nodes, so while cur will be True for all cases except for the last:

while head -> True
while 2nd node -> True
while 3rd node -> True
while 4th node -> True
while None -> False

So iteration should stop at the last. For the circular linked list, the last node points to the 1st node like:

head -> 2nd node -> 3rd node -> 4th node -> head

Instead of None, cur will be head. So for a circular linked list, while cur will never be False.

while head -> True
while 2nd node -> True
while 3rd node -> True
while 4th node -> True
while head -> True
while 2nd node -> True
while 3rd node -> True
...

It's basically allowing for an infinite loop unless you break out of it.

Length of a circular linked list (python)

3 Answers3