Une question posée dans presque toutes les interviews Java : dites-moi la différence entre ArrayList et LinkedList

Avant-propos

Bonjour à tous, je suis votre vieil ami Qing Ge, je sais que je vous manque, alors je suis de nouveau là ?

La structure des données de Java est au centre de l'interview. vous avez participé à Java, je pense que tous les étudiants interviewés en ont fait l'expérience. Lorsque les enquêteurs posent de telles questions, ils souhaitent souvent vérifier si vous avez étudié les structures sous-jacentes des types de données couramment utilisés en Java, plutôt que de simplement rester au niveau « savoir comment utiliser ». Alors, comment bien répondre à cette question lors de l’entretien et satisfaire l’intervieweur ?

Dans ce numéro, je me concentrerai sur les points de test haute fréquence JavaAnalysez les principes d'ArrayList et LinkedList, j'espère que cela pourra vous aider. ArrayList和LinkedList的原理进行分析，希望能帮助到你。

ArrayList和LinkedList简介

ArrayList底层是一个Object类型的数组，初始容量是10，支持动态扩容，扩容后的容量是当前容量的1.5倍，它的最大容量是 Integer.MAX_VALUE - 8（但是仍可以扩容到Integer.MAX_VALUE），对于空出的8位，目前的解释是避免一些机器内存溢出，减少出错几率。

LinkedList

Introduction à ArrayList et LinkedList

🎜 🎜🎜

ArrayList La couche inférieure est un tableau de type objet avec une capacité initiale de 10 et prend en charge l'expansion dynamique. La capacité étendue est de 1,5 fois la capacité actuelle. Sa capacité maximale est Integer.MAX_VALUE - 8 (mais elle peut toujours être étendue à Integer.MAX_VALUE). ), pour les 8 bits libérés, l'interprétation actuelle est <code style="font-size: 14px;overflow-wrap: break-word;padding: 2px 4px;border-radius: 4px;margin-right: 2px;margin- gauche : 2px ; couleur d'arrière-plan : rgba (27, 31, 35, 0,05) ; famille de polices : « Operator Mono », Consolas, Monaco, Menlo, monospace ; coupure de mot : break-all ; couleur : rgb (239, 112, 96);">Évitez certains débordements de mémoire machine et réduisez les risques d'erreurs. 🎜

LinkedListLa couche inférieure est une liste doublement chaînée. La capacité initiale est de 0. Pour augmentez la capacité, créez-en simplement une nouvelle. Pointez simplement le nœud vers le pointeur. 🎜🎜🎜Afin de le simplifier dans un langage exprimable verbalement afin que les étudiants puissent l'expliquer à l'intervieweur lors de l'entretien, je ne publierai pas ici les instructions auxiliaires du code source. Les étudiants intéressés peuvent vérifier le code source pour voir la structure interne et les méthodes. . Approfondissez votre compréhension de ce domaine. 🎜

Difference

Query

• ArrayList est très efficace en accès aléatoire, car le stockage des éléments est ordonné et l'emplacement des données interrogées dans la mémoire peut être connu via l'indice index. L'adresse est rapide et la complexité temporelle est O(1);
• L'efficacité de la requête LinkedList est faible, elle doit parcourir la liste chaînée une par une et la complexité temporelle est O(. n).

Insertion

• ArrayList est plus efficace lors de l'insertion de la queue, avec une complexité temporelle de O(1), mais l'efficacité de l'insertion à d'autres emplacements est relativement faible, nécessitant une grande quantité de mouvements de données, avec un temps complexité de O( n);
• LinkedList est plus efficace pour insérer des éléments en tête et en queue, et la complexité temporelle est O(1). Cependant, pour insérer un élément à une position spécifiée au milieu, vous avez besoin. parcourir pour trouver d’abord la position de l’élément, puis l’insérer, ce qui est complexe Degré O(n).

Delete

• La suppression d'éléments d'ArrayList nécessite beaucoup de mouvements de données, à l'exception du nœud final, et la complexité temporelle est O(n);
• LinkedList est relativement efficace pour supprimer des éléments. il suffit de changer le pointage du pointeur, mais la suppression d'éléments nécessite de parcourir et d'interroger l'emplacement des données, avec une complexité temporelle de O(n).

Espace mémoire

• ArrayList est implémenté en fonction des tableaux. La capacité est fixée après chaque extension, donc une partie de l'espace sera réservée à la fin
• LinkedList est implémentée en fonction de doublement ; listes chaînées, donc chaque nœud En plus de sauvegarder les données, vous devez également sauvegarder les pointeurs des nœuds précédents et suivants, ce qui consommera de l'espace.

Mécanisme d'expansion

• ArrayList doit copier les éléments du tableau d'origine dans un nouveau tableau à chaque fois qu'il est développé
• LinkedList est une liste chaînée et il n'y a pas d'expansion ;

Uniformité

Sécurité des fils

ArrayList et LinkedList sont tous deux dangereux pour les threads et peuvent facilement provoquer des problèmes de lecture sale dans les environnements multithread. Vous pouvez utiliser la méthode Collections.synchronizedList() pour garantir la sécurité des threads

Fonctionnalités de stockage

Les éléments stockés sont tous ordonnés. répété et les nouveaux éléments sont stockés à la fin de la liste.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!