search
HomeJavajavaTutorialWhen to use ArrayList and LinkedList in java?
When to use ArrayList and LinkedList in java?Nov 28, 2019 pm 04:10 PM
arraylistlinkedlist

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,使用以上代码进行测试,测试结果:

When to use ArrayList and LinkedList in java?

什么情况用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!

Statement
This article is reproduced at:博客园. If there is any infringement, please contact admin@php.cn delete
Java ArrayList遍历时使用foreach和iterator删除元素的区别是什么?Java ArrayList遍历时使用foreach和iterator删除元素的区别是什么?Apr 27, 2023 pm 03:40 PM

一、Iterator和foreach的区别多态差别(foreach底层就是Iterator)Iterator是一个接口类型,他不关心集合或者数组的类型;for和foreach都需要先知道集合的类型,甚至是集合内元素的类型;1.为啥说foreach底层就是Iterator编写的代码:反编译代码:二、foreach与iterator时remove的区别先来看阿里java开发手册但1的时候不会报错,2的时候就会报错(java.util.ConcurrentModificationException)首

如何在Java中检查ArrayList是否包含某个元素?如何在Java中检查ArrayList是否包含某个元素?Sep 03, 2023 pm 04:09 PM

您可以利用List接口的contains()方法来检查列表中是否存在对象。contains()方法booleancontains(Objecto)如果此列表包含指定的元素,则返回true。更正式地说,如果且仅当此列表包含至少一个元素e,使得(o==null?e==null:o.equals(e)),则返回true。参数c-要测试其在此列表中是否存在的元素。返回值如果此列表包含指定的元素,则返回true。抛出ClassCastException-如果指定元素的类型与此列表不兼容(可选)。NullP

使用LinkedList类的removeLast()方法删除链表中的最后一个元素使用LinkedList类的removeLast()方法删除链表中的最后一个元素Jul 24, 2023 pm 05:13 PM

使用LinkedList类的removeLast()方法删除链表中的最后一个元素LinkedList是Java集合框架中常见的一种数据结构,它以双向链表的形式存储元素。通过LinkedList类提供的方法,我们可以方便地对链表进行操作,例如添加、删除和修改元素。在某些场景下,我们可能需要删除链表中的最后一个元素。LinkedList类提供了removeLas

使用java的ArrayList.remove()函数移除ArrayList中的元素使用java的ArrayList.remove()函数移除ArrayList中的元素Jul 24, 2023 pm 01:21 PM

使用java的ArrayList.remove()函数移除ArrayList中的元素在Java中,ArrayList是一种常用的集合类,用于储存和操作一组元素。ArrayList类提供了许多方法来增删改查集合中的元素。其中一个使用频率较高的方法是remove(),它可以移除ArrayList中的元素。ArrayList的remove()方法有两种重载形式,一

使用java的ArrayList.clear()函数清空ArrayList中的元素使用java的ArrayList.clear()函数清空ArrayList中的元素Jul 24, 2023 pm 02:04 PM

使用Java的ArrayList.clear()函数清空ArrayList中的元素在Java编程中,ArrayList是一种非常常用的数据结构,它可以动态地存储和访问元素。然而,在某些情况下,我们可能需要清空ArrayList中的所有元素,以便重新使用或释放内存。这时,就可以使用ArrayList的clear()函数来实现。ArrayList.clear()

Java中ArrayList初始化容量大小为10的原因是什么Java中ArrayList初始化容量大小为10的原因是什么May 10, 2023 pm 02:19 PM

为什么HashMap的初始化容量为16?在聊ArrayList的初始化容量时,要先来回顾一下HashMap的初始化容量。这里以Java8源码为例,HashMap中的相关因素有两个:初始化容量及装载因子:/***Thedefaultinitialcapacity-MUSTbeapoweroftwo.*/staticfinalintDEFAULT_INITIAL_CAPACITY=1>1);if(newCapacity-minCapacity0)newCapacity=hugeCapacity

Java使用ArrayList类的contains()函数判断元素是否存在Java使用ArrayList类的contains()函数判断元素是否存在Jul 24, 2023 pm 07:33 PM

Java使用ArrayList类的contains()函数判断元素是否存在在Java编程中,ArrayList是一个非常常用的数据结构。它提供了一种灵活的方法来存储和操作一组数据。除了简单的添加、删除和访问元素之外,ArrayList还提供了一些有用的方法,例如contains()函数,用于判断元素是否存在于ArrayList中。contains()函数是A

在Java中从ArrayList获取唯一值在Java中从ArrayList获取唯一值Sep 04, 2023 am 08:41 AM

ArrayListisaclassofJavaCollectionFrameworkthatimplementsListInterface.Itisalinearstructurethatstoresandaccesseseachelementsequentially.Itallowsthestorageofduplicateelementshowever,thereareafewapproachesthatmayhelptogetuniquevaluesfromanArrayList.Inth

See all articles

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

AI Hentai Generator

AI Hentai Generator

Generate AI Hentai for free.

Hot Article

R.E.P.O. Energy Crystals Explained and What They Do (Yellow Crystal)
2 weeks agoBy尊渡假赌尊渡假赌尊渡假赌
Repo: How To Revive Teammates
4 weeks agoBy尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island Adventure: How To Get Giant Seeds
3 weeks agoBy尊渡假赌尊渡假赌尊渡假赌

Hot Tools

ZendStudio 13.5.1 Mac

ZendStudio 13.5.1 Mac

Powerful PHP integrated development environment

SAP NetWeaver Server Adapter for Eclipse

SAP NetWeaver Server Adapter for Eclipse

Integrate Eclipse with SAP NetWeaver application server.

EditPlus Chinese cracked version

EditPlus Chinese cracked version

Small size, syntax highlighting, does not support code prompt function

DVWA

DVWA

Damn Vulnerable Web App (DVWA) is a PHP/MySQL web application that is very vulnerable. Its main goals are to be an aid for security professionals to test their skills and tools in a legal environment, to help web developers better understand the process of securing web applications, and to help teachers/students teach/learn in a classroom environment Web application security. The goal of DVWA is to practice some of the most common web vulnerabilities through a simple and straightforward interface, with varying degrees of difficulty. Please note that this software

Atom editor mac version download

Atom editor mac version download

The most popular open source editor