Array dinamici in Java

Quando creano programmi di vari gradi di complessità, ogni sviluppatore utilizza molti tipi di dati, inclusi gli array. Questa struttura è adatta per riporre un set di un tipo, offre ottime prestazioni ed è generalmente conveniente. Uno svantaggio significativo degli array è che sono statici: la loro dimensione deve essere specificata in anticipo. Tuttavia, i programmatori non sanno ancora come prevedere il futuro (a meno che, ovviamente, non appaia l'intelligenza artificiale che elaborerà le informazioni in modo incredibilmente rapido e sarà in grado di prevedere qualsiasi evento). Per questo motivo abbiamo creato una struttura che può cambiare dimensione durante l'esecuzione del programma. Si chiama array dinamico .

Array dinamici nel corso JavaRush

Questo argomento è trattato in modo molto comprensibile e chiaro al livello 7 e parzialmente al livello 8 del corso JavaRush nella ricerca sulla sintassi Java. Nel corso di numerose lezioni e di ben 18 problemi, vengono trattati i temi chiave, i tipi di array dinamici e la differenza tra loro, comprese le prestazioni. Questo argomento è estremamente importante, poiché gli array dinamici alleviano lo sviluppatore da depressione, mal di testa e fanno risparmiare un'incredibile quantità di tempo.

Cos'è un array dinamico?

Un array dinamico è un array che può modificare la propria dimensione durante l'esecuzione del programma. In Java questo ruolo è svolto principalmente dalle classi ArrayList e LinkedList. A differenza degli array, ArrayList e LinkedList contengono solo tipi di dati di riferimento, ovvero possono memorizzare solo oggetti. Fortunatamente, Java dispone di meccanismi di autoboxing e autounboxing che consentono di memorizzare tipi primitivi in ​​array dinamici. Come un array statico, un array dinamico è omogeneo, ovvero può memorizzare un singolo tipo di dati. Tuttavia, grazie al meccanismo di ereditarietà e al corretto utilizzo delle interfacce, è possibile memorizzare in un array dinamico un'intera gamma di classi diverse ereditate da una comune, ma ne parleremo più avanti. Cioè, un array statico funziona così: E un array dinamico in Java funzionerà come segue (continuando il diagramma dal terzo passaggio): Java utilizza una speciale funzione nativa per copiare un array, quindi tale "spostamento" non è molto costoso.

Perché abbiamo bisogno di un array dinamico?

Un array dinamico in Java viene utilizzato per elaborare insiemi di dati omogenei la cui dimensione non è nota al momento della scrittura del programma. Ad esempio, potresti voler memorizzare nella cache i dati di ogni client che sta attualmente utilizzando l'applicazione. È impossibile prevedere in anticipo il numero di tali clienti. Senza array dinamici, questo problema può essere risolto con le seguenti opzioni:

1. Creare un array di grandi dimensioni che abbia il 100% di probabilità di coprire la necessità;
2. Crea un array statico che fungerà da buffer;
3. Applicare altre strutture dinamiche, come i set.

La prima opzione è adatta solo nel caso di un intervallo strettamente limitato. In altri casi, un array di questo tipo occuperà una grande quantità di spazio di memoria, il che è estremamente inefficiente. Il secondo richiederà l'implementazione di meccanismi aggiuntivi per la pulizia del buffer, la lettura e così via. Il terzo presenta anche degli svantaggi dovuti alle differenze di funzionalità.

Cosa fa un array dinamico in Java?

Nel linguaggio Java, le classi ArrayList e LinkedList agiscono come un array dinamico. Il più utilizzato è ArrayList, poiché si comporta come un classico array, a differenza di LinkedList, che implementa il concetto di lista doppiamente concatenata. Ne parleremo un po' più tardi.

ArrayList, LinkedList - concetti e regole operative

ArrayList è un array classico che può essere espanso durante l'esecuzione del programma. Si basa su un array regolare: la sua dimensione al momento della creazione è di 10 elementi. All’aumentare delle dimensioni, aumenta la capacità. Le regole con cui funziona ArrayList:

• Proprio come un array statico, è indicizzato da 0;
• L'inserimento alla fine e l'accesso per indice sono molto veloci - O(1);
• Per inserire un elemento all'inizio o al centro, dovrai copiare tutti gli elementi una cella a destra, quindi incollare un nuovo elemento nella posizione richiesta;
• L'accesso per valore dipende dal numero di elementi - O(n);
• A differenza di un array classico, può memorizzare null;

Nel caso di LinkedList tutto è un po' più complicato: si basa su una lista doppiamente collegata. Cioè, strutturalmente, questo array Java dinamico è un numero di oggetti sparsi che si riferiscono l'uno all'altro. È più facile spiegarlo con le immagini. All'interno di LinkedList abbiamo un oggetto principale Head, che memorizza informazioni sul numero di elementi, nonché un collegamento al primo e all'ultimo elemento: Ora il campo size = 0è , firste last = null. Ogni elemento aggiunto a questo elenco è il contenuto di un oggetto interno separato. Aggiungiamo un elemento Johnny: ora abbiamo un nodo con il valore "Johnny". Per l'elemento principale, i collegamenti al primo e all'ultimo elemento puntano al nuovo nodo. Questo oggetto ha anche collegamenti agli elementi precedenti e successivi. Il collegamento al precedente sarà sempre nullo, poiché questo è il primo elemento, e il collegamento al successivo sarà sempre nullo, poiché non esiste ancora. Risolviamo questo problema: aggiunto un nuovo elemento con il valore "Watson", che è diventato il secondo. Tieni presente che il primo elemento ha un campo nextche punta all'elemento successivo e il nuovo elemento ha un campo previousche punta a quello precedente. Per l'elemento principale, il collegamento all'ultimo elemento ora punta al nuovo nodo. Il diagramma seguente mostra come aggiungere elementi al centro dell'elenco: È stato aggiunto un nuovo elemento "Hamish". Per inserirlo al centro della lista basta riassegnare i collegamenti agli elementi, come mostrato in figura. Queste illustrazioni spiegano il processo di un elenco doppiamente collegato al livello più alto, senza entrare nei dettagli. Per riassumere la storia di LinkedList, possiamo derivare diverse regole per il suo funzionamento:

• Proprio come un array, è indicizzato da 0;
• L'accesso al primo e all'ultimo elemento non dipende dal numero di elementi - O(1);
• Ottenere un elemento tramite indice, inserirlo o eliminarlo dal centro di una lista dipende dal numero di elementi - O(n);
• Puoi utilizzare il meccanismo dell'iteratore: quindi l'inserimento e la cancellazione avverranno in tempo costante;
• A differenza di un array classico, può memorizzare null.

Esempi di codice

Esaminiamo alcuni esempi. Gli snippet di codice includono esempi sia per ArrayList che per LinkedList.

Creazione

// Создаем новый список
ArrayList<String> arrayList = new ArrayList<>();
// Создается новый список и указывается начальный размер внутреннего массива
ArrayList<String> arrayListLarge = new ArrayList<>(100000);

// Создаем новый LinkedList
LinkedList<String> linkedList = new LinkedList<>();

Aggiunta di un elemento

// Новый элемент добавляется в конец
arrayList.add("Johhny");
// Новый элемент добавляется в указанную позицию (в данном случае — в начало)
arrayList.add(0, "Watson");

// Новый элемент добавляется в конец двусвязного списка
linkedList.add("Java");
// Новый элемент добавляется в нулевую позицию списка:
linkedList.addFirst("I think");
// Новый элемент добавляется в конец списка
linkedList.addLast("language");
// Новый элемент добавляется в указанную позицию
linkedList.add(2, "is a terrific");

// Получение размера списков
int arraySize = arrayList.size(); // 2
int linkedSize = linkedList.size(); // 4

A prima vista, i metodi add()AND addLast()eseguono la stessa funzionalità, ma il metodo add()è arrivato a LinkedList dall'interfaccia Liste il metodo addLastè arrivato dall'interfaccia Deque. LinkedList implementa entrambe queste interfacce. Una buona pratica in questo caso sarebbe quella di utilizzare il metodo più appropriato al contesto. Se LinkedList viene utilizzato come coda, è meglio utilizzare l'estensione addLast. Se LinkedList viene utilizzato come elenco, sarebbe appropriato utilizzare add().

Rimozione di un elemento

// Удаление element по индексу
arrayList.remove(0);
// Удаление element по значению
arrayList.remove("Johnny");

// Удаление первого element в списке
linkedList.removeFirst();
// Удаление первого element в списке, фактически вызов предыдущего метода
linkedList.remove();
// Удаление последнего element в списке
linkedList.removeLast();
// Удаление первого вхождения element в список
linkedList.removeFirstOccurrence("language");
// Удаление последнего вхождения element в список
linkedList.removeLastOccurrence("Java");
// Удаление по индексу
linkedList.remove(2);

Se un oggetto viene eliminato dall'indice, il metodo restituisce l'oggetto eliminato. Se un oggetto viene eliminato per valore (o vengono eliminati il ​​primo o l'ultimo elemento di una LinkedList), il metodo restituisce true se l'oggetto viene trovato ed eliminato, false altrimenti.

Accesso a un elemento e ricerca nell'elenco

// Доступ к элементу по индексу
String arrayElement = arrayList.get(2);
// Поиск element по значению
int arrayIndex = arrayList.indexOf("Watson");
// Поиск последнего индекса вхождения element в список
int lastArrayIndex = arrayList.lastIndexOf("Watson");

// Доступ по индексу
String linkedElement = linkedList.get(3);
// Получение первого element
String firstLinkedElement = linkedList.getFirst();
// Получение последнего element
String lastLinkedElement = linkedList.getLast();

// Поиск element по значению
int linkedIndex = linkedList.indexOf("Java");
// Поиск последнего индекса вхождения element в список
int lastLinkedIndex = linkedList.lastIndexOf("Java");

Camminare in loop

// Использование обычного цикла
for(int i = 0; i<arrayList.size(); i++) {
  String value = arrayList.get(i);
  System.out.println(value);
}

for(int i = 0; i<linkedList.size(); i++) {
  String value = linkedList.get(i);
  System.out.println(value);
}

// Использование цикла for-each
for(String s : arrayList) {
  System.out.println(s);
}

for(String s : linkedList) {
  System.out.println(s);
}

Qui vale la pena spendere qualche parola sulla ricerca. Molti sviluppatori alle prime armi, quando cercano un elemento in un elenco, iniziano la ricerca in loop, confrontando tutti gli elementi con quello cercato, nonostante la presenza di metodi indexOf()e lastIndexOf(). Puoi anche utilizzare il metodo contains()per ottenere il fatto che un elemento sia nell'elenco:

boolean isContainsSherlock = arrayList.contains("Sherlock");
boolean isContainsPhp = linkedList.contains("Php");

Collegamenti per ulteriori letture

1. C'è un eccellente articolo qui sulla rimozione di elementi da un ArrayList. Dato che si tratta di un array Java dinamico , ci sono molte sottigliezze nella rimozione degli elementi.
2. Il funzionamento di ArrayList è illustrato in dettaglio qui .
3. Qualcosa in più su LinkedList.
4. Un paio di articoli di Habr su ArrayList e LinkedList .