成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

ArrayList和LinkedList對比

BlackFlagBin / 2250人閱讀

摘要：底層是鏈表實(shí)現(xiàn)的，對順序訪問進(jìn)行了優(yōu)化，插入和刪除元素時間復(fù)雜度較好，但是隨機(jī)訪問需要遍歷元素，所以效率比差。

次序是List最重要的特點(diǎn)；它保證維護(hù)元素特定的順序
簡單介紹：
ArrayList底層的實(shí)現(xiàn)是數(shù)組，隨機(jī)訪問所以用下標(biāo)訪問的速度比較快，但是插入和刪除元素，會有移動元素的開銷，所以速度比LinkedList差。
LikedList底層是鏈表實(shí)現(xiàn)的，對順序訪問進(jìn)行了優(yōu)化，插入和刪除元素時間復(fù)雜度較LinkedList好，但是隨機(jī)訪問需要遍歷元素，所以效率比ArrayList差。

例子如下：

import org.junit.Test;  
import java.util.ArrayList;  
import java.util.LinkedList;  
import java.util.List;  
  
public class ListAddTest {  
  
    List arrList = new ArrayList();  
    List lnkList = new LinkedList();  
  
    void add(List list) {  
  
        long startTime = System.currentTimeMillis();  
        System.out.println("開始的時間：" + startTime);  
        for (int i = 0; i < 100000; i++) {  
            list.add(0, String.valueOf(i));  
        }  
        long endTime = System.currentTimeMillis();  
        System.out.println("結(jié)束的時間：" + endTime);  
        System.out.println("總耗時：" + (endTime - startTime));  
  
    }  
  
    @Test  
    public void addTimeTest() {  
  
        add(arrList);  
        // 開始的時間：1487783199226  
        // 結(jié)束的時間：1487783199741  
        // 總耗時：515  
  
        add(lnkList);  
        // 開始的時間：1487783199741  
        // 結(jié)束的時間：1487783199756  
        // 總耗時：15  
  
    }  
  
}

分析

首先，閱讀JDK的文檔，我們從中可以知道，ArrayList實(shí)際上是一個可變長的數(shù)組，LinkedList則是由相互引用的節(jié)點(diǎn)組成的雙向鏈表

緊接著我們就要知道，在增加數(shù)據(jù)時LinkedList和ArrayList分別在底層發(fā)生了什么？于是略讀JDK源碼我們就可以得出：
● 既然LinkedList是一個由相互引用的節(jié)點(diǎn)組成的雙向鏈表，那么當(dāng)把數(shù)據(jù)插入至該鏈表某個位置時，該數(shù)據(jù)就會被組裝成一個新的節(jié)點(diǎn)，隨后只需改變鏈表中對應(yīng)的兩個節(jié)點(diǎn)之間的引用關(guān)系，使它們指向新節(jié)點(diǎn)，即可完成插入（如下圖）；同樣的道理，刪除數(shù)據(jù)時，只需刪除對應(yīng)節(jié)點(diǎn)的引用即可

● 而ArrayList是一個可變長數(shù)組，插入數(shù)據(jù)時，則需要先將原始數(shù)組中的數(shù)據(jù)復(fù)制到一個新的數(shù)組，隨后再將數(shù)據(jù)賦值到新數(shù)組的指定位置（如下圖）；刪除數(shù)據(jù)時，也是將原始數(shù)組中要保留的數(shù)據(jù)復(fù)制到一個新的數(shù)組

結(jié)論

因此，在添加或刪除數(shù)據(jù)的時候，ArrayList經(jīng)常需要復(fù)制數(shù)據(jù)到新的數(shù)組，而LinkedList只需改變節(jié)點(diǎn)之間的引用關(guān)系，這就是LinkedList在添加和刪除數(shù)據(jù)的時候通常比ArrayList要快的原因

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/71014.html

相關(guān)文章

  • Week 2 - Java 容器 - 詳細(xì)剖析 List 之 ArrayList, Vector,

    摘要：底層使用的是雙向鏈表數(shù)據(jù)結(jié)構(gòu)之前為循環(huán)鏈表，取消了循環(huán)?？焖匐S機(jī)訪問就是通過元素的序號快速獲取元素對象對應(yīng)于方法。而接口就是用來標(biāo)識該類支持快速隨機(jī)訪問。僅僅是起標(biāo)識作用。，中文名為雙端隊(duì)列。不同的是，是線程安全的，內(nèi)部使用了進(jìn)行同步。 前言 學(xué)習(xí)情況記錄 時間：week 2 SMART子目標(biāo) ：Java 容器 記錄在學(xué)習(xí)Java容器 知識點(diǎn)中，關(guān)于List的需要重點(diǎn)記錄的知識點(diǎn)。...

    MartinDai 評論0 收藏0

  • 常見的集合容器應(yīng)當(dāng)避免的坑

    摘要：盡可能避免使用，會導(dǎo)致復(fù)制數(shù)組，降低效率。再額外提一點(diǎn)，我們常用的另一個容器也是推薦要初始化長度從而避免擴(kuò)容。 showImg(https://segmentfault.com/img/remote/1460000019659723); 前言 前不久幫同事一起 review 一個 job 執(zhí)行緩慢的問題時發(fā)現(xiàn)不少朋友在擼碼實(shí)現(xiàn)功能時還是有需要細(xì)節(jié)不夠注意，于是便有了這篇文章。 Arra...

    GraphQuery 評論0 收藏0

  • 1、List接口 2、Set接口 3、判斷集合唯一性原理

    摘要：接口的特點(diǎn)接口的特點(diǎn)它是一個元素存取有序的集合。導(dǎo)致迭代器并不知道集合中的變化，容易引發(fā)數(shù)據(jù)的不確定性。枚舉已被迭代器替代。集合取出元素的方式可以采用迭代器增強(qiáng)。 01List接口的特點(diǎn) A:List接口的特點(diǎn): ?a:它是一個元素存取有序的集合。 例如，存元素的順序是11、22、33。那么集合中，元素的存儲就是按照11、22、33的順序完成的）。 ?b:它是一個帶有索引的...

    gnehc 評論0 收藏0

  • Java常見集合知識詳解

    摘要：集合的種類常見的集合類分如下幾個種類詳解接口是和接口的父接口，也是集合類除外根接口。接口集合中元素的存放特點(diǎn)是元素有序，同一元素可重復(fù)。總結(jié)中集合是一個非常重要的知識點(diǎn)，在實(shí)際運(yùn)用中也是常常會使用到。 集合的種類 常見的集合類分如下幾個種類： Collection - List - ArrayList - LinkedList - Set - HashSet...

    lewinlee 評論0 收藏0

  • 源碼|jdk源碼之LinkedList與modCount字段

    摘要：迭代器迭代器迭代中表被修改考慮以下這段代碼在迭代器創(chuàng)建之后，對表進(jìn)行了修改。這樣設(shè)計(jì)是因?yàn)椋鞔肀碇心硞€元素的位置，內(nèi)部會存儲某些能夠代表該位置的信息。 鏈表是對上一篇博文所說的順序表的一種實(shí)現(xiàn)。 與ArrayList思路截然不同，鏈表的實(shí)現(xiàn)思路是： 不同元素實(shí)際上是存儲在離散的內(nèi)存空間中的。 每一個元素都有一個指針指向下一個元素，這樣整個離散的空間就被串成了一個有順序的表。 ...

    趙連江 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<