Write a function to count the 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
Following is the Iterative implementation of the above algorithm to find the count of nodes in a given singly linked list.
Javascript
<script>// Javascript program to count number // of nodes in a linked list// Linked list Nodeclass Node { constructor(val) { this.data = val; this.next = null; }}// Head of listvar head; // Inserts a new Node at front of the list.function push(new_data) { // 1 & 2: Allocate the Node & Put in // the data var new_node = new Node(new_data); // 3. Make next of new Node as head new_node.next = head; // 4. Move the head to point to new Node head = new_node;}// Returns count of nodes in linked list function getCount() { var temp = head; var count = 0; while (temp != null) { count++; temp = temp.next; } return count;}// Driver code// Start with the empty listpush(1);push(3);push(1);push(2);push(1);document.write("Count of nodes is " + getCount());// This code contributed by Rajput-Ji </script> |
Output:
count of nodes is 5
Time Complexity: O(n), where n represents the length of the given linked list.
Auxiliary Space: O(1), no extra space is required, so it is a constant.
Recursive Solution:
int getCount(head) 1) If head is NULL, return 0. 2) Else return 1 + getCount(head->next)
Following is the Recursive implementation of the above algorithm to find the count of nodes in a given singly linked list.
Javascript
<script>// Recursive javascript program to count// number of nodes in a linked list// Linked list Nodeclass Node { constructor(val) { this.data = val; this.next = null; }}// Linked List class// Head of listvar head; // Inserts a new Node at front of the list.function push( new_data) { // 1 & 2: Allocate the Node & // Put in the data var new_node = new Node(new_data); // 3. Make next of new Node as head new_node.next = head; // 4. Move the head to point to new Node head = new_node;}Returns count of nodes in linked listfunction getCountRec(node) { // Base case if (node == null) return 0; // Count is this node plus rest // of the list return 1 + getCountRec(node.next);}// Wrapper over getCountRec()function getCount() { return getCountRec(head);}// Driver code// Start with the empty list push(1);push(3);push(1);push(2);push(1);document.write("Count of nodes is " + getCount());// This code contributed by gauravrajput1</script> |
Output:
Count of nodes is 5
Time Complexity: O(n), where n represents the length of the given linked list.
Auxiliary Space: O(n), for recursive stack where n represents the length of the given linked list.
Please refer complete article on Find Length of a Linked List (Iterative and Recursive) for more details!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
