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? — UnholySheep
– UnholySheep, Commented Aug 19, 2020 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
– jonrsharpe, Commented Aug 19, 2020 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
– alani, Commented Aug 19, 2020 at 13:08

chepner · Accepted Answer · 2020-08-19 14:07:42Z

2

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

answered Aug 19, 2020 at 14:07

chepner

538k77 gold badges594 silver badges746 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

rigons99 · Accepted Answer · 2020-08-19 13:24:31Z

1

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.

edited Aug 19, 2020 at 13:24

answered Aug 19, 2020 at 13:16

rigons99

1093 bronze badges

Comments

user14159088 · Accepted Answer · 2020-09-07 00:58:43Z

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.

Collectives™ on Stack Overflow

Length of a circular linked list (python)

3 Answers 3

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related