Programa Javascript para buscar un elemento en una lista vinculada

Escriba una función que busque una clave ‘x’ dada en una lista dada de enlaces simples. La función debe devolver verdadero si x está presente en la lista enlazada y falso en caso contrario.

bool search(Node *head, int x) 

Por ejemplo, si la clave a buscar es 15 y la lista enlazada es 14->21->11->30->10, entonces la función debería devolver falso. Si la clave a buscar es 14, entonces la función debería devolver verdadero.
Solución iterativa: 

1) Initialize a node pointer, current = head.
2) Do following while current is not NULL
    a) current->key is equal to the key being searched return true.
    b) current = current->next
3) Return false 

A continuación se muestra la implementación iterativa del algoritmo anterior para buscar una clave determinada.

<script>
// Iterative javascript program
// to search an element
// in linked list
 
//Node class
class Node
{
    constructor(d)
    {
        this.data = d;
        this.next = null;
    }
}
 
// Linked list class
 
// Head of list
var head;
 
// Inserts a new node at the front of the list
function push(new_data)
{
    // Allocate new node and putting data
    var new_node = new Node(new_data);
 
    // Make next of new node as head
    new_node.next = head;
 
    // Move the head to point to new Node
    head = new_node;
}
 
// Checks whether the value
// x is present in linked list
function search(head , x)
{
    // Initialize current
    var current = head;
         
    while (current != null)
    {
        if (current.data == x)
 
            // Data found
            return true;
            current = current.next;
        }
 
        // Data not found
        return false;
}
 
// Driver code
 
// Start with the empty list
// Use push() to construct list
// 14->21->11->30->10
push(10);
push(30);
push(11);
push(21);
push(14);
 
if (search(head, 21))
    document.write("Yes");
else
    document.write("No");
// This code contributed by aashish1995
</script>

Producción: 

Yes

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: 

bool search(head, x)
1) If head is NULL, return false.
2) If head's key is same as x, return true;
3) Else return search(head->next, x) 

A continuación se muestra la implementación recursiva del algoritmo anterior para buscar una clave determinada.

<script>
// Recursive javascript program to search
// an element in linked list
 
// Node class
class Node
{
    constructor(val)
    {
        this.data = val;
        this.next = null;
    }
}
  
// Linked list class
// Head of list
var head;
 
// Inserts a new node at the front
// of the list
function push(new_data)
{
    // Allocate new node and putting data
    var new_node = new Node(new_data);
 
    // Make next of new node as head
    new_node.next = head;
 
    // Move the head to point to new Node
    head = new_node;
}
 
// Checks whether the value x is present
// in linked list
function search(head, x)
{
    // Base case
    if (head == null)
        return false;
 
    // If key is present in current node,
    // return true
    if (head.data == x)
        return true;
 
    // Recur for remaining list
    return search(head.next, x);
}
 
// Driver code
     
// Start with the empty list
// Use push() to construct list
// 14->21->11->30->10
push(10);
push(30);
push(11);
push(21);
push(14);
 
if (search(head, 21))
    document.write("Yes");
        else
            document.write("No");
 
// This code contributed by gauravrajput1
</script>

Producción:  

Yes

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 un elemento en una lista vinculada (iterativa y recursiva) para obtener más detalles.