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.
Python
# A complete working Python program to # find the length of a Linked List# iteratively# Node classclass Node: # Function to initialize the node object def __init__(self, data): # Assign data self.data = data # Initialize next as null self.next = None# Linked List class contains a Node objectclass 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 the new Node self.head = new_node # This function counts number of nodes in # Linked List iteratively, given 'node' # as starting node. def getCount(self): # Initialise temp temp = self.head 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 hereif __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()) |
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.
Python
# A complete working Python program to # find the length of a Linked List # recursively# Node classclass Node: # Function to initialize the node object def __init__(self, data): # Assign data self.data = data # Initialize next as null self.next = None # Linked List class contains a Node objectclass 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 the 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): # Base case if (not node): return 0 else: return 1 + self.getCountRec(node.next) # A wrapper over getCountRec() def getCount(self): return self.getCountRec(self.head)# Code execution starts hereif __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()) |
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.
Approach: Linear Traversal Method
- Define a Node class with two attributes: data to store the value of the node, and next to store a reference to the next node in the list.
- Define a LinkedList class with a single attribute: head to store a reference to the first node in the list.
- Define an append method in the LinkedList class to add a new node to the end of the list.
- Define a length method in the LinkedList class to find the length of the list.
- Initialize a count variable to 0 and a current_node variable to the head of the list.
- Enter a while loop that continues until current_node is None.
- Increment the count variable by 1 on each iteration of the loop.
- Update current_node to be the next node in the list on each iteration of the loop.
- Return the value of the count variable as the length of the list.
Python3
class Node: def __init__(self, data): self.data = data self.next = None class LinkedList: def __init__(self): self.head = None def append(self, data): new_node = Node(data) if self.head is None: self.head = new_node return current_node = self.head while current_node.next: current_node = current_node.next current_node.next = new_node def length(self): count = 0 current_node = self.head while current_node: count += 1 current_node = current_node.next return countlinked_list = LinkedList()linked_list.append(1)linked_list.append(2)linked_list.append(3)linked_list.append(4)linked_list.append(5)print(linked_list.length()) # Output: 5 |
Output
5
The time complexity of the approach used in the program is O(n),
The auxiliary space used by the program is O(1).
Approach Name: Hash Table Method
Steps:
- Define a linked list class with a head pointer that points to the first node of the linked list.
- Create an empty hash table to store visited nodes.
- Traverse the linked list using the head pointer.
- For each node, check if it is already present in the hash table. If it is, stop traversing.
- If the node is not in the hash table, add it to the hash table and move to the next node.
- Return the size of the hash table as the length of the linked list.
Python3
# Python program for the above approach# Linked List Node Classclass Node: def __init__(self, data=None): self.data = data self.next = None# Linked List Classclass LinkedList: def __init__(self): self.head = None # Function to insert into Linked List def insert(self, data): new_node = Node(data) if self.head is None: self.head = new_node else: current_node = self.head while current_node.next: current_node = current_node.next current_node.next = new_node # Function to find the length of # the Linked List def length(self): visited_nodes = {} current_node = self.head while current_node: if current_node in visited_nodes: break visited_nodes[current_node] = True current_node = current_node.next return len(visited_nodes)# Driver Codelinked_list = LinkedList()linked_list.insert(1)linked_list.insert(2)linked_list.insert(3)# Function Callprint(linked_list.length()) |
Output
3
Time Complexity: O(n), where n is the length of the linked list, due to the traversal of the linked list.
Auxiliary Space: O(n), due to the hash table used to store visited nodes.
Please refer complete article on Find Length of a Linked List (Iterative and Recursive) for more details!
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
