Write a C function to count number of nodes in a given singly linked list.

C Algorithm - Find Length of a Linked List both Iterative and Recursive

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

C Programming:

[pastacode lang=”c” manual=”%2F%2F%20Iterative%20C%20program%20to%20find%20length%20or%20count%20of%20nodes%20in%20a%20linked%20list%0A%23include%3Cstdio.h%3E%0A%23include%3Cstdlib.h%3E%0A%20%0A%2F*%20Link%20list%20node%20*%2F%0Astruct%20node%0A%7B%0A%20%20%20%20int%20data%3B%0A%20%20%20%20struct%20node*%20next%3B%0A%7D%3B%0A%20%0A%2F*%20Given%20a%20reference%20(pointer%20to%20pointer)%20to%20the%20head%0A%20%20of%20a%20list%20and%20an%20int%2C%20push%20a%20new%20node%20on%20the%20front%0A%20%20of%20the%20list.%20*%2F%0Avoid%20push(struct%20node**%20head_ref%2C%20int%20new_data)%0A%7B%0A%20%20%20%20%2F*%20allocate%20node%20*%2F%0A%20%20%20%20struct%20node*%20new_node%20%3D%0A%20%20%20%20%20%20%20%20%20%20%20%20(struct%20node*)%20malloc(sizeof(struct%20node))%3B%0A%20%0A%20%20%20%20%2F*%20put%20in%20the%20data%20%20*%2F%0A%20%20%20%20new_node-%3Edata%20%20%3D%20new_data%3B%0A%20%0A%20%20%20%20%2F*%20link%20the%20old%20list%20off%20the%20new%20node%20*%2F%0A%20%20%20%20new_node-%3Enext%20%3D%20(*head_ref)%3B%0A%20%0A%20%20%20%20%2F*%20move%20the%20head%20to%20point%20to%20the%20new%20node%20*%2F%0A%20%20%20%20(*head_ref)%20%20%20%20%3D%20new_node%3B%0A%7D%0A%20%0A%2F*%20Counts%20no.%20of%20nodes%20in%20linked%20list%20*%2F%0Aint%20getCount(struct%20node*%20head)%0A%7B%0A%20%20%20%20int%20count%20%3D%200%3B%20%20%2F%2F%20Initialize%20count%0A%20%20%20%20struct%20node*%20current%20%3D%20head%3B%20%20%2F%2F%20Initialize%20current%0A%20%20%20%20while%20(current%20!%3D%20NULL)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20count%2B%2B%3B%0A%20%20%20%20%20%20%20%20current%20%3D%20current-%3Enext%3B%0A%20%20%20%20%7D%0A%20%20%20%20return%20count%3B%0A%7D%0A%20%0A%2F*%20Drier%20program%20to%20test%20count%20function*%2F%0Aint%20main()%0A%7B%0A%20%20%20%20%2F*%20Start%20with%20the%20empty%20list%20*%2F%0A%20%20%20%20struct%20node*%20head%20%3D%20NULL%3B%0A%20%0A%20%20%20%20%2F*%20Use%20push()%20to%20construct%20below%20list%0A%20%20%20%20%201-%3E2-%3E1-%3E3-%3E1%20%20*%2F%0A%20%20%20%20push(%26head%2C%201)%3B%0A%20%20%20%20push(%26head%2C%203)%3B%0A%20%20%20%20push(%26head%2C%201)%3B%0A%20%20%20%20push(%26head%2C%202)%3B%0A%20%20%20%20push(%26head%2C%201)%3B%0A%20%0A%20%20%20%20%2F*%20Check%20the%20count%20function%20*%2F%0A%20%20%20%20printf(%22count%20of%20nodes%20is%20%25d%22%2C%20getCount(head))%3B%0A%20%20%20%20return%200%3B%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)

C Programming:

[pastacode lang=”c” manual=”%2F%2F%20Recursive%20C%20program%20to%20find%20length%20or%20count%20of%20nodes%20in%20a%20linked%20list%0A%23include%3Cstdio.h%3E%0A%23include%3Cstdlib.h%3E%0A%20%0A%2F*%20Link%20list%20node%20*%2F%0Astruct%20node%0A%7B%0A%20%20%20%20int%20data%3B%0A%20%20%20%20struct%20node*%20next%3B%0A%7D%3B%0A%20%0A%2F*%20Given%20a%20reference%20(pointer%20to%20pointer)%20to%20the%20head%0A%20%20of%20a%20list%20and%20an%20int%2C%20push%20a%20new%20node%20on%20the%20front%0A%20%20of%20the%20list.%20*%2F%0Avoid%20push(struct%20node**%20head_ref%2C%20int%20new_data)%0A%7B%0A%20%20%20%20%2F*%20allocate%20node%20*%2F%0A%20%20%20%20struct%20node*%20new_node%20%3D%0A%20%20%20%20%20%20%20%20%20%20%20%20(struct%20node*)%20malloc(sizeof(struct%20node))%3B%0A%20%0A%20%20%20%20%2F*%20put%20in%20the%20data%20%20*%2F%0A%20%20%20%20new_node-%3Edata%20%20%3D%20new_data%3B%0A%20%0A%20%20%20%20%2F*%20link%20the%20old%20list%20off%20the%20new%20node%20*%2F%0A%20%20%20%20new_node-%3Enext%20%3D%20(*head_ref)%3B%0A%20%0A%20%20%20%20%2F*%20move%20the%20head%20to%20point%20to%20the%20new%20node%20*%2F%0A%20%20%20%20(*head_ref)%20%20%20%20%3D%20new_node%3B%0A%7D%0A%20%0A%2F*%20Counts%20the%20no.%20of%20occurences%20of%20a%20node%0A%20%20%20(search_for)%20in%20a%20linked%20list%20(head)*%2F%0Aint%20getCount(struct%20node*%20head)%0A%7B%0A%20%20%20%20%2F%2F%20Base%20case%0A%20%20%20%20if%20(head%20%3D%3D%20NULL)%0A%20%20%20%20%20%20%20%20return%200%3B%0A%20%0A%20%20%20%20%2F%2F%20count%20is%201%20%2B%20count%20of%20remaining%20list%0A%20%20%20%20return%201%20%2B%20getCount(head-%3Enext)%3B%0A%7D%0A%20%0A%2F*%20Drier%20program%20to%20test%20count%20function*%2F%0Aint%20main()%0A%7B%0A%20%20%20%20%2F*%20Start%20with%20the%20empty%20list%20*%2F%0A%20%20%20%20struct%20node*%20head%20%3D%20NULL%3B%0A%20%0A%20%20%20%20%2F*%20Use%20push()%20to%20construct%20below%20list%0A%20%20%20%20%201-%3E2-%3E1-%3E3-%3E1%20%20*%2F%0A%20%20%20%20push(%26head%2C%201)%3B%0A%20%20%20%20push(%26head%2C%203)%3B%0A%20%20%20%20push(%26head%2C%201)%3B%0A%20%20%20%20push(%26head%2C%202)%3B%0A%20%20%20%20push(%26head%2C%201)%3B%0A%20%0A%20%20%20%20%2F*%20Check%20the%20count%20function%20*%2F%0A%20%20%20%20printf(%22count%20of%20nodes%20is%20%25d%22%2C%20getCount(head))%3B%0A%20%20%20%20return%200%3B%0A%7D” message=”” highlight=”” provider=”manual”/] [ad type=”banner”]

Output:

count of nodes is 5

Categorized in:

C ProgrammingCodingLinked ListSingly Linked List

Tagged in:

, , , , , , , , , , , ,