CODEWITHSUNDEEP
python-3.xlinked-list
d'chang
d'chang

Reputation: 191

Finding the length of a linked list in python

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
    """

Hi I'm having a hard time understanding how to find the length of a linked list if someone could help I would really appreciate it.

Upvotes: 6

Views: 48683

Answers (4)

yo1995
yo1995

Reputation: 637

FYI: 2-line Python snippets to count the length of a singly linked-list

# iterative
n, curr = 0, head
while curr: n, curr = n + 1, curr.next

# recursive
def length(head: ListNode):
    return 0 if not head else 1 + length(head.next)

Upvotes: 1

Gaurao Mate
Gaurao Mate

Reputation: 23

try this:

def lengthRecursive(head):
    if head is None:
        return 0
    else:
       return 1 + lengthRecursive(head.next)

Upvotes: 1

Nitika Khurana
Nitika Khurana

Reputation: 69

You can also use this:

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

Upvotes: 6

Abhishek Dey
Abhishek Dey

Reputation: 1639

As stated in "Functional linked lists in Python":

The length operation returns the number of elements in a given list. To find the length of a list we need to scan all of its n elements. Therefore this operation has a time complexity of 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

head and tail are respectively:

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)

Upvotes: 0

Related Questions