Java에서 ArrayList 및 LinkedList를 언제 사용합니까?

언제 ArrayList 또는 LinkedList를 사용해야 합니까?

ArrayList 및 LinkedList는 Java 컬렉션 프레임워크에 개체 참조 목록을 저장하는 데 사용되는 두 가지 클래스입니다. ArrayList와 LinkedList는 모두 List 인터페이스를 구현합니다. 먼저 List에 대해 간단히 이해해 봅시다:

리스트는 순서가 지정된 요소의 모음이며 시퀀스라고도 합니다. 목록의 특정 인덱스 위치에 있는 요소에 빠르게 액세스하고, 추가하고, 제거하는 데 도움이 되는 요소 위치 기반 작업을 제공합니다. List 인터페이스는 Collection 및 Iterable을 상위 인터페이스로 구현합니다. 중복 및 null 값을 저장할 수 있으며 인덱스를 통해 요소에 액세스할 수 있습니다.

이 기사를 읽은 후 명확히 해야 할 질문: ArrayList와 LinkedList의 차이점은 무엇입니까? 언제 ArrayList를 사용해야 하며 언제 LinkedList를 사용해야 합니까?

(추천 영상: java 영상 튜토리얼)

다음은 ArrayList와 LinkedList의 차이점을 비교하기 위해 요소를 추가하고 삭제하는 예입니다.

목록 끝에 요소를 추가하세요. :

ArrayList의 대기열 끝에 요소를 추가하는 코드는 다음과 같습니다.

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

ArrayList의 add() 메서드 성능은 ensureCapacity() 메서드에 따라 달라집니다. ensureCapacity()의 구현은 다음과 같습니다.

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

ArrayList의 현재 용량이 충분히 크면 add() 작업이 매우 효율적이라는 것을 알 수 있습니다. 확장은 ArrayList의 용량 요구 사항이 현재 배열 크기를 초과하는 경우에만 필요합니다. 확장 프로세스 중에는 수많은 어레이 복사 작업이 수행됩니다. 배열이 복사되면 결국 System.arraycopy() 메서드가 호출되므로 add() 작업의 효율성은 여전히 ​​상당히 높습니다.

LinkedList의 add() 작업은 다음과 같이 구현됩니다. 또한 대기열 끝에 모든 요소를 ​​추가합니다.

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

addBefore() 메서드는 다음과 같이 구현됩니다.

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

LinkeList를 볼 수 있습니다. 연결리스트 구조를 사용하므로 용량의 크기를 유지할 필요가 없습니다. 이러한 관점에서 볼 때 ArrayList에 비해 성능상 이점이 있습니다. 그러나 요소를 추가할 때마다 새로운 Entry 개체와 더 많은 할당 작업이 필요합니다. 빈번한 시스템 호출은 성능에 일정한 영향을 미칩니다.

목록의 원하는 위치에 요소 추가

목록 끝에 요소를 제공하는 것 외에도 List 인터페이스는 원하는 위치에 요소를 삽입할 수 있는 메서드도 제공합니다. void add(int index,E element);

이 방법에서는 구현 방법이 다르기 때문에 ArrayList와 LinkedList 간에는 일정한 성능 차이가 있습니다. ArrayList는 배열을 기반으로 구현되고 배열은 연속적인 메모리 공간이므로 배열의 임의 위치에 요소가 삽입되면 , 해당 위치 이후의 모든 요소는 필연적으로 재배열이 필요하므로 효율성이 상대적으로 낮습니다.

다음 코드는 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++;
}

삽입 작업마다 배열 복사가 수행되는 것을 볼 수 있습니다. 목록 끝에 요소를 추가하는 경우에는 이 작업이 존재하지 않습니다. 배열 재구성 작업이 많으면 시스템 성능이 저하됩니다. 삽입된 요소가 목록에 일찍 포함될수록 배열 재구성 비용이 커집니다.

그리고 LinkedList는 이때 장점을 보여줍니다.

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

LinkedList의 경우 List 끝에 데이터를 삽입하는 것은 임의의 위치에 데이터를 삽입하는 것과 동일하며, 삽입 위치가 빨라지면 성능이 저하됩니다.

모든 위치에서 요소 삭제

요소 삭제를 위해 List 인터페이스는 모든 위치에서 요소를 삭제할 수 있는 메서드를 제공합니다.

public E remove(int index);

ArrayList의 경우, 제거() 메서드와 add() 메서드는 동일합니다. 임의의 위치에서 요소를 제거한 후에는 배열을 재구성해야 합니다. ArrayList의 구현은 다음과 같습니다.

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

ArrayList에서 모든 효과적인 요소 삭제 작업 후에는 배열을 재구성해야 함을 알 수 있습니다. 그리고 삭제된 위치가 빠를수록 배열 재구성의 오버헤드가 커집니다.

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

LinkedList 구현에서는 먼저 루프를 통해 삭제할 요소를 찾아야 합니다. 삭제할 위치가 List의 전반부에 있으면 앞에서 뒤로 검색하고, 후반부에 있으면 뒤에서 앞으로 검색합니다. 따라서 이전 요소를 삭제하거나 이후 요소를 삭제하려는 경우 매우 효율적이지만 목록의 중간에 있는 요소를 제거하려면 목록에 요소 수가 많을 때 거의 절반을 순회해야 합니다. 효율성이 매우 낮습니다.

Capacity 매개변수

capacity 매개변수는 ArrayList 및 Vector와 같은 배열 기반 목록의 고유한 성능 매개변수입니다. 초기화된 배열 크기를 나타냅니다. ArrayList에 저장된 요소의 개수가 기존 크기를 초과하는 경우. 이는 확장될 것이며, 어레이의 확장으로 인해 전체 어레이의 메모리 사본이 생성됩니다. 따라서 합리적인 어레이 크기는 어레이 확장 횟수를 줄여 시스템 성능을 향상시키는 데 도움이 됩니다.

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

ArrayList는 초기 배열 크기를 지정할 수 있는 생성자를 제공합니다.

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

위 내용은 Java에서 ArrayList 및 LinkedList를 언제 사용합니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!