Insertion d'un nouvel objet dans Linkedlist (de Strings) dans l'ordre alphabétique sans tri

Question

Je me demande si cela est possible en Java. Je veux l'insérer dans le bon endroit par ordre alphabétique. Par exemple est les éléments du LinkedList (disons qu'il est appelé coollist) étaient les suivants: [Dusty, Gordon, Mayer, Popovic, Zacharie] et je tente d'insérer une autre chaîne en faisant:

coollist.add(d,Nyugen); //d is a a variable representing ant int which is the index 

Que puis-je faire faire d la valeur qui va l'insérer dans l'ordre alphabétique, indépendamment de ce qui est dans LinkedList? Pouvez-vous m'aider? J'espère que cela a du sens.

Answer 1

Voici une façon de trouver l'index trié dans LinkedList.

import java.util.*; 

public class SortedLinkedListDemo { 

public static void main (String [] args) { 
    List<String> list = new LinkedList<String>(); 
    list.add ("Dusty"); 
    list.add ("Gordon"); 
    list.add ("Mayer"); 
    list.add ("Popovic"); 
    list.add ("Zechariah"); 

    list.add (getSortedIndex ("Nyugen", list), "Nyugen"); 

    System.out.println ("List: "+list); 
} 

private static int getSortedIndex (String name, List<String> list) { 
    for (int i=0; i < list.size(); i++) { 
     if (name.compareTo(list.get(i)) < 0) { 
      return i; 
     } 
    }  
    // name should be inserted at end. 
    return list.size(); 
} 

}

Cela donnera la sortie suivante:

Liste: [Dusty, Gordon, Mayer, Nyugen, Popovic, Zacharie]

Answer 2

La recherche dans une liste chaînée nécessite O (n). Mais puisque vos données sont triées, mettre la chaîne suivante en place est une question de trouver le bon emplacement. Dans une autre structure de données soutenue par un tableau, ceci est fait par une recherche binaire et prend O (log n). Voir le lien de leder dans les commentaires. Bien sûr, vous pouvez toujours parcourir la liste vous-même et insérer la chaîne, mais ce n'est pas ce que la liste chaînée est la meilleure.

Answer 3

Vous pouvez parcourir la liste en recherchant lorsque l'index produit une chaîne supérieure à l'argument. Ensuite, insérez juste derrière cet index. S'il s'agit d'une liste unidirectionnelle liée, vous devez garder une trace du nœud précédent afin de pouvoir mettre à jour ses champs.

Node newNode = new Node(stringToBeAdded); //Create new node 

    if (this.head == null){ //list is empty, just insert 
     this.head = newNode; //Initialize head 
    } 

    else{ 

     Node cur = this.head; //Start at the beginning of the list 
     Node prev = this.head; //just initialize the previous node to something 

     //keep going until found or at end of list 
     while((stringToBeAdded < cur.data) && (cur != null)){ 
     prev = cur; 
     cur = cur.next; 
     } 

     prev.next = newNode; 

     if (cur != null){ //if we did not reach the end 
     newNode.next = cur; //current Node is alphabetically greater 
     } 
    }