欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

淺談ArrayList和LinkedList到底誰更快

 更新時(shí)間:2021年06月10日 14:19:01   作者:偉衙內(nèi)  
今天給大家?guī)淼氖顷P(guān)于Java的相關(guān)知識(shí),文章圍繞著ArrayList和LinkedList到底誰更快展開,文中有非常詳細(xì)的介紹,需要的朋友可以參考下

一、ArrayList和LinkedList究竟誰快

在Java中應(yīng)該都知道ArrayList和LinkedList,

一直以來的概念呢是

ArrayList在get(index)這個(gè)應(yīng)該比LinkedList快;

LinkedList比ArrayList在add(index,element)快;

兩者共同遍歷呢,應(yīng)該是一樣快的,畢竟都要循環(huán)遍歷一遍。

直到我寫了一個(gè)測試類

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é)果

運(yùn)行了兩遍結(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ù)放在一個(gè)數(shù)組中

transient Object[] elementData;
public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

而LinkedList源碼,是把數(shù)據(jù)放在Node對(duì)象中,有個(gè)前后指針。

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

難道是前后指針這里花時(shí)間了么?

四、指定位置Get

再看get方法,

ArrayList的get,因?yàn)槭沁B續(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,是通過指針遍歷的,直到是這個(gè)index為止。

這里還有判斷size,如果是size的前一半,則通過first節(jié)點(diǎn)往后去找,如果在后一半則通過last節(jié)點(diǎn)往前找,這樣會(huì)更快,所以LinkedList的查找其實(shí)也不慢。

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插入一個(gè)新的,但沒想到這么快。

其實(shí)也能想到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++;
    }

所以項(xiàng)目中大部分用ArrayList也就是可以理解。

不過ArrayList是連續(xù)的內(nèi)存空間,在內(nèi)存空間很緊張情況下,LinkedList內(nèi)存利用率更高。

到此這篇關(guān)于淺談ArrayList和LinkedList到底誰更快的文章就介紹到這了,更多相關(guān)ArrayList和LinkedList內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • Spring源碼如何修改Bean的屬性用到的相關(guān)類

    Spring源碼如何修改Bean的屬性用到的相關(guān)類

    這篇文章主要介紹了Spring源碼如何修改Bean的屬性用到的相關(guān)類,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教
    2024-05-05
  • Spring依賴注入的三種方式小結(jié)

    Spring依賴注入的三種方式小結(jié)

    本篇文章主要介紹了Spring依賴注入的三種方式小結(jié),小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,也給大家做個(gè)參考。一起跟隨小編過來看看吧
    2017-08-08
  • java實(shí)現(xiàn)統(tǒng)計(jì)字符串中字符及子字符串個(gè)數(shù)的方法示例

    java實(shí)現(xiàn)統(tǒng)計(jì)字符串中字符及子字符串個(gè)數(shù)的方法示例

    這篇文章主要介紹了java實(shí)現(xiàn)統(tǒng)計(jì)字符串中字符及子字符串個(gè)數(shù)的方法,涉及java針對(duì)字符串的遍歷、判斷及運(yùn)算相關(guān)操作技巧,需要的朋友可以參考下
    2017-01-01
  • SpringBoot?常用讀取配置文件的三種方法詳解

    SpringBoot?常用讀取配置文件的三種方法詳解

    這篇文章主要介紹了SpringBoot?常用讀取配置文件的3種方法,通過本文學(xué)習(xí)可以解決Spring Boot有哪些常用的讀取配置文件方式,一些復(fù)雜的數(shù)據(jù)結(jié)構(gòu),如list,map如何配置,帶著這些問題一起通過本文學(xué)習(xí)吧
    2022-09-09
  • Spring Cloud超詳細(xì)i講解Feign自定義配置與使用

    Spring Cloud超詳細(xì)i講解Feign自定義配置與使用

    這篇文章主要介紹了SpringCloud Feign自定義配置與使用,本文通過實(shí)例代碼給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下
    2022-06-06
  • Java編程實(shí)現(xiàn)獲取當(dāng)前代碼行行號(hào)的方法示例

    Java編程實(shí)現(xiàn)獲取當(dāng)前代碼行行號(hào)的方法示例

    這篇文章主要介紹了Java編程實(shí)現(xiàn)獲取當(dāng)前代碼行行號(hào)的方法,結(jié)合實(shí)例形式分析了java基于StackTraceElement對(duì)象實(shí)現(xiàn)獲取代碼行號(hào)的相關(guān)操作技巧,需要的朋友可以參考下
    2017-08-08
  • JAVA 中的大數(shù)字操作類詳解

    JAVA 中的大數(shù)字操作類詳解

    Java的BigInteger類用于處理超出int和long范圍的大整數(shù),而BigDecimal類則用于高精度的浮點(diǎn)數(shù)運(yùn)算,這兩個(gè)類都是Number的子類,提供了一系列方法執(zhí)行加減乘除等運(yùn)算,BigInteger不支持表示小數(shù),只能表示整數(shù),BigDecimal可以控制小數(shù)位數(shù)和舍入方式,感興趣的朋友一起看看吧
    2024-10-10
  • Android 判斷真機(jī)和模擬器的方法

    Android 判斷真機(jī)和模擬器的方法

    這篇文章主要介紹了 Android 判斷真機(jī)和模擬器的方法的相關(guān)資料,需要的朋友可以參考下
    2017-02-02
  • Spring FTP上傳下載工具類遇到問題小結(jié)

    Spring FTP上傳下載工具類遇到問題小結(jié)

    本文通過實(shí)例代碼給大家介紹了Spring FTP上傳下載工具類遇到問題小結(jié),非常不錯(cuò),具有參考借鑒價(jià)值,需要的朋友參考下吧
    2017-12-12
  • springboot的maven多模塊混淆jar包的實(shí)現(xiàn)方法

    springboot的maven多模塊混淆jar包的實(shí)現(xiàn)方法

    springboot可以使用proguard-maven-plugin 這個(gè)插件 在 pom.xml 中自定義proguard 的指令,本文基于 springboot + maven + proguard 的maven多模塊架構(gòu)進(jìn)行代碼混淆,需要的朋友可以參考下
    2024-03-03

最新評(píng)論