ArrayList和LinkedList對比

BlackFlagBin 發布于2019-08-16 11:06 / 2239人閱讀

摘要：底層是鏈表實現的，對順序訪問進行了優化，插入和刪除元素時間復雜度較好，但是隨機訪問需要遍歷元素，所以效率比差。

次序是List最重要的特點；它保證維護元素特定的順序
簡單介紹：
ArrayList底層的實現是數組，隨機訪問所以用下標訪問的速度比較快，但是插入和刪除元素，會有移動元素的開銷，所以速度比LinkedList差。
LikedList底層是鏈表實現的，對順序訪問進行了優化，插入和刪除元素時間復雜度較LinkedList好，但是隨機訪問需要遍歷元素，所以效率比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("結束的時間：" + endTime);  
        System.out.println("總耗時：" + (endTime - startTime));  
  
    }  
  
    @Test  
    public void addTimeTest() {  
  
        add(arrList);  
        // 開始的時間：1487783199226  
        // 結束的時間：1487783199741  
        // 總耗時：515  
  
        add(lnkList);  
        // 開始的時間：1487783199741  
        // 結束的時間：1487783199756  
        // 總耗時：15  
  
    }  
  
}

分析

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

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

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

結論

因此，在添加或刪除數據的時候，ArrayList經常需要復制數據到新的數組，而LinkedList只需改變節點之間的引用關系，這就是LinkedList在添加和刪除數據的時候通常比ArrayList要快的原因

GPU云服務器云服務器 ArrayList和Vector LinkedList flink和spark對比專線和ipsec 網絡對比

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/71014.html

Week 2 - Java 容器 - 詳細剖析 List 之 ArrayList, Vector,

摘要：底層使用的是雙向鏈表數據結構之前為循環鏈表，取消了循環。快速隨機訪問就是通過元素的序號快速獲取元素對象對應于方法。而接口就是用來標識該類支持快速隨機訪問。僅僅是起標識作用。，中文名為雙端隊列。不同的是，是線程安全的，內部使用了進行同步。前言學習情況記錄時間：week 2 SMART子目標：Java 容器記錄在學習Java容器知識點中，關于List的需要重點記錄的知識點。...

MartinDai 2019-08-16 18:35 評論0 收藏0
常見的集合容器應當避免的坑

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

GraphQuery 2019-08-16 18:28 評論0 收藏0
1、List接口 2、Set接口 3、判斷集合唯一性原理

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

gnehc 2019-08-14 18:41 評論0 收藏0
Java常見集合知識詳解

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

lewinlee 2019-08-15 18:19 評論0 收藏0
源碼|jdk源碼之LinkedList與modCount字段

摘要：迭代器迭代器迭代中表被修改考慮以下這段代碼在迭代器創建之后，對表進行了修改。這樣設計是因為，迭代器代表表中某個元素的位置，內部會存儲某些能夠代表該位置的信息。鏈表是對上一篇博文所說的順序表的一種實現。與ArrayList思路截然不同，鏈表的實現思路是：不同元素實際上是存儲在離散的內存空間中的。每一個元素都有一個指針指向下一個元素，這樣整個離散的空間就被串成了一個有順序的表。 ...

趙連江 2019-08-16 12:42 評論0 收藏0