Quand utiliser ArrayList et LinkedList en Java ?

Quand dois-je utiliser ArrayList ou LinkedList ?

ArrayList et LinkedList sont utilisés pour stocker des objets dans la collection Java framework Deux classes qui référencent des listes. ArrayList et LinkedList implémentent l'interface List. Commençons par une brève compréhension de la liste :

Une liste est une collection ordonnée d'éléments, également appelée séquence. Il fournit des opérations basées sur la position des éléments qui permettent d'accéder, d'ajouter et de supprimer rapidement des éléments à des positions d'index spécifiques dans la liste. L'interface List implémente Collection et Iterable comme interfaces parents. Il permet de stocker des valeurs en double et nulles et prend en charge l'accès aux éléments via des index.

Questions à clarifier après avoir lu cet article : Quelles sont les différences entre ArrayList et LinkedList ? Quand devez-vous utiliser ArrayList et quand devez-vous utiliser LinkedList ?

(Vidéo recommandée : tutoriel vidéo Java)

Ajouter ci-dessous Prendre l'exemple de suppression d'éléments pour comparer les différences entre ArrayList et LinkedList

Ajouter des éléments à la fin de la liste :

Le code pour ajouter des éléments à la fin de la la file d'attente dans ArrayList est la suivante :

public boolean add(E e){
   ensureCapacity(size+1);//确保内部数组有足够的空间
   elementData[size++]=e;//将元素加入到数组的末尾，完成添加
   return true;      
}

Les performances de la méthode add() dans ArrayList dépendent de la méthode ensureCapacity(). L'implémentation de ensureCapacity() est la suivante :

public vod ensureCapacity(int minCapacity){
  modCount++;
  int oldCapacity=elementData.length;
  if(minCapacity>oldCapacity){    //如果数组容量不足，进行扩容
      Object[] oldData=elementData;
      int newCapacity=(oldCapacity*3)/2+1;  //扩容到原始容量的1.5倍
      if(newCapacitty<minCapacity)   //如果新容量小于最小需要的容量，则使用最小
                                                    //需要的容量大小
         newCapacity=minCapacity ;  //进行扩容的数组复制
         elementData=Arrays.copyof(elementData,newCapacity);
  }
}

Vous pouvez voir que tant que la capacité actuelle d'ArrayList est suffisamment grande, l'opération add() est très efficace. L'expansion n'est requise que lorsque les exigences de capacité d'ArrayList dépassent la taille actuelle du tableau. Au cours du processus d'expansion, un grand nombre d'opérations de copie de tableau seront effectuées. Lorsque le tableau est copié, la méthode System.arraycopy() sera finalement appelée, donc l'efficacité de l'opération add() est encore assez élevée.

L'opération add() de LinkedList est implémentée comme suit. Elle ajoute également n'importe quel élément à la fin de la file d'attente :

public boolean add(E e){
   addBefore(e,header);//将元素增加到header的前面
   return true;
}

La méthode addBefore() est implémentée. comme suit :

private Entry<E> addBefore(E e,Entry<E> entry){
     Entry<E> newEntry = new Entry<E>(e,entry,entry.previous);
     newEntry.provious.next=newEntry;
     newEntry.next.previous=newEntry;
     size++;
     modCount++;
     return newEntry;
}

On voit que LinkeList n'a pas besoin de maintenir la taille de la capacité car elle utilise la structure d'une liste chaînée. De ce point de vue, il présente certains avantages en termes de performances par rapport à ArrayList. Cependant, chaque ajout d'éléments nécessite un nouvel objet Entry et davantage d'opérations d'affectation. Les appels système fréquents auront un certain impact sur les performances.

Ajouter des éléments à n'importe quelle position de la liste

En plus de fournir des éléments à la fin de la liste, l'interface List fournit également une méthode pour insérer des éléments à n'importe quelle position. position: void add(int index,E element);

En raison de différentes implémentations, il existe certaines différences de performances entre ArrayList et LinkedList dans cette méthode puisque ArrayList est implémenté sur la base de tableaux et que les tableaux sont une mémoire continue. espace, si dans le tableau L'insertion d'un élément à n'importe quelle position entraînera inévitablement la réorganisation de tous les éléments après cette position, son efficacité sera donc relativement faible.

Le code suivant est implémenté dans ArrayList :

public void add(int index,E element){
   if(index>size||index<0)
      throw new IndexOutOfBoundsException(
        "Index:"+index+",size: "+size);
         ensureCapacity(size+1);
         System.arraycopy(elementData,index,elementData,index+1,size-index);
         elementData[index] = element;
         size++;
}

Vous pouvez voir que chaque opération d'insertion provoquera une copie du tableau. Cette opération n'existe pas lors de l'ajout d'éléments à la fin de la liste. Un grand nombre d'opérations de réorganisation du tableau entraîneront de faibles performances du système. Et plus l’élément inséré apparaît tôt dans la liste, plus le coût de réorganisation du tableau est élevé.

Et LinkedList montre son avantage à ce moment :

public void add(int index,E element){
   addBefore(element,(index==size?header:entry(index)));
}

On peut voir que pour LinkedList, insérer des données à la fin de la liste équivaut à insérer des données à n'importe quelle position. de la méthode d'insertion est réduite en raison de la position avancée.

Supprimer des éléments à n'importe quelle position

Pour la suppression d'éléments, l'interface List fournit une méthode pour supprimer des éléments à n'importe quelle position :

public E remove(int index);

Pour ArrayList , la méthode remove() et la méthode add() sont identiques. Après avoir supprimé des éléments à n'importe quelle position, le tableau doit être réorganisé. L'implémentation d'ArrayList est la suivante :

public E remove(int index){
   RangeCheck(index);
   modCount++;
   E oldValue=(E) elementData[index];
  int numMoved=size-index-1;
  if(numMoved>0)
     System.arraycopy(elementData,index+1,elementData,index,numMoved);
     elementData[--size]=null;
     return oldValue;
}

Vous pouvez voir qu'après chaque opération efficace de suppression d'élément dans ArrayList, le tableau doit être réorganisé. Et plus la position supprimée est précoce, plus la surcharge de réorganisation du tableau est importante.

public E remove(int index){
  return remove(entry(index));         
}
private Entry<E> entry(int index){
  if(index<0 || index>=size)
      throw new IndexOutBoundsException("Index:"+index+",size:"+size);
      Entry<E> e= header;
      if(index<(size>>1)){//要删除的元素位于前半段
         for(int i=0;i<=index;i++)
             e=e.next;
     }else{
         for(int i=size;i>index;i--)
             e=e.previous;
     }
         return e;
}

Dans l'implémentation de LinkedList, vous devez d'abord trouver l'élément à supprimer via une boucle. Si la position à supprimer se trouve dans la première moitié de la Liste, recherchez de l'avant vers l'arrière ; si la position est dans la seconde moitié, recherchez de l'arrière vers l'avant. Par conséquent, il est très efficace que vous souhaitiez supprimer les éléments antérieurs ou ultérieurs ; mais pour supprimer les éléments au milieu de la Liste, vous devez parcourir près de la moitié de la Liste. Lorsque la Liste contient un grand nombre d'éléments, le l'efficacité est très faible.

Paramètre de capacité

Le paramètre de capacité est un paramètre de performance unique des listes basées sur des tableaux telles que ArrayList et Vector. Il représente la taille du tableau initialisé. Lorsque le nombre d'éléments stockés dans ArrayList dépasse sa taille existante. Il s'étendra et l'expansion du tableau entraînera une copie mémoire de l'ensemble du tableau. Par conséquent, une taille de baie raisonnable permet de réduire le nombre d’extensions de baie, améliorant ainsi les performances du système.

public  ArrayList(){
  this(10);  
}
public ArrayList (int initialCapacity){
   super();
   if(initialCapacity<0)
       throw new IllegalArgumentException("Illegal Capacity:"+initialCapacity)
      this.elementData=new Object[initialCapacity];
}

ArrayList fournit un constructeur qui peut spécifier la taille initiale du tableau :

public ArrayList(int initialCapacity)

现以构造一个拥有100万元素的List为例，当使用默认初始化大小时，其消耗的相对时间为125ms左右，当直接制定数组大小为100万时，构造相同的ArrayList仅相对耗时16ms。

遍历列表

遍历列表操作是最常用的列表操作之一，在JDK1.5之后，至少有3中常用的列表遍历方式：

● forEach操作

● 迭代器

● for循环。

String tmp;
long start=System.currentTimeMills();    //ForEach 
for(String s:list){
    tmp=s;
}
System.out.println("foreach spend:"+(System.currentTimeMills()-start));
start = System.currentTimeMills();
for(Iterator<String> it=list.iterator();it.hasNext();){    
   tmp=it.next();
}
System.out.println("Iterator spend;"+(System.currentTimeMills()-start));
start=System.currentTimeMills();
int size=;list.size();
for(int i=0;i<size;i++){                     
    tmp=list.get(i);
}
System.out.println("for spend;"+(System.currentTimeMills()-start));

构造一个拥有100万数据的ArrayList和等价的LinkedList，使用以上代码进行测试，测试结果：

什么情况用ArrayList or LinkedList呢?

可以看到，最简便的ForEach循环并没有很好的性能表现，综合性能不如普通的迭代器，而是用for循环通过随机访问遍历列表时，ArrayList表项很好，但是LinkedList的表现却无法让人接受，甚至没有办法等待程序的结束。这是因为对LinkedList进行随机访问时，总会进行一次列表的遍历操作。性能非常差，应避免使用。

总结

ArrayList和LinkedList在性能上各有优缺点，都有各自所适用的地方，总的说来可以描述如下：

1．对ArrayList和LinkedList而言，在列表末尾增加一个元素所花的开销都是固定的。

对ArrayList而言，主要是在内部数组中增加一项，指向所添加的元素，偶尔可能会导致对数组重新进行分配；

而对LinkedList而言，这个开销是统一的，分配一个内部Entry对象。

2．在ArrayList的中间插入或删除一个元素意味着这个列表中剩余的元素都会被移动；而在LinkedList的中间插入或删除一个元素的开销是固定的。

3．LinkedList不支持高效的随机元素访问。

4．ArrayList的空间浪费主要体现在在list列表的结尾预留一定的容量空间，而LinkedList的空间花费则体现在它的每一个元素都需要消耗相当的空间

本文来自php中文网，java教程栏目，欢迎学习！  

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!