Tableaux dynamiques en Java

Lors de la création de programmes plus ou moins complexes, chaque développeur utilise de nombreux types de données, notamment des tableaux. Cette structure est bien adaptée au stockage d'un ensemble d'un type, offre d'excellentes performances et est généralement pratique. Un inconvénient majeur des tableaux est qu'ils sont statiques : leur taille doit être spécifiée à l'avance. Cependant, les programmeurs ne savent pas encore comment prédire l'avenir (à moins, bien sûr, qu'une IA traite les informations incroyablement rapidement et soit capable de prédire n'importe quel événement). Pour cette raison, nous avons créé une structure qui peut changer de taille pendant l'exécution du programme. C'est ce qu'on appelle un tableau dynamique .

Tableaux dynamiques dans le cours JavaRush

Ce sujet est abordé de manière très intelligible et claire au niveau 7 et partiellement au niveau 8 du cours JavaRush dans la quête Java Syntax. Au cours de plusieurs conférences et jusqu'à 18 problèmes, les questions clés sont abordées, les types de tableaux dynamiques et la différence entre eux, y compris les performances. Ce sujet est extrêmement important, car les tableaux dynamiques soulagent le développeur de la dépression, des maux de tête et lui font gagner un temps incroyable.

Qu'est-ce qu'un tableau dynamique ?

Un tableau dynamique est un tableau qui peut changer de taille lors de l'exécution d'un programme. En Java, ce rôle est principalement joué par les classes ArrayList et LinkedList. Contrairement aux tableaux, ArrayList et LinkedList contiennent uniquement des types de données de référence, c'est-à-dire qu'ils ne peuvent stocker que des objets. Heureusement, Java dispose de mécanismes d'autoboxing et d'autounboxing qui vous permettent de stocker des types primitifs dans des tableaux dynamiques. Comme un tableau statique, un tableau dynamique est homogène, c’est-à-dire qu’il peut stocker un seul type de données. Cependant, grâce au mécanisme d'héritage et à l'utilisation appropriée des interfaces, il est possible de stocker dans un tableau dynamique toute une gamme de classes différentes héritées d'une classe commune, mais nous en parlerons ci-dessous. Autrement dit, un tableau statique fonctionne comme ceci : Et un tableau dynamique en Java fonctionnera comme suit (en continuant le diagramme de la troisième étape) : Java utilise une fonction native spéciale pour copier un tableau, donc un tel « déplacement » n'est pas très cher.

Pourquoi avons-nous besoin d’un tableau dynamique ?

Un tableau dynamique en Java est utilisé pour traiter des ensembles de données homogènes dont la taille est inconnue au moment de l'écriture du programme. Par exemple, vous souhaiterez peut-être mettre en cache les données de chaque client qui utilise actuellement l'application. Il est impossible de prédire à l’avance le nombre de ces clients. Sans tableaux dynamiques, ce problème peut être résolu avec les options suivantes :

1. Créer un large éventail de chances de couvrir à 100 % les besoins ;
2. Créez un tableau statique qui fera office de tampon ;
3. Appliquez d'autres structures dynamiques, telles que des ensembles.

La première option ne convient que dans le cas d'une portée strictement limitée. Dans d'autres cas, un tel tableau occupera une grande quantité d'espace mémoire, ce qui est extrêmement inefficace. La seconde nécessitera la mise en œuvre de mécanismes supplémentaires pour l’effacement du tampon, la lecture, etc. Le troisième présente également des inconvénients dus à des différences de fonctionnalités.

Que fait un tableau dynamique en Java ?

Dans le langage Java, les classes ArrayList et LinkedList agissent comme un tableau dynamique. Le plus couramment utilisé est ArrayList, car il agit comme un tableau classique, contrairement à LinkedList, qui implémente le concept de liste doublement chaînée. Nous en reparlerons un peu plus tard.

ArrayList, LinkedList - concepts et règles de fonctionnement

ArrayList est un tableau classique qui peut être étendu lors de l'exécution du programme. Il est basé sur un tableau régulier : sa taille une fois créé est de 10 éléments. Plus la taille augmente, plus la capacité augmente. Les règles selon lesquelles ArrayList fonctionne :

• Tout comme un tableau statique, il est indexé à partir de 0 ;
• L'insertion à la fin et l'accès par index sont très rapides - O(1);
• Pour insérer un élément au début ou au milieu, vous devrez copier tous les éléments une cellule vers la droite, puis coller un nouvel élément à la position souhaitée ;
• L'accès par valeur dépend du nombre d'éléments - O(n) ;
• Contrairement à un tableau classique, il peut stocker des valeurs nulles ;

Dans le cas de LinkedList, tout est un peu plus compliqué : elle repose sur une liste doublement chaînée. Autrement dit, structurellement, ce tableau Java dynamique est constitué d'un certain nombre d'objets dispersés qui se réfèrent les uns aux autres. C'est plus facile à expliquer avec des images. Dans LinkedList, nous avons un objet principal Head, qui stocke des informations sur le nombre d'éléments, ainsi qu'un lien vers le premier et le dernier élément : maintenant le champ size = 0est , firstet last = null. Chaque élément ajouté à cette liste est le contenu d'un objet interne distinct. Ajoutons un élément Johnny: Nous avons maintenant un nœud avec la valeur « Johnny ». Pour l'élément principal, les liens vers le premier et le dernier élément pointent vers le nouveau nœud. Cet objet possède également des liens vers les éléments précédents et suivants. Le lien vers le précédent sera toujours nul, puisqu'il s'agit du premier élément, et le lien vers le suivant sera toujours nul, car il n'existe pas encore. Corrigeons cela : Ajout d'un nouvel élément avec la valeur « Watson », qui est devenu le deuxième. Veuillez noter que le premier élément a un champ nextqui pointe vers l'élément suivant et que le nouvel élément a un champ previousqui pointe vers le précédent. Pour l'élément principal, le lien vers le dernier élément pointe désormais vers le nouveau nœud. Le schéma suivant montre comment ajouter des éléments au milieu de la liste : Un nouvel élément « Hamish » a été ajouté. Pour l'insérer au milieu de la liste, il suffit de réaffecter les liens aux éléments, comme indiqué sur la figure. Ces illustrations expliquent le processus d'une liste doublement chaînée au niveau supérieur, sans entrer dans les détails. Pour résumer l'histoire de LinkedList, nous pouvons en déduire plusieurs règles pour son fonctionnement :

• Tout comme un tableau, il est indexé à partir de 0 ;
• L'accès au premier et au dernier élément ne dépend pas du nombre d'éléments - O(1) ;
• Obtenir un élément par index, l'insérer ou le supprimer au milieu d'une liste dépend du nombre d'éléments - O(n);
• Vous pouvez utiliser le mécanisme itérateur : alors l'insertion et la suppression se produiront en temps constant ;
• Contrairement à un tableau classique, il peut stocker des valeurs nulles.

Exemples de codes

Passons en revue quelques exemples. Les extraits de code incluent des exemples pour ArrayList et LinkedList.

Création

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

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

Ajout d'un élément

// Новый элемент добавляется в конец
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

À première vue, les méthodes add()AND addLast()exécutent la même fonctionnalité, mais la méthode add()est venue de l'interface à LinkedList Listet la méthode addLastest venue de l'interface Deque. LinkedList implémente ces deux interfaces. Une bonne pratique dans ce cas serait d’utiliser la méthode la plus appropriée au contexte. Si LinkedList est utilisé comme file d’attente, il est préférable d’utiliser le fichier addLast. Si LinkedList est utilisé comme liste, il serait approprié d'utiliser add().

Supprimer un élément

// Удаление 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);

Si un objet est supprimé par index, la méthode renvoie l'objet supprimé. Si un objet est supprimé par valeur (ou si le premier ou le dernier élément d'une LinkedList est supprimé), la méthode renvoie true si l'objet est trouvé et supprimé, false sinon.

Accéder à un élément et rechercher dans la liste

// Доступ к элементу по индексу
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");

Marcher en boucle

// Использование обычного цикла
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);
}

Ici, cela vaut la peine de dire quelques mots sur la recherche. De nombreux développeurs novices, lorsqu'ils recherchent un élément dans une liste, commencent la recherche en boucle, en comparant tous les éléments avec celui recherché, malgré la présence de méthodes indexOf()et lastIndexOf(). Vous pouvez également utiliser la méthode contains()pour obtenir le fait qu'un élément est dans la liste :

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

Liens pour des lectures complémentaires

1. Il existe un excellent article ici sur la suppression d'éléments d'une ArrayList. Étant donné qu'il s'agit d'un tableau Java dynamique , la suppression d'éléments présente de nombreuses subtilités.
2. Le fonctionnement d'ArrayList est illustré en détail ici .
3. Un peu plus sur LinkedList.
4. Quelques articles de Habr sur ArrayList et LinkedList .