Comment ajouter un élément à une liste liée en Java?

Question

En utilisant un comparateur et un itérateur, j'essaie d'ajouter des objets dans une liste chaînée dans l'ordre. Jusqu'à présent, je donne les résultats suivants:

public class ComparatorClass implements Comparator<Integer> { 
    public int compare(Integer int1, Integer int2) { 
     return int1.compareTo(int2); 
    } 
} 

et:

import java.util.ArrayList; 
import java.util.Comparator; 
import java.util.Iterator; 

public class OrderedListInheritance implements LinkedList { 

    ArrayList<Object> myList = new ArrayList<Object>(); 

    Comparator comp = new ComparatorClass(); 

    OrderedListInheritance(Comparator c) { 
     this.comp = c; 
    } 

    @Override 
    public void add(Object o) { 
     addLast(o); 
    } 

    @Override 
    public void addAtIndex(int index, Object o) { 
     Iterator it = getIterator(); 
     while (it.hasNext()) { 
      Object element = it.next(); 
      if (comp.compare(element, o) < 0) { 

     }else if (comp.compare(element, o) == 0) { 

     }else{ 
      myList.add(o); 
     } 
     } 
    } 

    @Override 
    public void addFirst(Object o) { 
     addAtIndex(0, o); 
    } 

    @Override 
    public void addLast(Object o) { 
     addAtIndex(myList.size(), o); 
    } 

    @Override 
    public Object get(int index) { 
     return myList.get(index); 
    } 

    @Override 
    public Iterator getIterator() { 
     Iterator iter = myList.iterator(); 
     return iter; 
    } 

    @Override 
    public int indexOf(Object o) { 
     return myList.indexOf(o); 
    } 

} 

Je ne suis pas sûr comment utiliser le Iterator conjointement avec le comparateur pour ajouter chaque élément à la liste chaînée dans l'ordre. Quelqu'un peut-il m'aider avec la logique?

Answer 1

Votre comparateur est erroné.

Une partie du contrat général pour un comparateur est que si compare(a, b) est positif, compare(b, a) est négatif.

Si vous passez un comparateur qui ne remplit pas le contrat comparateur, vous allez obtenir un comportement indéfini.

Answer 2

Y a-t-il une raison pour laquelle vous ne pouvez pas simplement utiliser un ArrayList normal et ensuite appeler Collections.sort(list) ou Collections.sort(list, comparator)?

Answer 3

Je voudrais écrire comme ceci:

public class IntegerComparator 
    implements Comparator<Integer> 
{ 
    public int compare(final Integer a, final Integer b) 
    { 
     return (a.compareTo(b)); 
    } 
} 

je vais commenter plus sur le code ... mais ce que vous avez donné ne fonctionnera pas ... vous déclarez un ArrayList mais que vous voulez alors utilisez un comparateur et vous ne lancez pas ... donc cela ne compilera pas.

L'autre problème est que vous ne devriez pas utiliser == 1 vous devriez utiliser < 0 et> 0 puisque le comparateur ne peut pas retourner 1, 0, -1 mais aussi d'autres nombres. De plus, vous ne gérez pas tous les cas < b, a == b et a> b.

Answer 4

Faisons nous vos devoirs? Votre problème ne semble pas être lié à l'interface du comparateur mais à une compréhension claire de ce que vous voulez qu'il fasse. Cela me semble être un endroit parfait pour préconiser un style de développement axé sur les tests. Commencer par écrire des tests à insérer dans une liste vide, insérer dans la tête d'une liste, insérer dans la queue, insérer au milieu d'une liste de longueur 2. Puis écrire des tests pour retourner le nième élément et l'élément avec un valeur donnée. Après avoir travaillé sur ces cas simples, il sera facile de trouver l'élément dans une liste ordonnée qui est la première plus grande que l'élément à insérer et ajouter l'élément devant le plus grand. Ne pas oublier les cas de bord d'ajouter une valeur en double, une valeur plus petite que tout dans la liste et une valeur plus grande que tout dans la liste.

Answer 5

Si vous implémentez la méthode add pour insérer l'élément dans l'ordre trié (ou n'importe où sauf la fin de la liste), vous enfreignez le contrat de l'interface List. Sémantiquement, ce n'est pas un List, et il n'est pas sûr de le passer à un code qui en attend un. Faire semblant d'implémenter l'interface List ne fera que créer des problèmes.

Comment utiliser un TreeSet? au lieu?

Set<Integer> list = new TreeSet<Integer>(); 

Bien sûr, un Set ne permettra pas les doublons.

Si vous voulez quelque chose qui autorise les doublons, mais permet toujours efficace, en ordre de récupération, essayez une collection dans le tas, comme PriorityQueue.