Insertion dans une liste triée de manière récursive

Question

J'ai besoin d'écrire une méthode qui insère des éléments dans une liste triée liée de manière récursive. La classe de noeud pour la liste ressemble à ceci:

protected class Node<T> { 

    protected Node(T data) { 
     this.data = data; 
    } 

    protected T data; 
    protected Node<T> next; 
} 

protected Node<E> head; 

}

La signature de la méthode est: void insert (données E). Je peux le faire de manière itérative, mais je n'arrive pas à comprendre comment le faire récursivement. Quelqu'un peut-il donner une idée?

Answer 1

En supposant que vous êtes censé être inséré à la fin de la liste, il suffit de répéter this.next jusqu'à ce que this.next soit null.

public void insert(E data) { 
    if (this.next == null) { 
     // we're at the end, so actually do the insert 
     // if you can do it iteratively, you should already know what to do here 
    } else { 
     this.next.insert(data); 
    } 
} 

Answer 2

Créez une fonction qui prend un noeud de départ et les données à insérer.

Si ce nœud est le bon endroit pour mettre les données, il suffit de l'insérer. Si ce n'est pas le cas, appelez la fonction récursivement pour essayer le nœud suivant.