Programa Javascript 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 simples dada.

<script>
// Javascript program to count number
// of nodes in a linked list
 
// Linked list Node
class Node
{
    constructor(val)
    {
        this.data = val;
        this.next = null;
    }
}
 
// Head of list
var head;
 
// Inserts a new Node at front of the list.
function push(new_data)
{
    // 1 & 2: Allocate the Node & Put in
    // the data
    var 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
function getCount()
{
    var temp = head;
    var count = 0;
    while (temp != null)
    {
        count++;
        temp = temp.next;
    }
    return count;
}
 
// Driver code
// Start with the empty list
push(1);
push(3);
push(1);
push(2);
push(1);
 
document.write("Count of nodes is " + getCount());
 
// This code contributed by Rajput-Ji
</script>

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.

<script>
// Recursive javascript program to count
// number of nodes in a linked list
 
// Linked list Node
class Node
{
    constructor(val)
    {
        this.data = val;
        this.next = null;
    }
}
 
// Linked List class
// Head of list
var head;
 
// Inserts a new Node at front of the list.
function push( new_data)
{
    // 1 & 2: Allocate the Node &
    // Put in the data
    var 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
function getCountRec(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()
function getCount()
{
    return getCountRec(head);
}
 
// Driver code
// Start with the empty list   
push(1);
push(3);
push(1);
push(2);
push(1);
 
document.write("Count of nodes is " + getCount());
 
// This code contributed by gauravrajput1
</script>

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!