Calculating the length of a Linked-List in Python

Question

I have a linked-list and I want to calculate it's length with a function, here's my definition :

class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

Ok, where's your code that attempts to calculate the length? — PM 2Ring
– PM 2Ring, Commented Aug 7, 2017 at 19:28
Why not, in your linked-list class, have a variable that increments and decrements when you add or remove nodes to and from the list? — RagingRoosevelt
– RagingRoosevelt, Commented Aug 7, 2017 at 19:29
@RagingRoosevelt because you can't do that in any sensible way with a singly linked list. — thebjorn
– thebjorn, Commented Aug 7, 2017 at 19:32
I didn't know how to approach it, and I thought it's simple task to those who know, so it's okay to ask for the code without writing it. — user8430613
– user8430613, Commented Aug 7, 2017 at 19:32
@HiDay it's not. SO is not a code-writing service, and questions like these are very likely to get closed. — thebjorn
– thebjorn, Commented Aug 7, 2017 at 19:34

Idos · Accepted Answer · 2017-08-07 20:47:58Z

3

Try this function:

def length(lst):
    r = 0
    while lst:
        lst = lst.next
        r += 1
    return r # 'r' being the length

It works by moving forward along the list counting the number of nodes observed until a None link is encountered.

Idos

15.3k14 gold badges63 silver badges81 bronze badges

answered Aug 7, 2017 at 19:29

Djaouad

22.8k4 gold badges37 silver badges57 bronze badges

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

Comments

Easton Bornemeier · Accepted Answer · 2017-08-07 19:32:14Z

2

You can simply set the head node to a variable, and continuous count until you hit the point where temp == NULL

def height(list):
    temp=list.head
    count=0
    while temp:
        count+=1
        temp=temp.next
    return count

answered Aug 7, 2017 at 19:30

Easton Bornemeier

1,93610 silver badges22 bronze badges