Поиск длины связанного списка в python

Question

def len_link(lst): 

"""Returns the length of the link. 

    >>> lst = link(1, link(2, link(3, link(4)))) 
    >>> len_link(lst) 
    4 
    >>> len_link(empty) 
    0 
    """ 

Привет, Мне трудно понять, как найти длину связанного списка, если кто-то может помочь, я был бы очень признателен.

Answer 1

Как указано в "Functional linked lists in Python":

Операция длина возвращает количество элементов в данном списке. Чтобы найти длину списка, нам нужно отсканировать все его n элементов. Следовательно, эта операция имеет временную сложность O (n).

def length(xs): 
    if is_empty(xs): 
     return 0 
    else: 
     return 1 + length(tail(xs)) 

assert length(lst(1, 2, 3, 4)) == 4 
assert length(Nil) == 0 

голова и хвост соответственно:

def head(xs): 
    return xs[0] 

assert head(lst(1, 2, 3)) == 1 
def tail(xs): 
    return xs[1] 

assert tail(lst(1, 2, 3, 4)) == lst(2, 3, 4) 

Answer 2

Вы также можете использовать это:

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