Wann werden ArrayList und LinkedList in Java verwendet?

Wann sollte ich ArrayList oder LinkedList verwenden?

ArrayList und LinkedList werden zum Speichern von Objekten in der Java-Sammlung verwendet Framework Zwei Klassen, die auf Listen verweisen. Sowohl ArrayList als auch LinkedList implementieren die List-Schnittstelle. Lassen Sie uns zunächst kurz die Liste verstehen:

Eine Liste ist eine geordnete Sammlung von Elementen, auch Sequenz genannt. Es bietet auf Elementpositionen basierende Operationen, mit denen Sie schnell auf Elemente an bestimmten Indexpositionen in der Liste zugreifen, diese hinzufügen und entfernen können. Die List-Schnittstelle implementiert Collection und Iterable als übergeordnete Schnittstellen. Es ermöglicht das Speichern doppelter Werte und Nullwerte und unterstützt den Zugriff auf Elemente über Indizes.

Fragen, die nach dem Lesen dieses Artikels geklärt werden müssen: Was sind die Unterschiede zwischen ArrayList und LinkedList? Wann sollten Sie ArrayList und wann LinkedList verwenden?

(Empfohlenes Video: Java-Video-Tutorial)

Unten hinzufügen Take das Beispiel des Löschens von Elementen, um die Unterschiede zwischen ArrayList und LinkedList zu vergleichen

Elemente am Ende der Liste hinzufügen:

Der Code zum Hinzufügen von Elementen am Ende der Die Warteschlange in ArrayList lautet wie folgt:

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

Die Leistung der add()-Methode in ArrayList hängt von der ensureCapacity()-Methode ab. Die Implementierung von ensureCapacity() lautet wie folgt:

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);
  }
}

Sie sehen, dass die Operation add() sehr effizient ist, solange die aktuelle Kapazität von ArrayList groß genug ist. Eine Erweiterung ist nur erforderlich, wenn die Kapazitätsanforderungen der ArrayList die aktuelle Array-Größe überschreiten. Während des Erweiterungsprozesses wird eine große Anzahl von Array-Kopiervorgängen ausgeführt. Wenn das Array kopiert wird, wird schließlich die Methode System.arraycopy() aufgerufen, sodass die Effizienz der Operation add() immer noch recht hoch ist.

Die add()-Operation von LinkedList wird wie folgt implementiert. Außerdem wird ein beliebiges Element am Ende der Warteschlange hinzugefügt:

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

Die addBefore()-Methode wird implementiert wie folgt:

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;
}

Es ist ersichtlich, dass LinkeList die Kapazitätsgröße nicht beibehalten muss, da es die Struktur einer verknüpften Liste verwendet. Unter diesem Gesichtspunkt bietet es gewisse Leistungsvorteile gegenüber ArrayList. Allerdings erfordert jedes Hinzufügen von Elementen ein neues Eintragsobjekt und mehr Zuweisungsvorgänge. Häufige Systemaufrufe haben einen gewissen Einfluss auf die Leistung.

Fügen Sie Elemente an einer beliebigen Position in der Liste hinzu

Zusätzlich zur Bereitstellung von Elementen am Ende der Liste bietet die Listenschnittstelle auch eine Methode zum Einfügen von Elementen an einer beliebigen Stelle position: void add(int index,E element);

Aufgrund unterschiedlicher Implementierungen gibt es bei dieser Methode gewisse Leistungsunterschiede zwischen ArrayList und LinkedList, da ArrayList auf Arrays basiert und Arrays ein kontinuierlicher Speicher sind Leerzeichen, wenn im Array Das Einfügen eines Elements an einer beliebigen Position führt unweigerlich dazu, dass alle Elemente nach dieser Position neu angeordnet werden, sodass die Effizienz relativ gering ist.

Der folgende Code ist in ArrayList implementiert:

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++;
}

Sie können sehen, dass jeder Einfügevorgang eine Array-Kopie verursacht. Dieser Vorgang ist nicht vorhanden, wenn Elemente am Ende der Liste hinzugefügt werden. Eine große Anzahl von Array-Reorganisationsvorgängen führt zu einer geringen Systemleistung. Und je früher das eingefügte Element in der Liste steht, desto höher sind die Kosten für die Array-Reorganisation.

Und LinkedList zeigt zu diesem Zeitpunkt seinen Vorteil:

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

Es ist ersichtlich, dass das Einfügen von Daten am Ende der Liste mit dem Einfügen von Daten an einer beliebigen Position identisch ist Der Einführvorgang wird aufgrund der Vorwärtsposition reduziert.

Elemente an jeder Position löschen

Zum Löschen von Elementen bietet die List-Schnittstelle eine Methode zum Löschen von Elementen an jeder Position:

public E remove(int index);

Für ArrayList , die Methode „remove()“ und die Methode „add()“ sind identisch. Nach dem Entfernen von Elementen an einer beliebigen Position muss das Array neu organisiert werden. Die Implementierung von ArrayList lautet wie folgt:

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;
}

Sie können sehen, dass nach jedem effektiven Elementlöschvorgang in ArrayList das Array neu organisiert werden muss. Und je früher die gelöschte Position liegt, desto größer ist der Aufwand für die Array-Reorganisation.

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;
}

Bei der Implementierung von LinkedList muss das zu löschende Element zunächst durch eine Schleife gefunden werden. Wenn die zu löschende Position in der ersten Hälfte der Liste liegt, suchen Sie von vorne nach hinten. Wenn die Position in der zweiten Hälfte liegt, suchen Sie von hinten nach vorne. Daher ist es sehr effizient, ob Sie die früheren oder späteren Elemente löschen möchten. Um jedoch die Elemente in der Mitte der Liste zu entfernen, müssen Sie fast die Hälfte der Liste durchlaufen Der Wirkungsgrad ist sehr gering.

Kapazitätsparameter

Der Kapazitätsparameter ist ein einzigartiger Leistungsparameter von Array-basierten Listen wie ArrayList und Vector. Es stellt die initialisierte Array-Größe dar. Wenn die Anzahl der in ArrayList gespeicherten Elemente die vorhandene Größe überschreitet. Es wird erweitert, und die Erweiterung des Arrays führt zu einer Speicherkopie des gesamten Arrays. Daher trägt eine angemessene Array-Größe dazu bei, die Anzahl der Array-Erweiterungen zu reduzieren und dadurch die Systemleistung zu verbessern.

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

ArrayList stellt einen Konstruktor bereit, der die anfängliche Array-Größe angeben kann:

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教程栏目，欢迎学习！  

Das obige ist der detaillierte Inhalt vonWann werden ArrayList und LinkedList in Java verwendet?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!