Implementazioni dell'interfaccia List

"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:"

class LinkedListElement
{
String data;
LinkedListElement next;
LinkedListElement previous;
}

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

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:"

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:"

"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:"

// 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."