Programa de Python 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.

# Iterative Python program to search
# an element in linked list
 
# Node class
class Node:
     
    # Function to initialise the
    # node object
    def __init__(self, data):
     
        # Assign data
        self.data = data
 
        # Initialize next as null
        self.next = None
 
# Linked List class
class LinkedList:
    def __init__(self):
 
        # Initialize head as None
        self.head = None
 
    # This function insert a new node at the
    # beginning of the linked list
    def push(self, new_data):
     
        # Create a new Node
        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 new Node
        self.head = new_node
 
    # This Function checks whether the value
    # x present in the linked list
    def search(self, x):
 
        # Initialize current to head
        current = self.head
 
        # Loop till current not equal to None
        while current != None:
            if current.data == x:
 
                # Data found
                return True
             
            current = current.next
         
        # Data Not found
        return False
 
# Driver code
if __name__ == '__main__':
 
    # Start with the empty list
    llist = 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(21):
        print("Yes")
    else:
        print("No")
# This code is contributed by Ravi Shankar

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 Python program to
# search an element in linked list
 
# 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
 
class LinkedList:
     
    def __init__(self):
 
        # Initialize head as None
        self.head = None
 
    # This function insert a new node at
    # the beginning of the linked list
    def push(self, new_data):
     
        # Create a new Node
        new_node = Node(new_data)
 
        # Make next of new Node as head
        new_node.next = self.head
 
        # Move the head to
        # point to new Node
        self.head = new_node
     
     
    # Checks whether the value key
    # is present in linked list
    def search(self, li, key):
         
        # Base case
        if(not li):
            return False
         
        # If key is present in
        # current node, return true
        if(li.data == key):
            return True
         
        # Recur for remaining list
        return self.search(li.next, key)
     
# Driver Code           
if __name__=='__main__':
 
    li = LinkedList()
     
    li.push(1)
    li.push(2)
    li.push(3)
    li.push(4)
     
    key = 4
     
    if li.search(li.head,key):
        print("Yes")
    else:
        print("No")
# This code is contributed by Manoj Sharma

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.