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:
# A complete working Python program to find length of a
# Linked List iteratively
# Node class
class Node:
# Function to initialise the node object
def __init__(self, data):
self.data = data # Assign data
self.next = None # Initialize next as null
# Linked List class contains a Node object
class LinkedList:
# Function to initialize head
def __init__(self):
self.head = None
# This function is in LinkedList class. It inserts
# a new node at the beginning of Linked List.
def push(self, new_data):
# 1 & 2: Allocate the Node &
# Put in the data
new_node = Node(new_data)
# 3. Make next of new Node as head
new_node.next = self.head
# 4. Move the head to point to new Node
self.head = new_node
# This function counts number of nodes in Linked List
# iteratively, given 'node' as starting node.
def getCount(self):
temp = self.head # Initialise temp
count = 0 # Initialise count
# Loop while end of linked list is not reached
while (temp):
count += 1
temp = temp.next
return count
# Code execution starts here
if __name__=='__main__':
llist = LinkedList()
llist.push(1)
llist.push(3)
llist.push(1)
llist.push(2)
llist.push(1)
print 'Count of nodes is :',llist.getCount()
[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:
# A complete working Python program to find length of a
# Linked List recursively
# Node class
class Node:
# Function to initialise the node object
def __init__(self, data):
self.data = data # Assign data
self.next = None # Initialize next as null
# Linked List class contains a Node object
class LinkedList:
# Function to initialize head
def __init__(self):
self.head = None
# This function is in LinkedList class. It inserts
# a new node at the beginning of Linked List.
def push(self, new_data):
# 1 & 2: Allocate the Node &
# Put in the data
new_node = Node(new_data)
# 3. Make next of new Node as head
new_node.next = self.head
# 4. Move the head to point to new Node
self.head = new_node
# This function counts number of nodes in Linked List
# recursively, given 'node' as starting node.
def getCountRec(self, node):
if (not node): # Base case
return 0
else:
return 1 + self.getCountRec(node.next)
# A wrapper over getCountRec()
def getCount(self):
return self.getCountRec(self.head)
# Code execution starts here
if __name__=='__main__':
llist = LinkedList()
llist.push(1)
llist.push(3)
llist.push(1)
llist.push(2)
llist.push(1)
print 'Count of nodes is :',llist.getCount()
[ad type=”banner”]
Output:
count of nodes is 5
