When to use ArrayList and LinkedList in java?

When should we use ArrayList or LinkedList?

ArrayList and LinkedList are used to store objects in the Java collection framework Two classes that reference lists. Both ArrayList and LinkedList implement the List interface. Let’s first have a brief understanding of List:

A list (list) is an ordered collection of elements, also called a sequence. It provides element position-based operations that help to quickly access, add, and remove elements at specific index positions in the list. The List interface implements Collection and Iterable as parent interfaces. It allows storing duplicate and null values, and supports accessing elements through indexes.

Questions to clarify after reading this article: What are the differences between ArrayList and LinkedList? When should you use ArrayList and when should you use LinkedList?

(Recommended video: java video tutorial)

Add the following Take the example of deleting elements to compare the differences between ArrayList and LinkedList

Add elements to the end of the list:

The code for adding elements to the end of the queue in ArrayList is as follows:

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

The performance of the add() method in ArrayList is determined by the ensureCapacity() method. The implementation of ensureCapacity() is as follows:

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

It can be seen that as long as the current capacity of ArrayList is large enough, the add() operation is very efficient. Expansion is only required when the ArrayList's capacity requirements exceed the current array size. During the expansion process, a large number of array copy operations will be performed. When the array is copied, the System.arraycopy() method will eventually be called, so the efficiency of the add() operation is still quite high.

The add() operation of LinkedList is implemented as follows. It also adds any element to the end of the queue:

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

The addBefore() method is implemented as follows:

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

It can be seen that LinkeList does not need to maintain the size of the capacity because it uses the structure of a linked list. From this point of view, it has certain performance advantages over ArrayList. However, each addition of elements requires a new Entry object and more assignment operations. Frequent system calls will have a certain impact on performance.

Add elements to any position in the list

In addition to providing elements to the end of the List, the List interface also provides a method to insert elements at any position: void add(int index,E element);

Due to different implementations, there are certain performance differences between ArrayList and LinkedList in this method. Since ArrayList is implemented based on arrays, and arrays are a continuous memory space, if in the array Inserting an element at any position will inevitably cause all elements after that position to be rearranged, so its efficiency will be relatively low.

The following code is the implementation in 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++;
}

You can see that each insertion operation will cause an array copy. This operation does not exist when adding elements to the end of the List. A large number of array reorganization operations will lead to low system performance. And the earlier the inserted element is in the List, the greater the cost of array reorganization.

And LinkedList shows its advantage at this time:

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

It can be seen that for LinkedList, inserting data at the end of the List is the same as inserting data at any position, and it will not be affected by the inserted data. The performance of the insertion method is reduced due to the forward position.

Delete elements at any position

For deletion of elements, the List interface provides a method to delete elements at any position:

public E remove(int index);

For ArrayList , the remove() method and the add() method are the same. After removing elements at any position, the array must be reorganized. The implementation of ArrayList is as follows:

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

It can be seen that after every effective element deletion operation in ArrayList, the array must be reorganized. And the earlier the deleted position is, the greater the overhead of array reorganization.

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

In the implementation of LinkedList, the element to be deleted must first be found through looping. If the position to be deleted is in the first half of the List, search from front to back; if the position is in the second half, search from back to front. Therefore, it is very efficient whether you want to delete the earlier or later elements; but to remove the elements in the middle of the List, you have to traverse almost half of the List. When the List has a large number of elements, the efficiency is very low.

Capacity parameter

The capacity parameter is a unique performance parameter of array-based Lists such as ArrayList and Vector. It represents the initialized array size. When the number of elements stored in ArrayList exceeds its existing size. It will expand, and the expansion of the array will cause a memory copy of the entire array. Therefore, a reasonable array size helps reduce the number of array expansions, thereby improving system performance.

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

ArrayList provides a constructor that can specify the initial array size:

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

The above is the detailed content of When to use ArrayList and LinkedList in java?. For more information, please follow other related articles on the PHP Chinese website!