Implémentations de l'interface List

"Si vous pensez que nous en avons tous fini avec l'interface List, alors vous vous trompez. Nous ne faisons que commencer. Laissez-moi vous parler des collections LinkedList et ArrayList ."

"Je vais commencer par la collection ArrayList."

"Voici à quoi ressemble le diagramme d'héritage de cette collection :"

"Les interfaces sont vertes."

"Les cours abstraits sont violets."

"Les classes ordinaires sont rouges."

"Les lignes pleines représentent l'héritage et les lignes pointillées représentent les implémentations d'interface."

"C'est la collection la plus simple. Dans une ArrayList , les éléments sont stockés dans un tableau simple."

"Le principal avantage de cette collection par rapport à un tableau est sa capacité à s'étendre, c'est-à-dire sa capacité à augmenter sa longueur selon les besoins."

"Si le tableau manque d'espace, un deuxième tableau plus grand est créé et tous les éléments du premier tableau y sont copiés. Ensuite, le deuxième tableau prend la place du premier et le premier est supprimé (il sera détruit par le ramasseur d'ordures)."

"Combien de plus le tableau devient-il?"

"La longueur du nouveau tableau est calculée comme (3*n)/2+1, où n est la longueur de l'ancien tableau. En d'autres termes, si l'ancien tableau avait une longueur de 100 éléments, alors le nouveau sera 300/2+1 = 151."

"Lors de l'ajout d'un élément au milieu d'une ArrayList, tous les éléments à droite de l'endroit où le nouvel élément sera inséré sont copiés 1 position vers la droite, puis le nouvel élément est ajouté à la cellule vide."

"Lors de la suppression d'un élément du milieu, tous les éléments à droite de cet élément sont copiés d'une position vers la gauche."

"Êtes-vous en train de dire que la ArrayList s'allonge lorsque vous y ajoutez des éléments, et qu'elle se raccourcit lorsque vous en supprimez?"

"Non, le tableau à l'intérieur d'une ArrayList ne se raccourcit jamais de lui-même ; cependant, vous pouvez forcer une ArrayList à réduire son tableau interne à la plus petite taille possible en appelant la méthode trimToSize ()."

"Et, bien sûr, je vais vous parler de LinkedList."

"Voici à quoi ressemble son diagramme d'héritage :"

"Les interfaces sont vertes."

"Les cours abstraits sont violets."

"Les classes ordinaires sont rouges."

"Les lignes pleines représentent l'héritage et les lignes pointillées représentent les implémentations d'interface."

"Comme vous le savez déjà, LinkedList stocke les éléments sous forme de liste liée."

« J'entends ça tout le temps, mais peux-tu me dire ce que c'est ?

"Bien sûr. "C'est simple."

"Une liste chaînée se compose d'éléments qui a) stockent des données et b) stockent des références aux éléments suivants et précédents."

"Voici à quoi ressemblerait la classe d' un tel élément si elle stockait des chaînes :"

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

"Et si nous utilisons une déclaration de type générique, cela ressemblerait à ceci :"

class LinkedListElement<T>
{
 T data;
 LinkedListElement<T> next;
 LinkedListElement<T> previous;
}

"Logique."

"Pour mieux le comprendre, écrivons du code dans lequel nous ajoutons 10 éléments à une liste doublement liée :"

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
  }
 }
}

"Imaginez que nous ayons 10 éléments dans la liste. Voici comment insérer un élément au milieu :"

"Les liens qui ont changé sont surlignés en rouge vif . Ils pointent maintenant vers le nouvel élément."

"Les nouveaux liens sont surlignés en violet vif . Ce sont les liens du nouvel élément vers ses voisins."

"Et maintenant, en tant que code :"

// 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;

"Merci, Ellie. J'ai définitivement appris beaucoup de nouvelles choses sur les listes."