List en Java : une brève introduction aux interfaces d'implémentation ArrayList et LinkedList

ArrayList est implémenté sur la base de tableaux. Il s'agit d'un tableau dynamique dont la capacité peut augmenter automatiquement, de la même manière que l'application dynamique de mémoire et la croissance dynamique de la mémoire en langage C. LinkedList est implémenté sur la base d'une liste chaînée circulaire bidirectionnelle (qui peut être facilement visible à partir du code source). En plus d'être exploitée comme une liste chaînée, elle peut également être utilisée comme pile, file d'attente et file d'attente à double extrémité.

1. Introduction à List

2. ArrayList

Caractéristiques de ArrayList

ArrayList est implémenté sur la base d'un tableau et est un Tableau dynamique, sa capacité peut augmenter automatiquement, similaire à l'application dynamique de mémoire et à la croissance dynamique de la mémoire en langage C.

ArrayList est thread-unsafe ne peut être utilisé que dans un environnement monothread Dans un environnement multithread, vous pouvez envisager d'utiliser Collections.synchronizedList. (Liste de liste) pour renvoyer une classe ArrayList thread-safe, vous pouvez également utiliser la classe CopyOnWriteArrayList sous le package simultané.

ArrayList implémente l'interface Serialisable, il prend donc en charge la sérialisation, peut être transmis via la sérialisation

ArrayList implémente l'interface RandomAccess, prenant en charge l'accès aléatoire rapide, qui est en fait Accès rapide en inscrivant le numéro de série

implémente l'interface Cloneable, peut être cloné

Notez ses trois méthodes de construction différentes. La capacité de l'ArrayList construit par le constructeur sans paramètre est de 10 par défaut. Le constructeur avec les paramètres Collection convertit la Collection en un tableau et l'assigne au tableau d'implémentation ArrayList elementData.

Faites attention à assurerCapacity, une méthode pour augmenter la capacité. Chaque fois qu'un élément est ajouté à ArrayList (il peut s'agir de 1 ou d'un groupe), cette méthode doit être appelée pour garantir une capacité suffisante. Lorsque la capacité n'est pas suffisante pour accueillir le nombre actuel d'éléments, la nouvelle capacité est définie à 1,5 fois l'ancienne capacité plus 1. Si la nouvelle capacité définie n'est pas suffisante, la nouvelle capacité est directement définie sur le paramètre transmis (c'est-à-dire est la capacité requise), puis utilisez la méthode Arrays.copyof() pour copier les éléments dans un nouveau tableau (voir le point 3 ci-dessous pour plus de détails). On peut en voir que lorsque la capacité n'est pas suffisante, chaque fois qu'un élément est ajouté, les éléments d'origine doivent être copiés dans un nouveau tableau, ce qui prend beaucoup de temps. Par conséquent, il est recommandé d'utiliser ArrayList uniquement lorsque le. le nombre d'éléments peut être déterminé à l'avance, sinon il est recommandé d'utiliser LinkedList.

L'implémentation d'ArrayList appelle un grand nombre de méthodes Arrays.copyof() et System.arraycopy(). Il nous est nécessaire d’avoir une compréhension approfondie de la mise en œuvre de ces deux méthodes.

Regardons d’abord la méthode Arrays.copyof(). Il a de nombreuses méthodes surchargées, mais les idées d'implémentation sont les mêmes. Regardons le code source de la version générique :

public static <T> T[] copyOf(T[] original, int newLength) {
    return (T[]) copyOf(original, newLength, original.getClass());
}

Évidemment, une autre méthode copyof est appelée, qui a trois paramètres, le dernier paramètre spécifie. le type de données à convertir. Le code source est le suivant :

public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
    T[] copy = ((Object)newType == (Object)Object[].class) ? (T[]) new Object[newLength] : (T[]) Array.newInstance(newType.getComponentType(), newLength);
    System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength));
    return copy;
}

On voit clairement ici que cette méthode crée en fait un tableau avec une longueur de newlength à l'intérieur. () pour copier les éléments du tableau d'origine vers le nouveau tableau.

Regardons la méthode System.arraycopy(). Cette méthode est marquée comme native et appelle le code C/C++ du système. Elle n'est pas visible dans JDK, mais son code source est visible dans openJDK. Cette fonction appelle en fait la fonction memmove() du langage C, elle peut donc garantir la copie et le déplacement corrects des éléments dans le même tableau. Elle est beaucoup plus efficace que la méthode de copie générale et est très adaptée au traitement par lots de tableaux. Java recommande fortement d'utiliser cette méthode lors de la copie d'un grand nombre d'éléments de tableau pour obtenir une plus grande efficacité.

Faites attention aux deux méthodes toArray d'ArrayList qui sont converties en tableaux statiques.

La première, la méthode Object[] toArray(). Cette méthode peut générer une exception java.lang.ClassCastException. Si vous utilisez directement la méthode de conversion descendante pour convertir l'intégralité de la collection ArrayList en un tableau Array du type spécifié, cette exception sera levée. Cependant, si vous ne la convertissez pas en un tableau Array du type spécifié. Tableau de tableau, le downcasting, mais le downcasting de chaque élément, ne lèvera pas cette exception. Évidemment, le downcasting des éléments du tableau un par un n'est pas efficace et peu pratique.

Deuxièmement, la méthode T[] toArray(T[] a). Cette méthode peut directement transformer le tableau converti depuis ArrayList vers le bas dans son ensemble (la transformation est en fait implémentée dans le code source de cette méthode), et il peut être vu à partir du code source de cette méthode que lorsque la taille du paramètre a est insuffisante , elle sera appelée en interne méthode Arrays.copyOf, cette méthode crée en interne un nouveau tableau et le renvoie, donc la forme courante de cette méthode est la suivante :

public static Integer[] vectorToArray2(ArrayList<Integer> v) {  
    Integer[] newText = (Integer[])v.toArray(new Integer[0]);  
    return newText;  
}

ArrayList基于数组实现，可以通过下标索引直接查找到指定位置的元素，因此查找效率高，但每次插入或删除元素，就要大量地移动元素，插入删除元素的效率低。

在查找给定元素索引值等的方法中，源码都将该元素的值分为null和不为null两种情况处理，ArrayList中允许元素为null。

三、LinkedList

LinkedList的特点

LinkedList是基于双向循环链表（从源码中可以很容易看出）实现的，除了可以当做链表来操作外，它还可以当做栈、队列和双端队列来使用；

LinkedList同样是非线程安全的，只在单线程下适合使用；

LinkedList实现了Serializable接口，因此它支持序列化，能够通过序列化传输；

实现了Cloneable接口，能被克隆；

相关推荐：

接口测试基础之入门篇

视频教程：

去除ArrayList集合中的重复自定义对象元素案例

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!