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

Java中ArrayList和LinkedList區(qū)別

 更新時(shí)間:2022年01月18日 09:52:56   作者:碼農(nóng)洞見(jiàn)?  
這篇文章主要介紹了Java中ArrayList和LinkedList區(qū)別,下面我們就重點(diǎn)聊一聊在日常開(kāi)發(fā)中經(jīng)常被使用到的兩個(gè)集合類ArrayList和LinkedList的本質(zhì)區(qū)別吧,需要的朋友可以參考一下

1 前言

許多語(yǔ)言,例如 Perl ,Python 和 Ruby ,都有集合的本地支持。有些語(yǔ)言(例如Python)甚至將基本集合組件(列表,映射和集合)作為內(nèi)置函數(shù)包含在其中。

通常,程序總是根據(jù)運(yùn)行時(shí)才知道的某些條件去創(chuàng)建新的對(duì)象。在此之前,無(wú)法知道所需對(duì)象的數(shù)量甚至確切類型。為了解決這個(gè)普遍的編程問(wèn)題,需要在任意時(shí)刻和任意位置創(chuàng)建任意數(shù)量的對(duì)象。java.util 庫(kù)提供了一套相當(dāng)完整的集合類(collection classes)來(lái)解決這個(gè)問(wèn)題,其中基本的類型有 List 、 Set 、 Queue 和 Map。這些類型也被稱作容器類。

2 數(shù)據(jù)結(jié)構(gòu)的區(qū)別

2.1 ArrayList

ArrayList是基于數(shù)組實(shí)現(xiàn)的,數(shù)組是典型的緊密結(jié)構(gòu),所以它使用索引在數(shù)組中搜索和讀取數(shù)據(jù)快,可以直接返回?cái)?shù)組中index位置的元素,因此在隨機(jī)訪問(wèn)集合元素上有較好的性能。

2.2 LinkedList

LinkedList是基于雙鏈表實(shí)現(xiàn)的,鏈表是典型的跳轉(zhuǎn)結(jié)構(gòu),插入和刪除只是指針指向的修改,所以它插入、刪除中間元素快,因此在操作數(shù)據(jù)方面性能較好。

2.3 使用場(chǎng)景

如果應(yīng)用程序?qū)?shù)據(jù)有較多的隨機(jī)訪問(wèn),ArrayList對(duì)象要優(yōu)于LinkedList對(duì)象;

如果應(yīng)用程序有更多的插入或者刪除操作,較少的隨機(jī)訪問(wèn),LinkedList對(duì)象要優(yōu)于ArrayList對(duì)象;

3 源碼分析

下面我們通過(guò)JDK1.8源碼源碼分析一下核心功能。

3.1 ArrayList核心源碼

public class ArrayList<E> extends AbstractList<E>
? ? ? ? implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
? ??
? ? //默認(rèn)大小
? ? private static final int DEFAULT_CAPACITY = 10;
? ? ?
? ? //省略。。。
? ??
? ? //動(dòng)態(tài)數(shù)組
? ? transient Object[] elementData;?
? ??
? ? //數(shù)組大小
? ? private int size;
? ??
? ? //空構(gòu)造器
? ? public ArrayList() {
? ? ? ? this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
? ? }
? ??
? ? // 查詢?cè)?
? ? public E get(int index) {
? ? ? ? // 檢查索引是否在范圍內(nèi)
? ? ? ? rangeCheck(index);?? ??? ??? ??? ??? ?
? ? ? ? return elementData(index);
? ? }
? ??
? ? //順序添加元素
? ? public boolean add(E e) {
? ? ? ? //擴(kuò)容
? ? ? ? ensureCapacityInternal(size + 1);?
? ? ? ? elementData[size++] = e;
? ? ? ? return true;
? ? }
? ??
? ? //從數(shù)組中間添加元素
? ? public void add(int index, E element) {
? ? ? ? // 檢查索引是否在范圍內(nèi)
? ? ? ? rangeCheckForAdd(index);
? ? ? ? // 擴(kuò)容
? ? ? ? ensureCapacityInternal(size + 1);?
? ? ? ? // 復(fù)制數(shù)組
? ? ? ? System.arraycopy(elementData, index, elementData, index + 1,
? ? ? ? ? ? ? ? ? ? ? ? ?size - index);
? ? ? ? // 替換元素
? ? ? ? elementData[index] = element;
? ? ? ? size++;
? ? }
? ??
? ? //是否要擴(kuò)容
? ? private void ensureCapacityInternal(int minCapacity) {
? ? ? ? ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
? ? }
? ??
? ? //確定容量
? ? private void ensureExplicitCapacity(int minCapacity) {
? ? ? ? modCount++;
? ? ? ? if (minCapacity - elementData.length > 0)
? ? ? ? ? ? grow(minCapacity);
? ? }
? ??
? ? //計(jì)算數(shù)組容量
? ? private static int calculateCapacity(Object[] elementData, int minCapacity) {
? ? ? ? if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
? ? ? ? ? ? return Math.max(DEFAULT_CAPACITY, minCapacity);
? ? ? ? }
? ? ? ? return minCapacity;
? ? }
? ??
? ? //動(dòng)態(tài)數(shù)組擴(kuò)容放法
? ? private void grow(int minCapacity) {
? ? ? ? //?
? ? ? ? int oldCapacity = elementData.length;
? ? ? ? int newCapacity = oldCapacity + (oldCapacity >> 1);
? ? ? ? if (newCapacity - minCapacity < 0)
? ? ? ? ? ? newCapacity = minCapacity;
? ? ? ? if (newCapacity - MAX_ARRAY_SIZE > 0)
? ? ? ? ? ? newCapacity = hugeCapacity(minCapacity);
? ? ? ? // 數(shù)組復(fù)制
? ? ? ? elementData = Arrays.copyOf(elementData, newCapacity);
? ? }
? ??
? ? ?//省略。。。
? ??
? }

總結(jié):

ArrayLis初始化構(gòu)造器的時(shí)候數(shù)組為{},在調(diào)用add方法以后默認(rèn)數(shù)組才賦值為新數(shù)組,新數(shù)組默認(rèn)長(zhǎng)度為10。
通過(guò)擴(kuò)容機(jī)制判斷原數(shù)組是否還有空間,若沒(méi)有則重新實(shí)例化一個(gè)空間更大的新數(shù)組,把舊數(shù)組的數(shù)據(jù)拷貝到新數(shù)組中。
在執(zhí)行查詢操作時(shí),先判斷下標(biāo)是否越界,然后在直接通過(guò)下標(biāo)從數(shù)組中返回元素。

3.2 LinkedList核心源碼

//JDK1.8
public class LinkedList<E>
? ? extends AbstractSequentialList<E>
? ? implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{?
? ? // 元素?cái)?shù)量
? ? transient int size = 0;
? ??
? ? // 鏈表首節(jié)點(diǎn)
? ? transient Node<E> first;
? ??
? ? // 鏈表尾節(jié)點(diǎn)
? ? transient Node<E> last;
? ??
? ? // 空構(gòu)造器
? ? public LinkedList() {
? ? ? ??
? ? }
? ??
? ? // Node內(nèi)部類
? ? 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;
? ? ? ? ? ? // 下一個(gè)元素地址
? ? ? ? ? ? this.next = next;
? ? ? ? ? ? // 上一個(gè)元素地址
? ? ? ? ? ? this.prev = prev;
? ? ? ? }
? ? }
? ??
? ? // 順序添加元素
? ? public boolean add(E e) {
? ? ? ? linkLast(e);
? ? ? ? return true;
? ? }
? ??
? ? // 指定位置添加元素
? ? public void add(int index, E element) {
? ? ? ? // 檢查是否越界
? ? ? ? checkPositionIndex(index);?? ?
? ? ? ? // 在鏈表末尾添加,否則在之前插入元素
? ? ? ? if (index == size)?? ??? ??? ?
? ? ? ? ? ? linkLast(element);
? ? ? ? else
? ? ? ? ? ? linkBefore(element, node(index));
? ? }
? ??
? ? // 添加元素e
? ? void linkLast(E e) {
? ? ? ? //把鏈表中l(wèi)ast元素賦給l ,如果是第一個(gè)元素則為null
? ? ? ? final Node<E> l = last;
? ? ? ? //把元素封裝為一個(gè)Node對(duì)象
? ? ? ? final Node<E> newNode = new Node<>(l, e, null);
? ? ? ? //把鏈表的last元素指向新的元素
? ? ? ? last = newNode;
? ? ? ? //如果添加的是第一個(gè)元素
? ? ? ? if (l == null){
? ? ? ? ? ? //把鏈表的first元素指向新的元素
? ? ? ? ? ? first = newNode;
? ? ? ? }
? ? ? ? //如果添加的不是第一個(gè)元素
? ? ? ? else{
? ? ? ? ? ? //把l的下一個(gè)元素指向新的元素
? ? ? ? ? ? l.next = newNode; ? ? ? ? ? ?
? ? ? ? }
? ? ? ? //集合中元素?cái)?shù)量加1
? ? ? ? size++;
? ? ? ? modCount++;
? ? }
? ??
? ? void linkBefore(E e, Node<E> succ) {
? ? ? ? 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++;
? ? }
? ??
? ? //獲取元素
? ? public E get(int index) {
? ? ? ? //檢測(cè)元素索引
? ? ? ? checkElementIndex(index);
? ? ? ? return node(index).item;
? ? }
? ??
? ? //返回指定元素索引處的(非空)節(jié)點(diǎn)
? ? Node<E> node(int index) {
? ? ? ? //把鏈表分為兩段,如果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;
? ? ? ? }
? ? }
? ??
? ? //省略。。。
? ??
}

總結(jié):

LinkedList的get首先判斷需要獲取的數(shù)據(jù)在該鏈表的前半段還是后半段,這樣可以減少需要遍歷的數(shù)據(jù),由于需要遍歷數(shù)據(jù),所以獲取數(shù)據(jù)的速度會(huì)比ArrayList慢。
由于LinkedList底層是用雙向鏈表實(shí)現(xiàn)的,沒(méi)有初始化大小,也沒(méi)有擴(kuò)容的機(jī)制。

4 碼農(nóng)來(lái)洞見(jiàn)

4.1為什么ArrayList比LinkedList要快

ArrayListLinkedList本質(zhì)上每次插入和刪除元素都會(huì)進(jìn)行復(fù)制數(shù)組的操作,如果ArrayList插入操作沒(méi)有觸發(fā)數(shù)組擴(kuò)容操作,并且在List靠近末尾的地方插入,那么ArrayList只需要移動(dòng)較少的數(shù)據(jù),而LinkedList則需要一直查找到列表尾部,反而耗費(fèi)較多時(shí)間,這時(shí)ArrayList就比LinkedList要快。

4.2 注意ArrayList不同JDK版本源碼

JDK1.7中在調(diào)用構(gòu)造器的時(shí)候數(shù)組長(zhǎng)度就初始化為了10,JDK1.8則是在調(diào)用add方法后才創(chuàng)建數(shù)組長(zhǎng)度為10的新數(shù)組替換默認(rèn)空數(shù)組。

4.3 高并發(fā)下如何保證集合數(shù)據(jù)的同步

ArrayListLinkedList都不是線程安全的。然而Vector類被認(rèn)為是過(guò)時(shí)的廢棄的了。

方案一: Collections.synchronizedList(); 得到一個(gè)線程安全的 ArrayList。

方案二: concurrent 并發(fā)包下的 CopyOnWriteArrayList 類。

CopyOnWriteArrayList和Collections.synchronizedList是實(shí)現(xiàn)線程安全的列表的兩種方式。兩種實(shí)現(xiàn)方式分別針對(duì)不同情況有不同的性能表現(xiàn),其中CopyOnWriteArrayList的寫(xiě)操作性能較差,而多線程的讀操作性能較好。而Collections.synchronizedList的寫(xiě)操作性能比CopyOnWriteArrayList在多線程操作的情況下要好很多,而讀操作因?yàn)槭遣捎昧藄ynchronized關(guān)鍵字的方式,其讀操作性能并不如CopyOnWriteArrayList。因此在不同的應(yīng)用場(chǎng)景下,應(yīng)該選擇不同的多線程安全實(shí)現(xiàn)類。

4.4 為什么Java的Vector類被認(rèn)為是過(guò)時(shí)的或者廢棄的

Vector中對(duì)每一個(gè)獨(dú)立操作都實(shí)現(xiàn)了同步,這通常不是我們想要的做法。對(duì)單一操作實(shí)現(xiàn)同步通常不是線程安全的(舉個(gè)例子,比如你想遍歷一個(gè)Vector實(shí)例。你仍然需要申明一個(gè)鎖來(lái)防止其他線程在同一時(shí)刻修改這個(gè)Vector實(shí)例。如果不添加鎖的話

通常會(huì)在遍歷實(shí)例的這個(gè)線程中導(dǎo)致一個(gè)ConcurrentModificationException)同時(shí)這個(gè)操作也是十分慢的(在創(chuàng)建了一個(gè)鎖就已經(jīng)足夠的前提下,為什么還需要重復(fù)的創(chuàng)建鎖)

當(dāng)然,即使你不需要同步,Vector也是有鎖的資源開(kāi)銷的。

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

相關(guān)文章

  • JPA之多對(duì)多查詢死循環(huán)嵌套問(wèn)題及解決方案

    JPA之多對(duì)多查詢死循環(huán)嵌套問(wèn)題及解決方案

    這篇文章主要介紹了JPA之多對(duì)多查詢死循環(huán)嵌套問(wèn)題及解決方案,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教
    2024-05-05
  • Java如何獲取Object中Value

    Java如何獲取Object中Value

    在Java中,獲取Object中的值需依賴于對(duì)象的類型和屬性,常用方法包括使用反射、getter方法、接口或抽象類、Map等數(shù)據(jù)結(jié)構(gòu),本文給大家介紹Java如何獲取Object中Value,感興趣的朋友跟隨小編一起看看吧
    2024-09-09
  • 深入了解Java行為型設(shè)計(jì)模式之策略模式

    深入了解Java行為型設(shè)計(jì)模式之策略模式

    策略模式屬于Java-設(shè)計(jì)模式中行為模式之一,該模式定義了一系列算法,并將每個(gè)算法封裝起來(lái),使它們可以相互替換。本文將通過(guò)示例詳細(xì)講解這一模式,需要的可以參考一下
    2022-09-09
  • 關(guān)于idea中SpringBoot啟動(dòng)失敗的坑

    關(guān)于idea中SpringBoot啟動(dòng)失敗的坑

    這篇文章主要介紹了關(guān)于idea中SpringBoot啟動(dòng)失敗的坑,本文給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下
    2021-03-03
  • java線程池ThreadPoolExecutor的八種拒絕策略示例詳解

    java線程池ThreadPoolExecutor的八種拒絕策略示例詳解

    ThreadPoolExecutor是一個(gè)典型的緩存池化設(shè)計(jì)的產(chǎn)物,因?yàn)槌刈佑写笮?當(dāng)池子體積不夠承載時(shí),就涉及到拒絕策略。JDK中已預(yù)設(shè)了?4?種線程池拒絕策略,下面結(jié)合場(chǎng)景詳細(xì)聊聊這些策略的使用場(chǎng)景以及還能擴(kuò)展哪些拒絕策略
    2021-11-11
  • Java線程的生命周期命名與獲取代碼實(shí)現(xiàn)

    Java線程的生命周期命名與獲取代碼實(shí)現(xiàn)

    這篇文章主要介紹了Java線程的生命周期命名與獲取代碼實(shí)現(xiàn),文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下
    2020-04-04
  • Java高級(jí)語(yǔ)法學(xué)習(xí)之反射詳解

    Java高級(jí)語(yǔ)法學(xué)習(xí)之反射詳解

    java的泛型和反射機(jī)制一直很難理解和應(yīng)用,下面這篇文章主要給大家介紹了關(guān)于Java高級(jí)語(yǔ)法學(xué)習(xí)之反射的相關(guān)資料,文中通過(guò)實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下
    2022-01-01
  • SpringBoot @ModelAttribute使用場(chǎng)景分析

    SpringBoot @ModelAttribute使用場(chǎng)景分析

    這篇文章主要介紹了SpringBoot @ModelAttribute使用場(chǎng)景分析,文中通過(guò)實(shí)例代碼圖文相結(jié)合給大家介紹的非常詳細(xì),需要的朋友可以參考下
    2021-08-08
  • 深入解析Spring中的@Bean注解

    深入解析Spring中的@Bean注解

    這篇文章主要介紹了深入解析Spring中的@Bean注解,Spring的@Bean注解用于告訴方法,產(chǎn)生一個(gè)Bean對(duì)象,然后這個(gè)Bean對(duì)象交給Spring管理,產(chǎn)生這個(gè)Bean對(duì)象的方法Spring只會(huì)調(diào)用一次,隨后這個(gè)Spring將會(huì)將這個(gè)Bean對(duì)象放在自己的IOC容器中,需要的朋友可以參考下
    2023-07-07
  • 解析iReport自定義行數(shù)分頁(yè)的操作方法

    解析iReport自定義行數(shù)分頁(yè)的操作方法

    ireport默認(rèn)都是自動(dòng)分頁(yè)數(shù)據(jù)超出頁(yè)面長(zhǎng)度就會(huì)自動(dòng)分到下一頁(yè),但有時(shí)候業(yè)務(wù)需要一頁(yè)只顯示固定幾行這時(shí)候就需要自定義條數(shù)了。下面看具體操作吧
    2021-10-10

最新評(píng)論