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
  • No additonal space overhead required
  • 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.

Length of a Linked List Algorithm

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
659 words
Last Post: Teaching Kids Programming - Linear Equation with Two Unknowns (Chicken and Rabbit Problem)
Next Post: Teaching Kids Programming - Remove Duplicates from Sorted Array via Two Pointer Algorithm

The Permanent URL is: Teaching Kisd Programming – Finding the Length of a Linked List (Recursion and Iterative Algorithm)

Leave a Reply