Write a C 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.
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
Java Programming:
[pastacode lang=”java” manual=”%2F%2F%20Java%20program%20to%20count%20number%20of%20nodes%20in%20a%20linked%20list%0A%20%0A%2F*%20Linked%20list%20Node*%2F%0Aclass%20Node%0A%7B%0A%20%20%20%20int%20data%3B%0A%20%20%20%20Node%20next%3B%0A%20%20%20%20Node(int%20d)%20%20%7B%20data%20%3D%20d%3B%20%20next%20%3D%20null%3B%20%7D%0A%7D%0A%20%0A%2F%2F%20Linked%20List%20class%0Aclass%20LinkedList%0A%7B%0A%20%20%20%20Node%20head%3B%20%20%2F%2F%20head%20of%20list%0A%20%0A%20%20%20%20%2F*%20Inserts%20a%20new%20Node%20at%20front%20of%20the%20list.%20*%2F%0A%20%20%20%20public%20void%20push(int%20new_data)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F*%201%20%26%202%3A%20Allocate%20the%20Node%20%26%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20Put%20in%20the%20data*%2F%0A%20%20%20%20%20%20%20%20Node%20new_node%20%3D%20new%20Node(new_data)%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F*%203.%20Make%20next%20of%20new%20Node%20as%20head%20*%2F%0A%20%20%20%20%20%20%20%20new_node.next%20%3D%20head%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F*%204.%20Move%20the%20head%20to%20point%20to%20new%20Node%20*%2F%0A%20%20%20%20%20%20%20%20head%20%3D%20new_node%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F*%20Returns%20count%20of%20nodes%20in%20linked%20list%20*%2F%0A%20%20%20%20public%20int%20getCount()%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20Node%20temp%20%3D%20head%3B%0A%20%20%20%20%20%20%20%20int%20count%20%3D%200%3B%0A%20%20%20%20%20%20%20%20while%20(temp%20!%3D%20null)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20count%2B%2B%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20temp%20%3D%20temp.next%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20return%20count%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F*%20Drier%20program%20to%20test%20above%20functions.%20Ideally%0A%20%20%20%20%20%20%20this%20function%20should%20be%20in%20a%20separate%20user%20class.%0A%20%20%20%20%20%20%20It%20is%20kept%20here%20to%20keep%20code%20compact%20*%2F%0A%20%20%20%20public%20static%20void%20main(String%5B%5D%20args)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F*%20Start%20with%20the%20empty%20list%20*%2F%0A%20%20%20%20%20%20%20%20LinkedList%20llist%20%3D%20new%20LinkedList()%3B%0A%20%20%20%20%20%20%20%20llist.push(1)%3B%0A%20%20%20%20%20%20%20%20llist.push(3)%3B%0A%20%20%20%20%20%20%20%20llist.push(1)%3B%0A%20%20%20%20%20%20%20%20llist.push(2)%3B%0A%20%20%20%20%20%20%20%20llist.push(1)%3B%0A%20%0A%20%20%20%20%20%20%20%20System.out.println(%22Count%20of%20nodes%20is%20%22%20%2B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20llist.getCount())%3B%0A%20%20%20%20%7D%0A%7D” 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)
Java Programming:
[pastacode lang=”java” manual=”%2F%2F%20Recursive%20Java%20program%20to%20count%20number%20of%20nodes%20in%20%0A%2F%2F%20a%20linked%20list%0A%20%0A%2F*%20Linked%20list%20Node*%2F%0Aclass%20Node%0A%7B%0A%20%20%20%20int%20data%3B%0A%20%20%20%20Node%20next%3B%0A%20%20%20%20Node(int%20d)%20%20%7B%20data%20%3D%20d%3B%20%20next%20%3D%20null%3B%20%7D%0A%7D%0A%20%0A%2F%2F%20Linked%20List%20class%0Aclass%20LinkedList%0A%7B%0A%20%20%20%20Node%20head%3B%20%20%2F%2F%20head%20of%20list%0A%20%0A%20%20%20%20%2F*%20Inserts%20a%20new%20Node%20at%20front%20of%20the%20list.%20*%2F%0A%20%20%20%20public%20void%20push(int%20new_data)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F*%201%20%26%202%3A%20Allocate%20the%20Node%20%26%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20Put%20in%20the%20data*%2F%0A%20%20%20%20%20%20%20%20Node%20new_node%20%3D%20new%20Node(new_data)%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F*%203.%20Make%20next%20of%20new%20Node%20as%20head%20*%2F%0A%20%20%20%20%20%20%20%20new_node.next%20%3D%20head%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F*%204.%20Move%20the%20head%20to%20point%20to%20new%20Node%20*%2F%0A%20%20%20%20%20%20%20%20head%20%3D%20new_node%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F*%20Returns%20count%20of%20nodes%20in%20linked%20list%20*%2F%0A%20%20%20%20public%20int%20getCountRec(Node%20node)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20Base%20case%0A%20%20%20%20%20%20%20%20if%20(node%20%3D%3D%20null)%0A%20%20%20%20%20%20%20%20%20%20%20%20return%200%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Count%20is%20this%20node%20plus%20rest%20of%20the%20list%0A%20%20%20%20%20%20%20%20return%201%20%2B%20getCountRec(node.next)%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F*%20Wrapper%20over%20getCountRec()%20*%2F%0A%20%20%20%20public%20int%20getCount()%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20return%20getCountRec(head)%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F*%20Drier%20program%20to%20test%20above%20functions.%20Ideally%0A%20%20%20%20%20%20%20this%20function%20should%20be%20in%20a%20separate%20user%20class.%0A%20%20%20%20%20%20%20It%20is%20kept%20here%20to%20keep%20code%20compact%20*%2F%0A%20%20%20%20public%20static%20void%20main(String%5B%5D%20args)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F*%20Start%20with%20the%20empty%20list%20*%2F%0A%20%20%20%20%20%20%20%20LinkedList%20llist%20%3D%20new%20LinkedList()%3B%0A%20%20%20%20%20%20%20%20llist.push(1)%3B%0A%20%20%20%20%20%20%20%20llist.push(3)%3B%0A%20%20%20%20%20%20%20%20llist.push(1)%3B%0A%20%20%20%20%20%20%20%20llist.push(2)%3B%0A%20%20%20%20%20%20%20%20llist.push(1)%3B%0A%20%0A%20%20%20%20%20%20%20%20System.out.println(%22Count%20of%20nodes%20is%20%22%20%2B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20llist.getCount())%3B%0A%20%20%20%20%7D%0A%7D” message=”” highlight=”” provider=”manual”/] [ad type=”banner”]Output:
count of nodes is 5