Python Program For Finding Length Of A Linked List

0 0 5 minutes read

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 class
class 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 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 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 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())

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 class
class 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 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 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 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())

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 count
linked_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

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 Class
class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None
 
# Linked List Class
class 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 Code
linked_list = LinkedList()
 
linked_list.insert(1)
linked_list.insert(2)
linked_list.insert(3)
 
# Function Call
print(linked_list.length())

Output

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 zambiatek!