Chapitre d'amélioration de Java (32) -----Résumé de la liste
- 黄舟original
- 2017-02-11 10:21:021179parcourir
Avant, LZ a entièrement introduit la plupart des connaissances sur l'interface List, telles que ArrayList, LinkedList, Vector et Stack. Grâce à ces points de connaissances, vous pouvez avoir une compréhension plus approfondie de l'interface List. Seules les connaissances résumées par induction sont vos connaissances. Donc ci-dessous, LZ fera un résumé de l'interface List. Lecture recommandée :
Chapitre sur l'amélioration de Java (21)---- - ArrayList
> Chapitre sur l'amélioration de Java (29)-----Vecteur
Amélioration Java (Sanyi) -----Pile
1. Présentation de l'interface Liste
L'interface Liste devient une collection ordonnée, c'est-à-dire une séquence. Cette interface peut contrôler avec précision la position d'insertion de chaque élément dans la liste, et les utilisateurs peuvent accéder aux éléments en fonction de leur index entier (position dans la liste) et rechercher des éléments dans la liste. L'image suivante est le schéma-cadre de l'interface List :
Avec le diagramme-cadre, vous pouvez clairement comprendre la structure de List Ses classes et interfaces sont les suivantes :
L'interface racine dans la Collection. hiérarchie. Il représente un ensemble d’objets, également appelés éléments d’une collection. Pour Collection, il ne fournit aucune implémentation directe et toutes les implémentations relèvent de la responsabilité de ses sous-classes.
AbstractCollection :
Fournit une implémentation de base de l'interface Collection pour minimiser la nécessité d'implémenter ce travail d'interface. Pour que nous puissions implémenter une collection immuable, il nous suffit d'étendre cette classe et de fournir des implémentations des méthodes iterator et size. Mais pour implémenter une collection modifiable, la méthode add de cette classe doit être surchargée (sinon, UnsupportedOperationException sera levée), et l'itérateur renvoyé par la méthode iterator doit également implémenter sa méthode Remove.térateur :
itérateur.liste et obtient la position actuelle de l'itérateur dans la liste.
. Il représente une file d'attente ordonnée.
AbstractList : implémentation de base de l'interface List pour minimiser la mise en œuvre du stockage de données à « accès aléatoire » (tel sous forme de tableau) est nécessaire pour fonctionner avec le support de cette interface.
File d'attente : File d'attente. Fournit des opérations de base d’insertion, de récupération et d’inspection pour la file d’attente. Deque : Une collection linéaire qui prend en charge l'insertion et la suppression d'éléments aux deux extrémités. La plupart des implémentations de Deque n'ont pas de limite fixe sur le nombre d'éléments qu'elles peuvent contenir, mais cette interface prend en charge à la fois les deques avec une limite de capacité et les deques sans limite de taille fixe. Le travail requis pour accéder à cette interface prise en charge par un magasin de données tel qu'une liste chaînée. Dans un sens, cette classe revient à implémenter une méthode « d’accès aléatoire » sur un itérateur de liste. LinkedList : implémentation de liste chaînée de l'interface List. Il implémente toutes les opérations de liste facultatives. Il implémente toutes les opérations de liste facultatives et autorise tous les éléments, y compris null. En plus d'implémenter l'interface List, cette classe fournit également des méthodes pour manipuler la taille du tableau utilisé en interne pour stocker la liste. Vector : implémente un tableau d'objets évolutif. Comme un tableau, il contient des composants accessibles à l’aide d’index entiers. Pile : Pile d'objets dernier entré, premier sorti (LIFO). Il étend la classe Vector avec cinq opérations qui permettent de traiter les vecteurs comme des piles. Énumération : 2. Scénarios d'utilisation Le but fondamental de l’apprentissage des connaissances est de les utiliser. Chaque point de connaissance a son périmètre d'utilisation. Il en va de même pour les collections. La famille des collections en Java est très vaste et chaque membre a le scénario d'utilisation le plus approprié. Lorsque je suis entré en contact avec List pour la première fois, LZ a dit Si cela implique des opérations telles que "pile", "file d'attente" et "liste chaînée", veuillez donner la priorité à l'utilisation de List. Quant à la liste dont il s'agit, elle est divisée comme suit : 1 Si vous avez besoin d'insérer et de supprimer rapidement des éléments, vous devez utiliser. Liste liée. 2 Si vous avez besoin d'accéder rapidement aux éléments, vous devez utiliser ArrayList. 2.1 ArrayList, analyse des performances de LinkedList Nous avons également découvert les scénarios d'utilisation et les différences entre eux.
>
L'énumération, un objet qui implémente cette interface, génère une série d'éléments, un à la fois. la première fois. Les appels continus à la méthode nextElement renverront une séquence d’éléments consécutifs.
3. Pour un "environnement monothread" ou un "environnement multithread, mais la liste n'est gérée que par un seul thread", vous devez envisager d'utiliser un mode asynchrone classes. S'il s'agit d'un "environnement multithread et que List peut être exploité par plusieurs threads en même temps". Envisagez d'utiliser une classe synchronisée (telle que Vector). public class ListTest {
private static final int COUNT = 100000;
private static ArrayList arrayList = new ArrayList<>();
private static LinkedList linkedList = new LinkedList<>();
private static Vector vector = new Vector<>();
public static void insertToList(List list){
long startTime = System.currentTimeMillis();
for(int i = 0 ; i < COUNT ; i++){
list.add(0,i);
}
long endTime = System.currentTimeMillis();
System.out.println("插入 " + COUNT + "元素" + getName(list) + "花费 " + (endTime - startTime) + " 毫秒");
}
public static void deleteFromList(List list){
long startTime = System.currentTimeMillis();
for(int i = 0 ; i < COUNT ; i++){
list.remove(0);
}
long endTime = System.currentTimeMillis();
System.out.println("删除" + COUNT + "元素" + getName(list) + "花费 " + (endTime - startTime) + " 毫秒");
}
public static void readList(List list){
long startTime = System.currentTimeMillis();
for(int i = 0 ; i < COUNT ; i++){
list.get(i);
}
long endTime = System.currentTimeMillis();
System.out.println("读取" + COUNT + "元素" + getName(list) + "花费 " + (endTime - startTime) + " 毫秒");
}
private static String getName(List list) {
String name = "";
if(list instanceof ArrayList){
name = "ArrayList";
}
else if(list instanceof LinkedList){
name = "LinkedList";
}
else if(list instanceof Vector){
name = "Vector";
}
return name;
}
public static void main(String[] args) {
insertToList(arrayList);
insertToList(linkedList);
insertToList(vector);
System.out.println("--------------------------------------");
readList(arrayList);
readList(linkedList);
readList(vector);
System.out.println("--------------------------------------");
deleteFromList(arrayList);
deleteFromList(linkedList);
deleteFromList(vector);
}
}插入 100000元素ArrayList花费 3900 毫秒
插入 100000元素LinkedList花费 15 毫秒
插入 100000元素Vector花费 3933 毫秒
--------------------------------------
读取100000元素ArrayList花费 0 毫秒
读取100000元素LinkedList花费 8877 毫秒
读取100000元素Vector花费 16 毫秒
--------------------------------------
删除100000元素ArrayList花费 4618 毫秒
删除100000元素LinkedList花费 16 毫秒
删除100000元素Vector花费 4759 毫秒
从上面的运行结果我们可以清晰的看出ArrayList、LinkedList、Vector增加、删除、遍历的效率问题。下面我就插入方法add(int index, E element),delete、get方法各位如有兴趣可以研究研究。
首先我们先看三者之间的源码：
ArrayList
public void add(int index, E element) {
rangeCheckForAdd(index); //检查是否index是否合法
ensureCapacityInternal(size + 1); //扩容操作
System.arraycopy(elementData, index, elementData, index + 1, size - index); //数组拷贝
elementData[index] = element; //插入
size++;
}rangeCheckForAdd、ensureCapacityInternal两个方法没有什么影响，真正产生影响的是System.arraycopy方法，该方法是个JNI函数，是在JVM中实现的。声明如下：
public static native void arraycopy(Object src, int srcPos, Object dest, int destPos, int length);
目前LZ无法看到源码，具体的实现不是很清楚，不过System.arraycopy源码分析对其进行了比较清晰的分析。但事实上我们只需要了解该方法会移动index后面的所有元素即可，这就意味着ArrayList的add(int index, E element)方法会引起index位置之后所有元素的改变，这真是牵一处而动全身。
LinkedList
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size) //插入位置在末尾
linkLast(element);
else
linkBefore(element, node(index));
}该方法比较简单，插入位置在末尾则调用linkLast方法，否则调用linkBefore方法，其实linkLast、linkBefore都是非常简单的实现，就是在index位置插入元素，至于index具体为知则有node方法来解决，同时node对index位置检索还有一个加速作用，如下：
Node<E> node(int index) {
if (index < (size >> 1)) { //如果index 小于 size/2 则从头开始查找
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else { //如果index 大于 size/2 则从尾部开始查找
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}所以linkedList的插入动作比ArrayList动作快就在于两个方面。1：linkedList不需要执行元素拷贝动作，没有牵一发而动全身的大动作。2:查找插入位置有加速动作即：若index < 双向链表长度的1/2，则从前向后查找; 否则，从后向前查找。
Vector
Vector的实现机制和ArrayList一样，同样是使用动态数组来实现的，所以他们两者之间的效率差不多，add的源码也一样，如下：
public void add(int index, E element) {
insertElementAt(element, index);
}
public synchronized void insertElementAt(E obj, int index) {
modCount++;
if (index > elementCount) {
throw new ArrayIndexOutOfBoundsException(index
+ " > " + elementCount);
}
ensureCapacityHelper(elementCount + 1);
System.arraycopy(elementData, index, elementData, index + 1, elementCount - index);
elementData[index] = obj;
elementCount++;
}上面是针对ArrayList、LinkedList、Vector三者之间的add（int index,E element)方法的解释，解释了LinkedList的插入动作要比ArrayList、Vector的插入动作效率为什么要高出这么多！至于delete、get两个方法LZ就不多解释了。
同时LZ在写上面那个例子时发现了一个非常有趣的现象，就是linkedList在某些时候执行add方法时比ArrayList方法会更慢！至于在什么情况？为什么会慢LZ下篇博客解释，当然不知道这个情况各位是否也遇到过？？
2.2、Vector和ArrayList的区别
四、更多
java提高篇（二一）-----ArrayList
java提高篇（二二）-----LinkedList
java提高篇（二九）-----Vector
Chapitre sur l'amélioration de Java (1er mars)-----Stack
et ci-dessus Ceci est le contenu résumé dans le chapitre sur l'amélioration de Java (32) ----- Liste Pour plus de contenu connexe, veuillez faire attention au site Web PHP chinois (www.php.cn) !