Java Language
elenchi

introduzione

Sintassi

• ls.add (elemento E); // Aggiunge un elemento
• ls.remove (elemento E); // Rimuove un elemento
• for (E element: ls) {} // Iterates su ogni elemento
• ls.toArray (new String [ls.length]); // Converte un elenco di stringhe in un array di stringhe
• ls.get (int index); // Restituisce l'elemento nell'indice specificato.
• ls.set (indice int, elemento E); // Sostituisce l'elemento in una posizione specificata.
• ls.isEmpty (); // Restituisce true se la matrice non contiene elementi, altrimenti restituisce false.
• ls.indexOf (Object o); // Restituisce l'indice della prima posizione dell'elemento specificato o, o, se non è presente, restituisce -1.
• ls.lastIndexOf (Object o); // Restituisce l'indice dell'ultima posizione dell'elemento specificato o, oppure, se non è presente, restituisce -1.
• ls.size (); // Restituisce il numero di elementi nella lista.

Osservazioni

List<String> list = new ArrayList<>();
list.add("world");
System.out.println(list.indexOf("world"));      // Prints "0"
// Inserting a new value at index 0 moves "world" to index 1
list.add(0, "Hello");
System.out.println(list.indexOf("world"));      // Prints "1"
System.out.println(list.indexOf("Hello"));      // Prints "0"

Ordinamento di un elenco generico

La classe Collections offre due metodi statici standard per ordinare un elenco:

• sort(List<T> list) applicabile agli elenchi in cui T extends Comparable<? super T> , e
• sort(List<T> list, Comparator<? super T> c) applicabile a liste di qualsiasi tipo.

L'applicazione del primo richiede la modifica della classe di elementi di elenco ordinati, il che non è sempre possibile. Potrebbe anche non essere desiderabile poiché, sebbene fornisca l'ordinamento predefinito, altri ordini di ordinamento potrebbero essere richiesti in circostanze diverse, o l'ordinamento è solo un'attività a parte.

Considera che abbiamo un'attività di ordinare oggetti che sono istanze della seguente classe:

public class User {
    public final Long id;
    public final String username;

    public User(Long id, String username) {
        this.id = id;
        this.username = username;
    }

    @Override
    public String toString() {
        return String.format("%s:%d", username, id);
    }
}

Per utilizzare Collections.sort(List<User> list) è necessario modificare la classe User per implementare l'interfaccia Comparable . Per esempio

public class User implements Comparable<User> {
    public final Long id;
    public final String username;

    public User(Long id, String username) {
        this.id = id;
        this.username = username;
    }

    @Override
    public String toString() {
        return String.format("%s:%d", username, id);
    }

    @Override
    /** The natural ordering for 'User' objects is by the 'id' field. */
    public int compareTo(User o) {
        return id.compareTo(o.id);
    }
}

(A parte: molte classi Java standard come String , Long , Integer implementano l'interfaccia Comparable rende gli elenchi di quegli elementi ordinabili per impostazione predefinita e semplifica l'implementazione di compare o compareTo in altre classi.)

Con la modifica sopra, possiamo facilmente ordinare un elenco di oggetti User base all'ordine naturale delle classi. (In questo caso, abbiamo definito che essere ordinati in base ai valori id ). Per esempio:

List<User> users = Lists.newArrayList(
    new User(33L, "A"),
    new User(25L, "B"),
    new User(28L, ""));
Collections.sort(users);

System.out.print(users);
// [B:25, C:28, A:33]

Tuttavia, supponiamo di voler ordinare gli oggetti User per name anziché per id . In alternativa, supponiamo di non essere stato in grado di modificare la classe per renderla Comparable .

È qui che il metodo di sort con l'argomento Comparator è utile:

Collections.sort(users, new Comparator<User>() {
    @Override
    /* Order two 'User' objects based on their names. */
    public int compare(User left, User right) {
        return left.username.compareTo(right.username);
    }
});
System.out.print(users);
// [A:33, B:25, C:28]

Collections.sort(users, (l, r) -> l.username.compareTo(r.username));

users.sort((l, r) -> l.username.compareTo(r.username))

Creare una lista

Dando alla tua lista un tipo

Per creare un elenco è necessario un tipo (qualsiasi classe, ad esempio String ). Questo è il tipo della tua List . L' List memorizzerà solo oggetti del tipo specificato. Per esempio:

List<String> strings;

Può memorizzare "string1" , "hello world!" , "goodbye" , ecc., ma non può memorizzare 9.2 , tuttavia:

List<Double> doubles;

Può memorizzare 9.2 , ma non "hello world!" .

Inizializzazione della lista

Se provate ad aggiungere qualcosa agli elenchi sopra, otterrete una NullPointerException, perché le strings e i doubles uguali sono nulli !

Esistono due modi per inizializzare un elenco:

Opzione 1: utilizza una classe che implementa List

List è un'interfaccia, il che significa che non ha un costruttore, piuttosto metodi che una classe deve sovrascrivere. ArrayList è l' List più comunemente usato, anche se LinkedList è anche comune. Quindi inizializziamo la nostra lista in questo modo:

List<String> strings = new ArrayList<String>();

o

List<String> strings = new LinkedList<String>();

List<String> strings = new ArrayList<>();

List<String> strings = new LinkedList<>();

Opzione 2: usa la classe Collections

La classe Collections fornisce due metodi utili per la creazione di elenchi senza una variabile di List :

• emptyList() : restituisce una lista vuota.
• singletonList(T) : crea una lista di tipo T e aggiunge l'elemento specificato.

E un metodo che utilizza un List esistente per riempire i dati in:

• addAll(L, T...) : aggiunge tutti gli elementi specificati all'elenco passato come primo parametro.

Esempi:

import java.util.List;
import java.util.Collections;

List<Integer> l = Collections.emptyList();
List<Integer> l1 = Collections.singletonList(42);
Collections.addAll(l1, 1, 2, 3);

Operazioni di accesso posizionale

L'API List ha otto metodi per le operazioni di accesso posizionale:

• add(T type)
• add(int index, T type)
• remove(Object o)
• remove(int index)
• get(int index)
• set(int index, E element)
• int indexOf(Object o)
• int lastIndexOf(Object o)

Quindi, se abbiamo una lista:

List<String> strings = new ArrayList<String>();

E volevamo aggiungere le stringhe "Ciao mondo!" e "Arrivederci mondo!" ad esso, lo faremmo come tale:

strings.add("Hello world!");
strings.add("Goodbye world!");

E la nostra lista conterrebbe i due elementi. Ora diciamo che volevamo aggiungere "Programma in corso!" in cima alla lista. Lo faremmo in questo modo:

strings.add(0, "Program starting!");

NOTA: il primo elemento è 0.

Ora, se volessimo rimuovere il "mondo degli addii!" linea, potremmo farlo in questo modo:

strings.remove("Goodbye world!");

E se volessimo rimuovere la prima riga (che in questo caso sarebbe "Programma in avvio!", Potremmo farlo in questo modo:

strings.remove(0);

Nota:

1. L'aggiunta e la rimozione di elementi di elenco modifica l'elenco e questo può portare a una ConcurrentModificationException se l'elenco viene iterato contemporaneamente.

2. L'aggiunta e la rimozione di elementi può essere O(1) o O(N) seconda della classe di elenco, del metodo utilizzato e dell'aggiunta / rimozione di un elemento all'inizio, alla fine o al centro dell'elenco.

Per recuperare un elemento della lista in una posizione specifica puoi usare E get(int index); metodo dell'API List. Per esempio:

strings.get(0);

restituirà il primo elemento della lista.

Puoi sostituire qualsiasi elemento in una posizione specificata usando il set(int index, E element); . Per esempio:

strings.set(0,"This is a replacement");

Questo imposterà la stringa "Questa è una sostituzione" come il primo elemento della lista.

Nota: il metodo set sovrascrive l'elemento nella posizione 0. Non aggiungerà la nuova stringa nella posizione 0 e spingerà quella precedente nella posizione 1.

L' int indexOf(Object o); restituisce la posizione della prima occorrenza dell'oggetto passato come argomento. Se non ci sono occorrenze dell'oggetto nella lista, viene restituito il valore -1. In continuazione dell'esempio precedente se si chiama:

strings.indexOf("This is a replacement")

lo 0 dovrebbe essere restituito quando impostiamo la stringa "This is a replacement" nella posizione 0 della nostra lista. Nel caso in cui ci siano più di un'occorrenza nella lista quando int indexOf(Object o); viene chiamato quindi come detto verrà restituito l'indice della prima occorrenza. Chiamando int lastIndexOf(Object o) è possibile recuperare l'indice dell'ultima occorrenza nell'elenco. Quindi se aggiungiamo un altro "Questa è una sostituzione":

strings.add("This is a replacement");
strings.lastIndexOf("This is a replacement");

Questa volta verrà restituito 1 e non lo 0;

Iterare su elementi in una lista

Per esempio, diciamo che abbiamo una lista di tipo String che contiene quattro elementi: "ciao", "come", "sono", "tu?"

Il modo migliore per scorrere su ogni elemento è utilizzare un ciclo for-each:

public void printEachElement(List<String> list){
    for(String s : list){
        System.out.println(s);
    }
}

Quale stamperebbe:

hello,
how
are
you?

Per stamparli tutti nella stessa riga, puoi usare StringBuilder:

public void printAsLine(List<String> list){
    StringBuilder builder = new StringBuilder();
    for(String s : list){
        builder.append(s);
    }
    System.out.println(builder.toString());
}

Stamperà:

hello, how are you?

In alternativa, è possibile utilizzare l'indicizzazione degli elementi (come descritto in Accedere all'elemento con l'indice ith da ArrayList ) per iterare un elenco. Attenzione: questo approccio è inefficiente per gli elenchi collegati.

Rimozione di elementi dall'elenco B presenti nell'elenco A

Supponiamo di avere 2 elenchi A e B, e tu vuoi rimuovere da B tutti gli elementi che hai in A il metodo in questo caso è

 List.removeAll(Collection c);

#Esempio:

public static void main(String[] args) {
    List<Integer> numbersA = new ArrayList<>();
    List<Integer> numbersB = new ArrayList<>();
    numbersA.addAll(Arrays.asList(new Integer[] { 1, 3, 4, 7, 5, 2 }));
    numbersB.addAll(Arrays.asList(new Integer[] { 13, 32, 533, 3, 4, 2 }));
    System.out.println("A: " + numbersA);
    System.out.println("B: " + numbersB);

    numbersB.removeAll(numbersA);
    System.out.println("B cleared: " + numbersB);
    }

questo stamperà

A: [1, 3, 4, 7, 5, 2]

B: [13, 32, 533, 3, 4, 2]

B cancellato: [13, 32, 533]

Trovare elementi comuni tra 2 elenchi

Supponiamo di avere due liste: A e B, e devi trovare gli elementi che esistono in entrambi gli elenchi.

Puoi farlo invocando semplicemente il metodo List.retainAll() .

Esempio:

public static void main(String[] args) {
    List<Integer> numbersA = new ArrayList<>();
    List<Integer> numbersB = new ArrayList<>();
    numbersA.addAll(Arrays.asList(new Integer[] { 1, 3, 4, 7, 5, 2 }));
    numbersB.addAll(Arrays.asList(new Integer[] { 13, 32, 533, 3, 4, 2 }));

    System.out.println("A: " + numbersA);
    System.out.println("B: " + numbersB);
    List<Integer> numbersC = new ArrayList<>();
    numbersC.addAll(numbersA);
    numbersC.retainAll(numbersB);

    System.out.println("List A : " + numbersA);
    System.out.println("List B : " + numbersB);
    System.out.println("Common elements between A and B: " + numbersC);

}

Convertire un elenco di numeri interi in un elenco di stringhe

List<Integer> nums = Arrays.asList(1, 2, 3);
List<String> strings = nums.stream()
    .map(Object::toString)
    .collect(Collectors.toList());

Questo è:

1. Crea un flusso dall'elenco
2. Mappare ogni elemento usando Object::toString
3. Raccogli i valori di String in un List utilizzando Collectors.toList()

Creazione, aggiunta e rimozione di elementi da un ArrayList

ArrayList è una delle strutture dati integrate in Java. È una matrice dinamica (in cui non è necessario dichiarare la dimensione della struttura dati prima) per la memorizzazione di elementi (oggetti).

Estende la classe AbstractList e implementa l'interfaccia List . Un ArrayList può contenere elementi duplicati dove mantiene l'ordine di inserimento. Va notato che la classe ArrayList non è sincronizzata, quindi è necessario prestare attenzione quando si maneggia la concorrenza con ArrayList . ArrayList consente l'accesso casuale perché l'array funziona alla base dell'indice. La manipolazione è lenta in ArrayList causa dello spostamento che si verifica spesso quando un elemento viene rimosso dall'elenco di array.

Un ArrayList può essere creato come segue:

List<T> myArrayList = new ArrayList<>();

Dove T ( Generics ) è il tipo che verrà archiviato all'interno di ArrayList .

Il tipo di ArrayList può essere qualsiasi oggetto. Il tipo non può essere un tipo primitivo (usa invece le loro classi wrapper ).

Per aggiungere un elemento a ArrayList , utilizzare il metodo add() :

myArrayList.add(element);

O per aggiungere elementi a un determinato indice:

myArrayList.add(index, element); //index of the element should be an int (starting from 0)

Per rimuovere un oggetto da ArrayList , utilizzare il metodo remove() :

myArrayList.remove(element);

O per rimuovere un elemento da un certo indice:

myArrayList.remove(index); //index of the element should be an int (starting from 0)

Sostituzione sul posto di un elemento di elenco

Questo esempio riguarda la sostituzione di un elemento List assicurando che l'elemento di sostituzione si trovi nella stessa posizione dell'elemento che viene sostituito.

Questo può essere fatto usando questi metodi:

• set (indice int, tipo T)
• int indexOf (tipo T)

Considera una ArrayList contenente gli elementi "Programma in corso!", "Ciao mondo!" e "Arrivederci mondo!"

List<String> strings = new ArrayList<String>();
strings.add("Program starting!");
strings.add("Hello world!");
strings.add("Goodbye world!");

Se conosciamo l'indice dell'elemento che vogliamo sostituire, possiamo semplicemente usare set come segue:

strings.set(1, "Hi world");

Se non conosciamo l'indice, possiamo prima cercarlo. Per esempio:

int pos = strings.indexOf("Goodbye world!");
if (pos >= 0) {
    strings.set(pos, "Goodbye cruel world!");
}

Gli appunti:

1. L'operazione set non causerà una ConcurrentModificationException .
2. L'operazione set è veloce ( O(1) ) per ArrayList ma è lenta ( O(N) ) per una LinkedList .
3. Una ricerca indexOf su ArrayList o LinkedList è lenta ( O(N) ).

Rendere una lista non modificabile

La classe Collections fornisce un modo per rendere un elenco non modificabile:

List<String> ls = new ArrayList<String>();
List<String> unmodifiableList = Collections.unmodifiableList(ls);

Se vuoi un elenco non modificabile con un oggetto puoi usare:

List<String> unmodifiableList = Collections.singletonList("Only string in the list");

Spostare gli oggetti nella lista

La classe Collections ti consente di spostare gli oggetti nella lista usando vari metodi (ls è la lista):

Inversione di una lista:

Collections.reverse(ls);

Ruotare le posizioni degli elementi in una lista

Il metodo di rotazione richiede un argomento intero. Questo è il numero di punti per spostarlo lungo la linea. Un esempio di questo è qui sotto:

List<String> ls = new ArrayList<String>();
ls.add(" how");
ls.add(" are");
ls.add(" you?");
ls.add("hello,");
Collections.rotate(ls, 1);

for(String line : ls) System.out.print(line);
System.out.println();

Questo stamperà "ciao, come stai?"

Mescolare elementi in una lista

Usando la stessa lista sopra, possiamo mescolare gli elementi in una lista:

Collections.shuffle(ls);

Possiamo anche dargli un oggetto java.util.Random che usa per posizionare in modo casuale gli oggetti in punti:

Random random = new Random(12); 
Collections.shuffle(ls, random);

Classi che implementano List - Pro e Contro

L'interfaccia List è implementata da classi diverse. Ognuno di loro ha il suo modo di implementarlo con strategie diverse e fornire pro e contro diversi.

Classi che implementano List

Queste sono tutte le classi public in Java SE 8 che implementano l'interfaccia java.util.List :

1. Classi astratte:
   • AbstractList
   • AbstractSequentialList
2. Classi concrete:
   • Lista di array
   • AttributeList
   • CopyOnWriteArrayList
   • Lista collegata
   • RoleList
   • RoleUnresolvedList
   • Pila
   • Vettore

Pro e contro di ogni implementazione in termini di complessità temporale

Lista di array

public class ArrayList<E>
extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, Serializable

ArrayList è un'implementazione di array ridimensionabile dell'interfaccia List. Memorizzando la lista in un array, ArrayList fornisce metodi (oltre ai metodi che implementano l'interfaccia List ) per manipolare la dimensione dell'array.

Inizializza ArrayList of Integer con dimensione 100

List<Integer> myList = new ArrayList<Integer>(100); // Constructs an empty list with the specified initial capacity.

- PROFESSIONISTI:

Le operazioni di dimensione, isEmpty, get , set , iterator e listIterator vengono eseguite in tempo costante. Quindi ottenere e impostare ogni elemento dell'elenco ha lo stesso costo in termini di tempo :

int e1 = myList.get(0);  //   \
int e2 = myList.get(10); //    | => All the same constant cost => O(1)
myList.set(2,10);        //   /

- CONS:

L'implementazione di un array (struttura statica) che aggiunge elementi alle dimensioni dell'array ha un costo elevato a causa del fatto che è necessario eseguire una nuova allocazione per tutto l'array. Tuttavia, dalla documentazione :

L'operazione di aggiunta viene eseguita in tempo costante ammortizzato, ovvero, l'aggiunta di n elementi richiede tempo O (n)

La rimozione di un elemento richiede O (n) tempo.

AttributeList

Alla venuta

CopyOnWriteArrayList

Alla venuta

Lista collegata

public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, Serializable

LinkedList è implementato da un elenco collegato doppiamente una struttura di dati collegata che consiste in un insieme di record collegati in sequenza chiamati nodi.

Iitialize LinkedList of Integer

List<Integer> myList = new LinkedList<Integer>(); // Constructs an empty list.

- PROFESSIONISTI:

L'aggiunta o la rimozione di un elemento nella parte anteriore dell'elenco o alla fine è costante.

myList.add(10);  // \
myList.add(0,2); //  | => constant time => O(1)
myList.remove(); // /

- CONS: dalla documentazione :

Le operazioni che indicizzano nella lista attraverseranno la lista dall'inizio o dalla fine, a seconda di quale sia più vicino all'indice specificato.

Operazioni come:

myList.get(10);    // \
myList.add(11,25); //  | => worst case done in O(n/2)
myList.set(15,35); // /

RoleList

Alla venuta

RoleUnresolvedList

Alla venuta

Pila

Alla venuta

Vettore

Alla venuta