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

Java中ArrayList和LinkedList區(qū)別

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

1 前言

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

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

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

2.1 ArrayList

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

2.2 LinkedList

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

2.3 使用場景

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

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

3 源碼分析

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

3.1 ArrayList核心源碼

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

總結(jié):

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

3.2 LinkedList核心源碼

//JDK1.8
public class LinkedList<E>
? ? extends AbstractSequentialList<E>
? ? implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{?
? ? // 元素數(shù)量
? ? transient int size = 0;
? ??
? ? // 鏈表首節(jié)點
? ? transient Node<E> first;
? ??
? ? // 鏈表尾節(jié)點
? ? transient Node<E> last;
? ??
? ? // 空構造器
? ? 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;
? ? ? ? ? ? // 下一個元素地址
? ? ? ? ? ? this.next = next;
? ? ? ? ? ? // 上一個元素地址
? ? ? ? ? ? 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 ,如果是第一個元素則為null
? ? ? ? final Node<E> l = last;
? ? ? ? //把元素封裝為一個Node對象
? ? ? ? final Node<E> newNode = new Node<>(l, e, null);
? ? ? ? //把鏈表的last元素指向新的元素
? ? ? ? last = newNode;
? ? ? ? //如果添加的是第一個元素
? ? ? ? if (l == null){
? ? ? ? ? ? //把鏈表的first元素指向新的元素
? ? ? ? ? ? first = newNode;
? ? ? ? }
? ? ? ? //如果添加的不是第一個元素
? ? ? ? else{
? ? ? ? ? ? //把l的下一個元素指向新的元素
? ? ? ? ? ? l.next = newNode; ? ? ? ? ? ?
? ? ? ? }
? ? ? ? //集合中元素數(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) {
? ? ? ? //檢測元素索引
? ? ? ? checkElementIndex(index);
? ? ? ? return node(index).item;
? ? }
? ??
? ? //返回指定元素索引處的(非空)節(jié)點
? ? 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ù)的速度會比ArrayList慢。
由于LinkedList底層是用雙向鏈表實現(xiàn)的,沒有初始化大小,也沒有擴容的機制。

4 碼農(nóng)來洞見

4.1為什么ArrayList比LinkedList要快

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

4.2 注意ArrayList不同JDK版本源碼

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

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

ArrayListLinkedList都不是線程安全的。然而Vector類被認為是過時的廢棄的了。

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

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

CopyOnWriteArrayList和Collections.synchronizedList是實現(xiàn)線程安全的列表的兩種方式。兩種實現(xiàn)方式分別針對不同情況有不同的性能表現(xiàn),其中CopyOnWriteArrayList的寫操作性能較差,而多線程的讀操作性能較好。而Collections.synchronizedList的寫操作性能比CopyOnWriteArrayList在多線程操作的情況下要好很多,而讀操作因為是采用了synchronized關鍵字的方式,其讀操作性能并不如CopyOnWriteArrayList。因此在不同的應用場景下,應該選擇不同的多線程安全實現(xiàn)類。

4.4 為什么Java的Vector類被認為是過時的或者廢棄的

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

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

當然,即使你不需要同步,Vector也是有鎖的資源開銷的。

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

相關文章

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

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

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

    Java如何獲取Object中Value

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

    深入了解Java行為型設計模式之策略模式

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

    關于idea中SpringBoot啟動失敗的坑

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

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

    ThreadPoolExecutor是一個典型的緩存池化設計的產(chǎn)物,因為池子有大小,當池子體積不夠承載時,就涉及到拒絕策略。JDK中已預設了?4?種線程池拒絕策略,下面結(jié)合場景詳細聊聊這些策略的使用場景以及還能擴展哪些拒絕策略
    2021-11-11
  • Java線程的生命周期命名與獲取代碼實現(xiàn)

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

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

    Java高級語法學習之反射詳解

    java的泛型和反射機制一直很難理解和應用,下面這篇文章主要給大家介紹了關于Java高級語法學習之反射的相關資料,文中通過實例代碼介紹的非常詳細,需要的朋友可以參考下
    2022-01-01
  • SpringBoot @ModelAttribute使用場景分析

    SpringBoot @ModelAttribute使用場景分析

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

    深入解析Spring中的@Bean注解

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

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

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

最新評論