淺談ArrayList和LinkedList到底誰更快
更新時間：2021年06月10日 14:19:01 作者：偉衙內(nèi)
今天給大家?guī)淼氖顷P(guān)于Java的相關(guān)知識,文章圍繞著ArrayList和LinkedList到底誰更快展開,文中有非常詳細(xì)的介紹,需要的朋友可以參考下
一、ArrayList和LinkedList究竟誰快
在Java中應(yīng)該都知道ArrayList和LinkedList，
一直以來的概念呢是
ArrayList在get(index)這個應(yīng)該比LinkedList快；
LinkedList比ArrayList在add(index,element)快；
兩者共同遍歷呢，應(yīng)該是一樣快的，畢竟都要循環(huán)遍歷一遍。
直到我寫了一個測試類
package com.lw;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import org.junit.Test;
public class TestJDKList {
List<Integer> linkedList = new LinkedList<>();
List<Integer> arrayList = new ArrayList<>();
int length = 1000000;
@Test
public void testLinkedInsert(){
for (int i = 0; i < length; i++) {
linkedList.add(i);
}
long currentMi2 = System.currentTimeMillis();
linkedList.add(length/2,3);
long endTime2 = System.currentTimeMillis();
System.out.println("testLinkedInsert:" + (endTime2 - currentMi2)); // 9
}
@Test
public void testArrayInsert(){
for (int i = 0; i < length; i++) {
arrayList.add(i);
}
long currentMi2 = System.currentTimeMillis();
arrayList.add(length/2,3);
long endTime2 = System.currentTimeMillis();
System.out.println("testArrayInsert:" + (endTime2 - currentMi2)); // 1
}
@Test
public void testLinkedGet(){
for (int i = 0; i < length; i++) {
linkedList.add(i);
}
long currentMi2 = System.currentTimeMillis();
linkedList.get(length/2);
long endTime2 = System.currentTimeMillis();
System.out.println("testLinkedGet:" + (endTime2 - currentMi2)); // 5
}
@Test
public void testArrayGet(){
for (int i = 0; i < length; i++) {
arrayList.add(i);
}
long currentMi2 = System.currentTimeMillis();
arrayList.get(length/2);
long endTime2 = System.currentTimeMillis();
System.out.println("testArrayGet:" + (endTime2 - currentMi2)); // 0
}
@Test
public void testLinkedIter(){
for (int i = 0; i < length; i++) {
linkedList.add(i);
}
long currentMi2 = System.currentTimeMillis();
for (Integer i : linkedList) {
};
long endTime2 = System.currentTimeMillis();
System.out.println("testLinkedIter:" + (endTime2 - currentMi2)); // 26
}
@Test
public void testArrayIter(){
for (int i = 0; i < length; i++) {
arrayList.add(i);
}
long currentMi2 = System.currentTimeMillis();
for (Integer i : arrayList) {
};
long endTime2 = System.currentTimeMillis();
System.out.println("testArrayIter:" + (endTime2 - currentMi2)); // 11
}
@Test
public void testLinkedAdd() {
long currentMi2 = System.currentTimeMillis();
for (int i = 0; i < length; i++) {
linkedList.add(i);
}
long endTime2 = System.currentTimeMillis();
System.out.println("testLinkedAdd:" + (endTime2 - currentMi2)); // 53
}
@Test
public void testArrayAdd(){
long currentMi1 = System.currentTimeMillis();
for (int i = 0; i < length; i++) {
arrayList.add(i);
}
long endTime1 = System.currentTimeMillis();
System.out.println("testArrayAdd:" + (endTime1 - currentMi1)); // 35
}
}
二、結(jié)果
運行了兩遍結(jié)果如下：
testLinkedInsert:7
testArrayInsert:0
testLinkedAdd:218
testArrayAdd:23
testLinkedGet:4
testArrayGet:0
testLinkedIter:14
testArrayIter:11
----------------第二遍分割線---------------------------------
testLinkedInsert:12
testArrayInsert:0
testLinkedIter:13
testArrayIter:12
testLinkedGet:3
testArrayGet:0
testLinkedAdd:119
testArrayAdd:23
顛覆三觀，ArrayList竟然無論怎樣都比LinkedList快？？
三、循環(huán)Add
ArrayList的add源碼，它是把數(shù)據(jù)放在一個數(shù)組中
transient Object[] elementData;
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
而LinkedList源碼，是把數(shù)據(jù)放在Node對象中，有個前后指針。
public boolean add(E e) {
linkLast(e);
return true;
}
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
難道是前后指針這里花時間了么？
四、指定位置Get
再看get方法，
ArrayList的get，因為是連續(xù)的內(nèi)存，所以取數(shù)據(jù)很快。
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
E elementData(int index) {
return (E) elementData[index];
}
再看LinkedList的get，是通過指針遍歷的，直到是這個index為止。
這里還有判斷size，如果是size的前一半，則通過first節(jié)點往后去找，如果在后一半則通過last節(jié)點往前找，這樣會更快，所以LinkedList的查找其實也不慢。
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
Node<E> node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
五、指定位置Add
ArrayList的add(index,element)
這里是可以擴(kuò)容的，將index后半段拷貝到index+1，然后在index插入一個新的，但沒想到這么快。
其實也能想到System.arraycopy是native，所以快也能理解
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
然后是LinkedList的add(index,element)
無非是指針的指向變化而已，但沒想到比上面的System.arraycopy還要慢，果然不愧為native方法。
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
final Node<E> pred = succ.prev;
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
所以項目中大部分用ArrayList也就是可以理解。
不過ArrayList是連續(xù)的內(nèi)存空間，在內(nèi)存空間很緊張情況下，LinkedList內(nèi)存利用率更高。
到此這篇關(guān)于淺談ArrayList和LinkedList到底誰更快的文章就介紹到這了,更多相關(guān)ArrayList和LinkedList內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
您可能感興趣的文章:
- java中ArrayList和LinkedList的區(qū)別詳解
- 區(qū)分Java中的ArrayList和LinkedList
- java 集合之實現(xiàn)類ArrayList和LinkedList的方法
- Java中ArrayList和LinkedList之間的區(qū)別_動力節(jié)點Java學(xué)院整理
- java中ArrayList與LinkedList對比詳情
- java 中ArrayList與LinkedList性能比較
- Java中ArrayList和LinkedList的遍歷與性能分析
- 分析Java中ArrayList與LinkedList列表結(jié)構(gòu)的源碼
- 淺談 java中ArrayList、Vector、LinkedList的區(qū)別聯(lián)系
- JAVA LinkedList和ArrayList的使用及性能分析
相關(guān)文章
Spring源碼如何修改Bean的屬性用到的相關(guān)類
這篇文章主要介紹了Spring源碼如何修改Bean的屬性用到的相關(guān)類,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2024-05-05
本篇文章主要介紹了Spring依賴注入的三種方式小結(jié)，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-08-08
java實現(xiàn)統(tǒng)計字符串中字符及子字符串個數(shù)的方法示例
這篇文章主要介紹了java實現(xiàn)統(tǒng)計字符串中字符及子字符串個數(shù)的方法,涉及java針對字符串的遍歷、判斷及運算相關(guān)操作技巧,需要的朋友可以參考下2017-01-01
這篇文章主要介紹了SpringBoot?常用讀取配置文件的3種方法,通過本文學(xué)習(xí)可以解決Spring Boot有哪些常用的讀取配置文件方式，一些復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，如list，map如何配置，帶著這些問題一起通過本文學(xué)習(xí)吧2022-09-09
Spring Cloud超詳細(xì)i講解Feign自定義配置與使用
這篇文章主要介紹了SpringCloud Feign自定義配置與使用,本文通過實例代碼給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2022-06-06
Java編程實現(xiàn)獲取當(dāng)前代碼行行號的方法示例
這篇文章主要介紹了Java編程實現(xiàn)獲取當(dāng)前代碼行行號的方法,結(jié)合實例形式分析了java基于StackTraceElement對象實現(xiàn)獲取代碼行號的相關(guān)操作技巧,需要的朋友可以參考下2017-08-08
Java的BigInteger類用于處理超出int和long范圍的大整數(shù),而BigDecimal類則用于高精度的浮點數(shù)運算,這兩個類都是Number的子類,提供了一系列方法執(zhí)行加減乘除等運算,BigInteger不支持表示小數(shù),只能表示整數(shù),BigDecimal可以控制小數(shù)位數(shù)和舍入方式,感興趣的朋友一起看看吧2024-10-10
這篇文章主要介紹了 Android 判斷真機和模擬器的方法的相關(guān)資料,需要的朋友可以參考下2017-02-02
本文通過實例代碼給大家介紹了Spring FTP上傳下載工具類遇到問題小結(jié)，非常不錯，具有參考借鑒價值，需要的朋友參考下吧2017-12-12
springboot的maven多模塊混淆jar包的實現(xiàn)方法
springboot可以使用proguard-maven-plugin 這個插件 在 pom.xml 中自定義proguard 的指令,本文基于 springboot + maven + proguard 的maven多模塊架構(gòu)進(jìn)行代碼混淆,需要的朋友可以參考下2024-03-03