Programa Java para encontrar la longitud de una lista enlazada

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.

// Java program to count number of
// nodes in a linked list
 
// Linked list Node
class Node
{
    int data;
    Node next;
    Node(int d)  { data = d;  next = null; }
}
 
// Linked List class
class LinkedList
{
    // Head of list
    Node head; 
 
    // Inserts a new Node at front
    // of the list.
    public void push(int new_data)
    {
        /* 1 & 2: Allocate the Node &
                  Put in the data*/
        Node new_node = new Node(new_data);
 
        // 3. Make next of new Node as head
        new_node.next = head;
 
        // 4. Move the head to point to new Node
        head = new_node;
    }
 
    // Returns count of nodes in linked list
    public int getCount()
    {
        Node temp = head;
        int count = 0;
        while (temp != null)
        {
            count++;
            temp = temp.next;
        }
        return count;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        // Start with the empty list
        LinkedList llist = new LinkedList();
        llist.push(1);
        llist.push(3);
        llist.push(1);
        llist.push(2);
        llist.push(1);
 
        System.out.println("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. 

// Recursive Java program to count number
// of nodes in a linked list
 
// Linked list Node
class Node
{
    int data;
    Node next;
    Node(int d) 
    { 
        data = d; 
        next = null;
    }
}
 
// Linked List class
class LinkedList
{
     
    Node head; 
 
    // Inserts a new Node at front of
    // the list.
    public void push(int new_data)
    {
        /* 1 & 2: Allocate the Node &
                  Put in the data*/
        Node new_node = new Node(new_data);
 
        // 3. Make next of new Node as head
        new_node.next = head;
 
        // 4. Move the head to point to new Node
        head = new_node;
    }
 
    // Returns count of nodes in linked list
    public int getCountRec(Node node)
    {
        // Base case
        if (node == null)
            return 0;
 
        // Count is this node plus rest
        // of the list
        return 1 + getCountRec(node.next);
    }
 
    // Wrapper over getCountRec()
    public int getCount()
    {
        return getCountRec(head);
    }
 
    // Driver code
    public static void main(String[] args)
    {
        // Start with the empty list
        LinkedList llist = new LinkedList();
        llist.push(1);
        llist.push(3);
        llist.push(1);
        llist.push(2);
        llist.push(1);
 
        System.out.println("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!