Find Length of a Linked List both Iterative and Recursive:
Write a Python function to count number of nodes in a given singly linked list.
For example, the function should return 5 for linked list 1->3->1->2->1.
Singly Linked List:
Singly Linked List is a collection of ordered set of elements. A Node in singly linked list has two parts – data part and link part. Data part of the node contains the actual information which is represented as node. Link part of the node contains address of next node linked to it.
It can be traversed in only one direction because the node stores only next pointer. So, it can’t reverse linked list.
Iterative Solution
1) Initialize count as 0
2) Initialize a node pointer, current = head.
3) Do following while current is not NULL
a) current = current -> next
b) count++;
4) Return count
Python Programming:
[pastacode lang=”python” manual=”%23%20A%20complete%20working%20Python%20program%20to%20find%20length%20of%20a%0A%23%20Linked%20List%20iteratively%0A%20%0A%23%20Node%20class%0Aclass%20Node%3A%0A%20%20%20%20%23%20Function%20to%20initialise%20the%20node%20object%0A%20%20%20%20def%20__init__(self%2C%20data)%3A%0A%20%20%20%20%20%20%20%20self.data%20%3D%20data%20%23%20Assign%20data%0A%20%20%20%20%20%20%20%20self.next%20%3D%20None%20%23%20Initialize%20next%20as%20null%0A%20%0A%20%0A%23%20Linked%20List%20class%20contains%20a%20Node%20object%0Aclass%20LinkedList%3A%0A%20%0A%20%20%20%20%23%20Function%20to%20initialize%20head%0A%20%20%20%20def%20__init__(self)%3A%0A%20%20%20%20%20%20%20%20self.head%20%3D%20None%0A%20%0A%20%0A%20%20%20%20%23%20This%20function%20is%20in%20LinkedList%20class.%20It%20inserts%0A%20%20%20%20%23%20a%20new%20node%20at%20the%20beginning%20of%20Linked%20List.%0A%20%20%20%20def%20push(self%2C%20new_data)%3A%0A%20%0A%20%20%20%20%20%20%20%20%23%201%20%26%202%3A%20Allocate%20the%20Node%20%26%0A%20%20%20%20%20%20%20%20%23%20%20%20%20%20Put%20in%20the%20data%0A%20%20%20%20%20%20%20%20new_node%20%3D%20Node(new_data)%0A%20%0A%20%20%20%20%20%20%20%20%23%203.%20Make%20next%20of%20new%20Node%20as%20head%0A%20%20%20%20%20%20%20%20new_node.next%20%3D%20self.head%0A%20%0A%20%20%20%20%20%20%20%20%23%204.%20Move%20the%20head%20to%20point%20to%20new%20Node%0A%20%20%20%20%20%20%20%20self.head%20%3D%20new_node%0A%20%0A%20%0A%20%20%20%20%23%20This%20function%20counts%20number%20of%20nodes%20in%20Linked%20List%0A%20%20%20%20%23%20iteratively%2C%20given%20’node’%20as%20starting%20node.%0A%20%20%20%20def%20getCount(self)%3A%0A%20%20%20%20%20%20%20%20temp%20%3D%20self.head%20%23%20Initialise%20temp%0A%20%20%20%20%20%20%20%20count%20%3D%200%20%23%20Initialise%20count%0A%20%0A%20%20%20%20%20%20%20%20%23%20Loop%20while%20end%20of%20linked%20list%20is%20not%20reached%0A%20%20%20%20%20%20%20%20while%20(temp)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20count%20%2B%3D%201%0A%20%20%20%20%20%20%20%20%20%20%20%20temp%20%3D%20temp.next%0A%20%20%20%20%20%20%20%20return%20count%0A%20%0A%20%0A%23%20Code%20execution%20starts%20here%0Aif%20__name__%3D%3D’__main__’%3A%0A%20%20%20%20llist%20%3D%20LinkedList()%0A%20%20%20%20llist.push(1)%0A%20%20%20%20llist.push(3)%0A%20%20%20%20llist.push(1)%0A%20%20%20%20llist.push(2)%0A%20%20%20%20llist.push(1)%0A%20%20%20%20print%20’Count%20of%20nodes%20is%20%3A’%2Cllist.getCount()%0A” message=”” highlight=”” provider=”manual”/] [ad type=”banner”]Output:
count of nodes is 5
Recursive Solution
int getCount(head) 1) If head is NULL, return 0. 2) Else return 1 + getCount(head->next)
Python Programming:
[pastacode lang=”python” manual=”%23%20A%20complete%20working%20Python%20program%20to%20find%20length%20of%20a%0A%23%20Linked%20List%20recursively%0A%20%0A%23%20Node%20class%0Aclass%20Node%3A%0A%20%20%20%20%23%20Function%20to%20initialise%20the%20node%20object%0A%20%20%20%20def%20__init__(self%2C%20data)%3A%0A%20%20%20%20%20%20%20%20self.data%20%3D%20data%20%20%23%20Assign%20data%0A%20%20%20%20%20%20%20%20self.next%20%3D%20None%20%20%23%20Initialize%20next%20as%20null%0A%20%0A%20%0A%23%20Linked%20List%20class%20contains%20a%20Node%20object%0Aclass%20LinkedList%3A%0A%20%0A%20%20%20%20%23%20Function%20to%20initialize%20head%0A%20%20%20%20def%20__init__(self)%3A%0A%20%20%20%20%20%20%20%20self.head%20%3D%20None%0A%20%0A%20%0A%20%20%20%20%23%20This%20function%20is%20in%20LinkedList%20class.%20It%20inserts%0A%20%20%20%20%23%20a%20new%20node%20at%20the%20beginning%20of%20Linked%20List.%0A%20%20%20%20def%20push(self%2C%20new_data)%3A%0A%20%0A%20%20%20%20%20%20%20%20%23%201%20%26%202%3A%20Allocate%20the%20Node%20%26%0A%20%20%20%20%20%20%20%20%23%20%20%20%20%20%20%20%20Put%20in%20the%20data%0A%20%20%20%20%20%20%20%20new_node%20%3D%20Node(new_data)%0A%20%0A%20%20%20%20%20%20%20%20%23%203.%20Make%20next%20of%20new%20Node%20as%20head%0A%20%20%20%20%20%20%20%20new_node.next%20%3D%20self.head%0A%20%0A%20%20%20%20%20%20%20%20%23%204.%20Move%20the%20head%20to%20point%20to%20new%20Node%0A%20%20%20%20%20%20%20%20self.head%20%3D%20new_node%0A%20%0A%20%20%20%20%23%20This%20function%20counts%20number%20of%20nodes%20in%20Linked%20List%0A%20%20%20%20%23%20recursively%2C%20given%20’node’%20as%20starting%20node.%0A%20%20%20%20def%20getCountRec(self%2C%20node)%3A%0A%20%20%20%20%20%20%20%20if%20(not%20node)%3A%20%23%20Base%20case%0A%20%20%20%20%20%20%20%20%20%20%20%20return%200%0A%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%201%20%2B%20self.getCountRec(node.next)%0A%20%0A%20%20%20%20%23%20A%20wrapper%20over%20getCountRec()%0A%20%20%20%20def%20getCount(self)%3A%0A%20%20%20%20%20%20%20return%20self.getCountRec(self.head)%0A%20%0A%23%20Code%20execution%20starts%20here%0Aif%20__name__%3D%3D’__main__’%3A%0A%20%20%20%20llist%20%3D%20LinkedList()%0A%20%20%20%20llist.push(1)%0A%20%20%20%20llist.push(3)%0A%20%20%20%20llist.push(1)%0A%20%20%20%20llist.push(2)%0A%20%20%20%20llist.push(1)%0A%20%20%20%20print%20’Count%20of%20nodes%20is%20%3A’%2Cllist.getCount()%0A” message=”” highlight=”” provider=”manual”/] [ad type=”banner”]Output:
count of nodes is 5