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
- Algorithms to Compute the Length of a Linked List
- Teaching Kids Programming – Compute the Kth Last Node of a Linked List (and Length of a Linked List)
- Teaching Kisd Programming – Finding the Length of a Linked List (Recursion and Iterative Algorithm)
–EOF (The Ultimate Computing & Technology Blog) —
loading...
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