Una lista concatenata è uno dei tipi primari di strutture di dati nel mondo della programmazione. È una disposizione di nodi che contiene sia dati e riferimenti che punta al nodo successivo. Per ordinare una lista concatenata in Java, c'è una classe di elenco collegato che funziona con il framework di insiemi che implementa gli algoritmi come l'ordinamento.

Istruzioni

Ordinare una lista concatenata in Java

1

Dichiarare l'elenco collegato creando un nuovo oggetto LinkedList e assegnarlo a una variabile di oggetto LinkedList. LinkedList eredita dalla classe List generica, pertanto qualsiasi metodo che accetta un elenco accetterà anche un oggetto LinkedList.
""LinkedList l = new LinkedList();""

2

Aggiungere all'elenco oggetti dello stesso tipo (ad esempio numeri interi). Questi possono essere oggetti di qualsiasi tipo, ma al fine di ordinare un elenco collegato, dovrebbero essere di tutti dello stesso tipo.

3

Utilizzare il metodo List.addFirst per inserire nuovi oggetti all'inizio dell'elenco, cosicché qualunque oggetti aggiunti sarà in ordine inverso. Se si desidera aggiungerli alla fine dell'elenco, utilizzare il metodo List.addLast.""list.addFirst(1);
list.addFirst(3);
list.addFirst(2);""

4

Utilizzare un iteratore per scorrere l'elenco e stamparle prima e dopo per vedere che cosa fa il metodo sort.""for( Iterator i = list.iterator(); i.hasNext(); ) {
System.out.println(i.next());
}""

Ordinamento con comparatori personalizzati e predefiniti

5

Ordinare l'elenco con il comparatore di predefinito. Un comparatore è un oggetto che confronta due oggetti. Oggetto di confronto predefinito utilizza l'operatore, less than quindi l'elenco verrà ordinato in ordine crescente. Per ordinare l'elenco, utilizzare il metodo statico di metodo.""Collections.sort(list);""

6

Ordinare l'elenco con un criterio di confronto personalizzato scrivendo una classe che implementa l'interfaccia comparator e passa un'istanza come argomento per ordinare. La classe che implementa il comparatore ha solo implementare il metodo singolo "Confronta".""public class GreaterThan implements Comparator {@Override
public int compare(Object arg0, Object arg1) {
int x = (Integer)arg0;
int y = (Integer)arg1;
if(x > y) {
return -1;
} else if(x == y) {
return 0;
} else {
return 1;
}
}}""

7

Utilizzare la chiamata al metodo passando una nuova istanza di GreaterThan come secondo argomento. Poiché gli oggetti che sono maggiori verranno ordinati in primo luogo, l'elenco verrà ordinato in ordine invece di ordine crescente decrescente. In alternativa, se si sta ordinando un elenco di oggetti di una classe personalizzata che hai scritto te stesso, che la classe può implementare l'interfaccia Comparable invece di utilizzare una classe separata di comparatore.""Collections.sort(list, new GreaterThan());""

Consigli & Avvertenze

• È problematico per utilizzare un valore integer per l'iterazione per ciclo e il metodo di List.size(). Lo scorrimento di un elenco collegato è un'operazione dispendiosa. Quando si utilizza l'operatore di indice (come l[2]) come si farebbe con una matrice, Java deve scorrere l'elenco fino a quando si arriva a indice 2. Per elenchi di piccole dimensioni, questo non è un problema, ma con qualcosa di più grande, utilizzando l'operatore di indice per scorrere diventa risorsa-molto costoso.
• Non importa come è implementato l'oggetto elenco, poiché LinkedList implementa la stessa interfaccia.
• Il metodo compare deve restituire -1 se arg0 devono essere ordinati prima di arg1, 0 se dovrebbe essere ordinato ugualmente e 1 se arg1 devono essere ordinati prima di arg0.
• L'oggetto iteratore assicura che ogni nodo nell'elenco è visitato solo una volta. Si tratta di una cosa importante da ricordare, come nodi visiti inutilmente possono abusare di strutture di dati al punto che a malapena si eseguirà il programma.