{"id":26868,"date":"2017-12-26T20:41:26","date_gmt":"2017-12-26T15:11:26","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26868"},"modified":"2018-10-30T16:17:30","modified_gmt":"2018-10-30T10:47:30","slug":"python-algorithm-find-length-linked-list-iterative-recursive","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/python-algorithm-find-length-linked-list-iterative-recursive\/","title":{"rendered":"Find Length of a Linked List both Iterative and Recursive"},"content":{"rendered":"

Find Length of a Linked List both Iterative and Recursive:<\/span><\/h3>\n

Write a Python function<\/a> to count number of nodes in a given singly linked list.<\/p>\n

\"C<\/p>\n

For example, the function should return 5 for linked list 1->3->1->2->1.<\/p>\n

Singly Linked List:<\/span><\/h3>\n

Singly Linked List is a collection of ordered set of elements<\/strong>. A Node in singly linked list has two parts \u2013 data part and link part<\/strong>. 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.<\/p>\n

It can be traversed in only one direction because the node stores only next pointer. So, it can\u2019t\u00a0reverse linked list.<\/a><\/p>\n

Iterative Solution<\/strong><\/span><\/h3>\n
1) Initialize count as 0 \r\n2) Initialize a node pointer, current = head.\r\n3) Do following while current is not NULL\r\n     a) current = current -> next\r\n     b) count++;\r\n4) Return count<\/pre>\n
Python Programming:<\/strong><\/span><\/h3>\n[pastacode lang=\u201dpython\u201d manual=\u201d%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\u2019node\u2019%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\u2019__main__\u2019%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\u2019Count%20of%20nodes%20is%20%3A\u2019%2Cllist.getCount()%0A\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n[ad type=\u201dbanner\u201d]\n
Output:<\/strong><\/span><\/h3>\n
count of nodes is 5<\/pre>\n
Recursive Solution<\/strong><\/span><\/h3>\n
int getCount(head)<\/strong>\r\n1) If head is NULL, return 0.\r\n2) Else return 1 + getCount(head->next)<\/pre>\n
Python Programming:<\/strong><\/span><\/h3>\n[pastacode lang=\u201dpython\u201d manual=\u201d%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\u2019node\u2019%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\u2019__main__\u2019%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\u2019Count%20of%20nodes%20is%20%3A\u2019%2Cllist.getCount()%0A\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n[ad type=\u201dbanner\u201d]\n
Output:<\/strong><\/span><\/h3>\n
count of nodes is 5<\/pre>\n","protected":false},"excerpt":{"rendered":"
Python Algorithm – Find Length of a Linked List both Iterative and Recursive – Linked List – Write a C function to count number of nodes in a given singly<\/p>\n","protected":false},"author":1,"featured_media":31259,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[79476,4148,79478],"tags":[72483,80240,80236,80239,80231,80237,80241,80232,80238,80235,80234,80230,80233],"class_list":["post-26868","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-linked-list","category-python","category-singly-linked-list","tag-c-linked-list","tag-find-length-of-linked-list-java","tag-geeksforgeeks","tag-get-length-of-linked-list-python","tag-how-to-calculate-the-length-of-linked-list-without-using-counter-in-java","tag-how-to-find-the-length-of-a-linked-list-python","tag-length-of-linked-list-c","tag-length-of-linked-list-python","tag-linked-list-implementation-in-python","tag-linkedlist-java","tag-recursive-linked-list-java","tag-size-of-linked-list-c","tag-what-is-a-class-loader-what-does-it-do"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26868","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=26868"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26868\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media\/31259"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26868"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26868"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26868"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}