Ma méthode de recursion find (T data) redimensionne ma LinkedList. Comment est-ce que j'arrête ça?

Question

J'ai besoin de faire des méthodes pour une LinkedList qui utilise la récursivité. J'ai d'autres qui sont bons, mais c'est l'un de ceux qui me donne du mal:

public boolean find(T data){  
    if(head == null) 
     return false; 
    else{ 
     if(head.data == data) 
      return true; 
     else{ 
      head = head.next; 
      return find(data); 
     } 
    } 
} 

Il est censé trouver un élément dans le LinkedList mais le problème est, la liste ne doit pas être ajoutée, ce qui évidemment le mien est avec la position de tête augmentant. Le prototype est censé avoir 1 paramètre, celui des données. Comment puis-je l'empêcher d'augmenter la position de la tête?

Answer 1

Vous devez conserver une référence distincte au nœud actuel; n'utilisez pas head. Je le ferais en utilisant une méthode d'aide.

public boolean find(T data){  
    return find(data, head); 
} 

private boolean find(T data, Node current) { 
    if (current == null) return false; 
    if (current.data.equals(data)) return true; 
    current = current.next; 
    return find(data, current); 
} 

Notez l'utilisation de .equals() au lieu de == lorsque l'on compare les valeurs data. J'ai supposé que head est de classe Node. Si ce n'est pas la bonne estimation, remplissez la classe réelle dans votre implémentation.

Answer 2

À moins que vos exigences ne soient rigides dans l'utilisation de la récursivité, je vous suggère d'utiliser l'itération pour parcourir une liste. La récursivité est inefficace car elle crée une pile de fonctions inutile.

La récursion est utile pour simplifier le code pour les traversées non linéaires ou la structure de données.

Le code pour l'utilisation de l'itération serait le suivant.

public boolean find(T data) { 

    boolean found = false; 
    T current = head; 

    while(current != null) { 

     if(current.data.equals(data)) { 

      found = true; 
      break; 
     } 

     current = current.next; 
    } 

    return found; 
}