Java中ArrayList和LinkedList區(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要快
ArrayList
和LinkedList
本質(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ù)的同步
ArrayList
和LinkedList
都不是線程安全的。然而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)文章希望大家以后多多支持腳本之家!
- java中ArrayList和LinkedList的區(qū)別詳解
- 淺談 java中ArrayList、Vector、LinkedList的區(qū)別聯(lián)系
- 淺析 ArrayList 和 LinkedList 有什么區(qū)別
- ArrayList和LinkedList區(qū)別及使用場(chǎng)景代碼解析
- Java中ArrayList和LinkedList之間的區(qū)別_動(dòng)力節(jié)點(diǎn)Java學(xué)院整理
- Java面試崗常見(jiàn)問(wèn)題之ArrayList和LinkedList的區(qū)別
- Java ArrayList與LinkedList及HashMap容器的用法區(qū)別
- Java中ArrayList和LinkedList的區(qū)別
- ArrayList與linkedList的用法區(qū)別及擴(kuò)容方式
- Java中ArrayList和LinkedList有什么區(qū)別舉例詳解
相關(guān)文章
JPA之多對(duì)多查詢死循環(huán)嵌套問(wèn)題及解決方案
這篇文章主要介紹了JPA之多對(duì)多查詢死循環(huán)嵌套問(wèn)題及解決方案,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2024-05-05關(guān)于idea中SpringBoot啟動(dòng)失敗的坑
這篇文章主要介紹了關(guān)于idea中SpringBoot啟動(dòng)失敗的坑,本文給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2021-03-03java線程池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-11Java線程的生命周期命名與獲取代碼實(shí)現(xiàn)
這篇文章主要介紹了Java線程的生命周期命名與獲取代碼實(shí)現(xiàn),文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-04-04Java高級(jí)語(yǔ)法學(xué)習(xí)之反射詳解
java的泛型和反射機(jī)制一直很難理解和應(yīng)用,下面這篇文章主要給大家介紹了關(guān)于Java高級(jí)語(yǔ)法學(xué)習(xí)之反射的相關(guān)資料,文中通過(guò)實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下2022-01-01SpringBoot @ModelAttribute使用場(chǎng)景分析
這篇文章主要介紹了SpringBoot @ModelAttribute使用場(chǎng)景分析,文中通過(guò)實(shí)例代碼圖文相結(jié)合給大家介紹的非常詳細(xì),需要的朋友可以參考下2021-08-08解析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