Java中ArrayList和LinkedList區(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要快
ArrayList
和LinkedList
本質(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ù)的同步
ArrayList
和LinkedList
都不是線程安全的。然而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ù)瀏覽下面的相關文章希望大家以后多多支持腳本之家!
- java中ArrayList和LinkedList的區(qū)別詳解
- 淺談 java中ArrayList、Vector、LinkedList的區(qū)別聯(lián)系
- 淺析 ArrayList 和 LinkedList 有什么區(qū)別
- ArrayList和LinkedList區(qū)別及使用場景代碼解析
- Java中ArrayList和LinkedList之間的區(qū)別_動力節(jié)點Java學院整理
- Java面試崗常見問題之ArrayList和LinkedList的區(qū)別
- Java ArrayList與LinkedList及HashMap容器的用法區(qū)別
- Java中ArrayList和LinkedList的區(qū)別
- ArrayList與linkedList的用法區(qū)別及擴容方式
- Java中ArrayList和LinkedList有什么區(qū)別舉例詳解
相關文章
java線程池ThreadPoolExecutor的八種拒絕策略示例詳解
ThreadPoolExecutor是一個典型的緩存池化設計的產(chǎn)物,因為池子有大小,當池子體積不夠承載時,就涉及到拒絕策略。JDK中已預設了?4?種線程池拒絕策略,下面結(jié)合場景詳細聊聊這些策略的使用場景以及還能擴展哪些拒絕策略2021-11-11SpringBoot @ModelAttribute使用場景分析
這篇文章主要介紹了SpringBoot @ModelAttribute使用場景分析,文中通過實例代碼圖文相結(jié)合給大家介紹的非常詳細,需要的朋友可以參考下2021-08-08