Programa de Python para encontrar la longitud de una lista vinculada

Escriba una función para contar el número de Nodes en una lista enlazada simple dada.

Por ejemplo, la función debería devolver 5 para la lista enlazada 1->3->1->2->1.

Solución iterativa:

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 

A continuación se muestra la implementación iterativa del algoritmo anterior para encontrar el recuento de Nodes en una lista de enlaces individuales dada.

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

Producción: 

count of nodes is 5

Complejidad de tiempo: O(n), donde n representa la longitud de la lista enlazada dada.
Espacio auxiliar: O(1), no se requiere espacio adicional, por lo que es una constante.

Solución recursiva:

int getCount(head)
1) If head is NULL, return 0.
2) Else return 1 + getCount(head->next)

A continuación se muestra la implementación recursiva del algoritmo anterior para encontrar el recuento de Nodes en una lista de enlaces simples dada.

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

Producción: 

Count of nodes is 5

Complejidad de tiempo: O(n), donde n representa la longitud de la lista enlazada dada.
Espacio auxiliar: O(n), para pila recursiva donde n representa la longitud de la lista enlazada dada.

¡ Consulte el artículo completo sobre Buscar la longitud de una lista vinculada (iterativa y recursiva) para obtener más detalles!