# Teaching Kisd Programming – Finding the Length of a Linked List (Recursion and Iterative Algorithm)

Given a singly linked list node, return its length. The linked list has fields next and val.

Constraints
n ≤ 100,000 where n is the number of nodes in node

### Linked List compared to Array/List

List allocation is continuous – meaning all elements in an list/array are put one by one next to each other. Advantages of using a list:

• Random access O(1) time
• Length is known in O(1) time

For linked list, we store additional pointer(s) aka next or previous. The nodes could live in separate RAM addresses. We need O(N) time to locate a particular Node (also finding the length of the Linked List).

As the nodes are not required to be in continuous memory address space, thus it is less likely to suffer from Out-of-Memory. For arrays, if computer can’t find a piece of continuous memory space to hold elements, an Out-of-Memory exception will be thrown.

### Python Definition of Linked List Data Structure

There are two kinds of linked lists: Singly and Doubly. The definition of a singly linked list is:

 ```1 2 3 4 ``` ```class Node:     def __init__(self, val, next):         self.val = val         self.next = next```
```class Node:
def __init__(self, val, next):
self.val = val
self.next = next```

Each node stores the value and a pointer that points to next node. A doubly linked list also stores an additional pointer that points to previous:

 ```1 2 3 4 5 ``` ```class Node:     def __init__(self, val, next, prev):         self.val = val         self.next = next         self.prev = prev```
```class Node:
def __init__(self, val, next, prev):
self.val = val
self.next = next
self.prev = prev```

### Iterative Algorithm to Count the Number of Nodes in a Linked List

We can follow the nodes from the head until we reach the end (None):

 ```1 2 3 4 5 6 7 8 9 10 11 ``` ```# class LLNode: #     def __init__(self, val, next=None): #         self.val = val #         self.next = next class Solution:     def solve(self, node):         ans = 0         while node:             node = node.next             ans += 1         return ans```
```# class LLNode:
#     def __init__(self, val, next=None):
#         self.val = val
#         self.next = next
class Solution:
def solve(self, node):
ans = 0
while node:
node = node.next
ans += 1
return ans```

Time complexity is O(N) as we are traversing each node exactly once. Space complexity is constant.

### Iterative Algorithm to Count the Number of Nodes in a Linked List

The length of the current linked list is equal to 1 plus the length of its next.

 ```1 2 3 4 5 6 7 ``` ```# class LLNode: #     def __init__(self, val, next=None): #         self.val = val #         self.next = next class Solution:     def solve(self, node):         return 1 + self.solve(node.next) if node else 0```
```# class LLNode:
#     def __init__(self, val, next=None):
#         self.val = val
#         self.next = next
class Solution:
def solve(self, node):
return 1 + self.solve(node.next) if node else 0```

Without tail recursion optimisation, the Recursion may suffer from Stack-overflow error if the recursion depths exceeds the stack size.

GD Star Rating