最新国产好看的视频,伊人天堂AV在线,国产Aaaaaa视频,蜜臀视频在线观看一区,人妻av色图,密臀久久久精品影片,青青视频免费观看毛片,久草在线观看视,国产三级精品色情在线

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

運(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ù)放在一個數(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)文章希望大家以后多多支持腳本之家！

  • SpringBoot集成WebSocket【基于純H5】進(jìn)行點對點[一對一]和廣播[一對多]實時推送

    SpringBoot集成WebSocket【基于純H5】進(jìn)行點對點[一對一]和廣播[一對多]實時推送

    這篇文章主要介紹了SpringBoot集成WebSocket【基于純H5】進(jìn)行點對點[一對一]和廣播[一對多]實時推送，具有一定的參考價值，感興趣的小伙伴們可以參考一下
    2018-08-08
  • Mybatis-Plus中分頁插件PaginationInterceptor的使用

    Mybatis-Plus中分頁插件PaginationInterceptor的使用

    我們在開發(fā)的過程中，經(jīng)常會遇到分頁操作，本文主要介紹了Mybatis-Plus中分頁插件PaginationInterceptor的使用，文中通過示例代碼介紹的非常詳細(xì)，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2023-06-06
  • 教你如何正確了解java三大特性!!!!

    教你如何正確了解java三大特性!!!!

    所有的面向?qū)ο缶幊陶Z言的思路都是差不多的，而這三大特性，則是思路中的支柱點，接下來我就重點講解了一下java三大特性，感興趣的朋友跟隨腳本之家小編一起看看吧
    2021-07-07
  • java后臺接受到圖片后保存方法

    java后臺接受到圖片后保存方法

    在本篇文章里小編給大家整理了關(guān)于java后臺接受到圖片后怎么保存的相關(guān)知識點，需要的朋友們參考學(xué)習(xí)下。
    2019-06-06
  • SpringCloud LoadBalancer自定義負(fù)載均衡器使用解析

    SpringCloud LoadBalancer自定義負(fù)載均衡器使用解析

    LoadBalancerClient 是 SpringCloud 提供的一種負(fù)載均衡客戶端，Ribbon 負(fù)載均衡組件內(nèi)部也是集成了 LoadBalancerClient 來實現(xiàn)負(fù)載均衡，本文給大家深入解析 LoadBalancerClient 接口源碼，感興趣的朋友跟隨小編一起看看吧
    2023-04-04
  • Restful傳遞數(shù)組參數(shù)及注解大全

    Restful傳遞數(shù)組參數(shù)及注解大全

    這篇文章主要介紹了Restful傳遞數(shù)組參數(shù)及注解大全的相關(guān)資料,需要的朋友可以參考下
    2015-12-12
  • java模擬ajax訪問另一個項目的controller代碼實例

    java模擬ajax訪問另一個項目的controller代碼實例

    今天小編就為大家分享一篇關(guān)于java模擬ajax訪問另一個項目的controller代碼實例，小編覺得內(nèi)容挺不錯的，現(xiàn)在分享給大家，具有很好的參考價值，需要的朋友一起跟隨小編來看看吧
    2019-03-03
  • Maven?pom.xml文件獲取當(dāng)前時間戳方式

    Maven?pom.xml文件獲取當(dāng)前時間戳方式

    這篇文章主要介紹了Maven?pom.xml文件獲取當(dāng)前時間戳方式，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教
    2021-12-12
  • 詳解Spring中singleton?bean如何同時服務(wù)多個請求

    詳解Spring中singleton?bean如何同時服務(wù)多個請求

    這篇文章主要介紹了詳解Spring中singleton?bean如何同時服務(wù)多個請求
    2023-02-02

    • 最新評論

    民县| 额尔古纳市| 密云县| 交口县| 公主岭市| 石棉县| 贵南县| 巧家县| 河西区| 桐庐县| 广东省| 涟源市| 枣阳市| 茂名市| 云安县| 乐山市| 宝丰县| 嘉定区| 永仁县| 雅安市| 抚远县| 大关县| 酒泉市| 拉萨市| 江源县| 徐州市| 宜宾市| 普兰店市| 武川县| 丰都县| 区。| 名山县| 彭山县| 翁牛特旗| 兴文县| 柳河县| 龙南县| 镇原县| 双流县| 得荣县| 永善县|