Programa Java para buscar un elemento en una lista enlazada

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.

// Iterative Java program to search
// an element in linked list
 
//Node class
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 the front
    // of the list
    public void push(int new_data)
    {
        //Allocate new node and putting data
        Node 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
    public boolean search(Node head, int x)
    {
        // Initialize current
        Node current = head;   
        while (current != null)
        {
            // Data found
            if (current.data == x)
                return true;   
            current = current.next;
        }
     
        // Data not found
        return false;   
    }
 
    // Driver code
    public static void main(String args[])
    {
        // Start with the empty list
        LinkedList llist = new LinkedList();
 
        // Use push() to construct list
        // 14->21->11->30->10
        llist.push(10);
        llist.push(30);
        llist.push(11);
        llist.push(21);
        llist.push(14);
 
        if (llist.search(llist.head, 21))
            System.out.println("Yes");
        else
            System.out.println("No");
    }
}
// This code is contributed by Pratik Agarwal

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.

// Recursive Java program to search an element
// in linked list
 
// Node class
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 the
    // front of the list
    public void push(int new_data)
    {
        // Allocate new node and putting data
        Node 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
    public boolean search(Node head, int 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
    public static void main(String args[])
    {
        // Start with the empty list
        LinkedList llist = new LinkedList();
 
        // Use push() to construct list
        // 14->21->11->30->10
        llist.push(10);
        llist.push(30);
        llist.push(11);
        llist.push(21);
        llist.push(14);
 
        if (llist.search(llist.head, 21))
            System.out.println("Yes");
        else
            System.out.println("No");
    }
}
// This code is contributed by Pratik Agarwal

Producción:

Yes

Complejidad de tiempo: O(n), donde n representa la longitud de la lista enlazada dada.
Espacio auxiliar: O(n), para pila de llamadas recursivas 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.