CodeGym /Java Course /Collezioni Java /Implementazioni dell'interfaccia List

Implementazioni dell'interfaccia List

Collezioni Java
Livello 6 , Lezione 5
Disponibile

"Se pensi che abbiamo finito con l'interfaccia List, allora ti sbagli. Abbiamo appena iniziato. Lascia che ti parli delle raccolte LinkedList e ArrayList ."

"Inizierò con la raccolta ArrayList."

"Ecco come appare il diagramma di ereditarietà di questa raccolta:"

"Le interfacce sono verdi."

"Le classi astratte sono viola."

"Le classi ordinarie sono rosse."

"Le linee continue rappresentano l'ereditarietà e le linee tratteggiate rappresentano le implementazioni dell'interfaccia."

"Questa è la raccolta più semplice. All'interno di un ArrayList , gli elementi sono memorizzati in un semplice array."

"Il vantaggio principale di questa raccolta rispetto a un array è la sua capacità di espandersi, ovvero la sua capacità di aumentare la sua lunghezza secondo necessità".

"Se l'array esaurisce lo spazio, viene creato un secondo array più grande e tutti gli elementi del primo array vengono copiati in esso. Quindi il secondo array prende il posto del primo e il primo viene scartato (sarà distrutta dal netturbino)."

"Quanto è più grande l'array?"

"La lunghezza del nuovo array è calcolata come (3*n)/2+1, dove n è la lunghezza del vecchio array. In altre parole, se il vecchio array era lungo 100 elementi, quello nuovo sarà 300/2+1 = 151."

"Quando si aggiunge un elemento al centro di un ArrayList, tutti gli elementi a destra di dove verrà inserito il nuovo elemento vengono copiati 1 posizione a destra, quindi il nuovo elemento viene aggiunto alla cella vuota."

"Quando rimuovi un elemento dal centro, tutti gli elementi a destra di quell'elemento vengono copiati di 1 posizione a sinistra."

"Stai dicendo che ArrayList si allunga quando aggiungi elementi e che si accorcia quando rimuovi elementi?"

"No, l'array all'interno di un ArrayList non si accorcia mai da solo; tuttavia, puoi forzare un ArrayList a ridurre il suo array interno alla dimensione più piccola possibile chiamando il metodo trimToSize (). "

"E, naturalmente, ti parlerò di LinkedList."

"Ecco come appare il suo diagramma di ereditarietà:"

"Le interfacce sono verdi."

"Le classi astratte sono viola."

"Le classi ordinarie sono rosse."

"Le linee continue rappresentano l'ereditarietà e le linee tratteggiate rappresentano le implementazioni dell'interfaccia."

"Come già sai, LinkedList memorizza gli elementi come un elenco collegato."

"Lo sento sempre, ma potresti dirmi di cosa si tratta?"

"Certo. "È semplice."

"Un elenco collegato è costituito da elementi che a) memorizzano dati eb) memorizzano riferimenti agli elementi successivi e precedenti."

"Ecco come apparirebbe la classe per un tale elemento se memorizzasse le stringhe:"

Esempio Descrizione
class LinkedListElement
{
String data;
LinkedListElement next;
LinkedListElement previous;
}
Il campo dati memorizza il valore String dell'elemento.
Il campo successivo memorizza un riferimento all'elemento successivo nell'elenco.
Il campo precedente memorizza un riferimento all'elemento precedente nell'elenco.

"E se usiamo una dichiarazione di tipo generico, allora sarebbe simile a questo:"

Una classe per un elemento di elenco collegato con una dichiarazione di tipo generico
class LinkedListElement<T>
{
 T data;
 LinkedListElement<T> next;
 LinkedListElement<T> previous;
}

"Ha senso."

"Per capirlo meglio, scriviamo codice in cui aggiungiamo 10 elementi a un elenco doppiamente collegato:"

Esempio
public static void main(String[] args)
{
 LinkedListElement<Integer> tail; // The tail (very last element) of the list

 for(int i = 0; i < 10; i++)
 {
  LinkedListElement<Integer> element = new LinkedListElement<Integer>();
  element.data = i;

  if (tail == null) // If the tail doesn't exist, then make our element the last element
  {
   tail = element;
  }
  else // if there is a tail, add the element
  {
   tail.next = element; // Set the next field on the tail element
   element.previous = tail; // Add a reference to the tail to the new element
   tail = element; // Make the new element the tail
  }
 }
}

"Immagina di avere 10 elementi nell'elenco. Ecco come inserire un elemento nel mezzo:"

Implementazioni dell'interfaccia List - 3

"I collegamenti che sono cambiati sono evidenziati in rosso vivo . Ora puntano al nuovo elemento."

"I nuovi collegamenti sono evidenziati in viola brillante . Sono i collegamenti del nuovo elemento ai suoi vicini."

"E ora come codice:"

Inserisci un elemento nel mezzo di un elenco collegato
// This field stores the element that is the head of the list
LinkedListElement<Integer> head = …

// Get the 4th element (counting from zero)
LinkedListElement<Integer> element4 = head.next.next.next.next;
// Get the 5th element
LinkedListElement<Integer> element5 = element4.next;

// Create the new element that we will insert
LinkedListElement<Integer> newElement = new LinkedListElement<Integer>();
newElement.data = -18;

// Replace the references in the element on the left
newElement.previous = element4;
element4.next = newElement;

// Replace the references in the element on the right
newElement.next = element5;
element5.previous = newElement;

"Grazie, Ellie. Ho sicuramente imparato molte cose nuove sulle liste."

Commenti
TO VIEW ALL COMMENTS OR TO MAKE A COMMENT,
GO TO FULL VERSION