Java集合ArrayList與LinkedList詳解
更新時間：2022年08月10日 09:35:16 作者：亞雷???????
這篇文章主要介紹了Java集合ArrayList與LinkedList詳解，對于ArrayList和LinkedList，他們都是List接口的一個實現(xiàn)類，并且我們知道他們的實現(xiàn)方式各不相同，例如ArrayList底層實現(xiàn)是一個數(shù)組
前言
對于Java程序員，可以說對于ArrayList和LinkedList可謂是十分熟悉了
對于ArrayList和LinkedList，他們都是List接口的一個實現(xiàn)類，并且我們知道他們的實現(xiàn)方式各不相同，例如ArrayList底層實現(xiàn)是一個數(shù)組，而LinkedList底層實現(xiàn)是鏈表，對于數(shù)組來說，插入慢但是查詢快，而對于鏈表來說查詢慢，插入快
今天我們就來分析分析他們的源碼
ArrayList
我們先看一看ArrayList的類圖。他繼承于AbstractList，而這個類是List類的的骨架，可以說這個類是List類的基石
成員屬性
/**
序列化ID
**/
private static final long serialVersionUID = 8683452581122892189L;
/**
默認容量
**/
private static final int DEFAULT_CAPACITY = 10;
/**
如果傳入的容量為0，那么將使用這個空元素數(shù)組
**/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
默認空元素數(shù)組，長度為0，傳入元素時會初始化為默認元素大小
**/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
真正存儲數(shù)據的數(shù)組
**/
transient Object[] elementData;
/**
列表中元素的個數(shù)
**/
private int size;這里需要主要關注的成員屬性為size和elementData，一個是元素個數(shù)，一個是真正存儲數(shù)據的數(shù)組
構造函數(shù)
/**
指定數(shù)組長度構造
**/
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
/**
空參構造
**/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/**
傳入一個集合，將該集合的元素初始化到ArrayList種
**/
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}擴容機制
我們知道ArrayList是一個動態(tài)數(shù)組，但是他的底層實現(xiàn)是一個數(shù)組，那他是怎樣保證動態(tài)的呢？
ArrayList每次添加元素之前，都會檢查添加元素后的元素個數(shù)是否超過數(shù)組長度，如果超出，那么就會進行擴容，而數(shù)組擴容通過一個公開的方法實現(xiàn)，我們也可以手動進行擴容
public void ensureCapacity(int minCapacity) {
//判斷數(shù)組是否等于默認空數(shù)組，不等于則給minExpand賦值為10
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
? 0 : DEFAULT_CAPACITY;
//判斷參數(shù)是否大于minExpand大于的時候才會去擴容
if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;//記錄數(shù)組修改次數(shù) + 1
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
//真正擴容的方法
private void grow(int minCapacity) {
//獲取原來的容量
int oldCapacity = elementData.length;
//計算新容量，新容量大小 = 舊容量大小的1.5倍
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);
}我們可以發(fā)現(xiàn)每次擴容，ArrayList都會擴容1.5倍，通過位運算完成計算擴容大小的，我們知道，擴容之后進行數(shù)據遷移這個操作是很費時間的，比如我們有10w條數(shù)據，這樣的話，進行數(shù)據遷移的時候，我們會耗費很長時間，所以我們建議再初始化的時候就定義一個容量，這樣可以讓ArrayList的效率提高很多
add方法
//添加元素到尾部
public boolean add(E e) {
//檢查是否需要擴容
ensureCapacityInternal(size + 1);
//將元素添加到數(shù)組末尾，并把size++
elementData[size++] = e;
return true;
}
//添加元素到指定索引
public void add(int index, E element) {
//檢查index是否越界
rangeCheckForAdd(index);
//檢查是否需要擴容
ensureCapacityInternal(size + 1);
//將index以及之后的元素向后挪動一位
//這樣index就能添加元素了
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
//添加元素到index的位置
elementData[index] = element;
size++;
}
//將集合c的元素添加到list中
public boolean addAll(Collection<? extends E> c) {
//把c轉換為數(shù)組
Object[] a = c.toArray();
//拿到c的長度
int numNew = a.length;
//檢查是否需要擴容
ensureCapacityInternal(size + numNew); // Increments modCount
//將a數(shù)組拷貝到原來數(shù)組的末尾
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}
//將集合c的元素從index位置開始添加到list中
public boolean addAll(int index, Collection<? extends E> c) {
//檢查index是否越界
rangeCheckForAdd(index);
//將c轉換為數(shù)組
Object[] a = c.toArray();
//獲取數(shù)組a的長度
int numNew = a.length;
//檢查是否需要擴容
ensureCapacityInternal(size + numNew); // Increments modCount
//計算需要移動的長度
int numMoved = size - index;
if (numMoved > 0)
//向后移動
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
將數(shù)組a拷貝到原數(shù)組中
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}get方法
public E get(int index) {
//檢查index是否越界
rangeCheck(index);
//返回對應數(shù)組中指定索引的元素
return elementData(index);
}remove方法
//刪除指定索引的元素
public E remove(int index) {
//判斷index是否越界
rangeCheck(index);
//將數(shù)組修改次數(shù)+1
modCount++;
//拿到對應索引的元素
E oldValue = elementData(index);
計算移動位置
int numMoved = size - index - 1;
if (numMoved > 0)
//移動數(shù)組
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
//size-1，并把尾部元素置為null，這里把尾部置為null主要是為了讓GC起作用
elementData[--size] = null;
return oldValue;
}
//刪除第一個滿足o.equals(elementData[index]的元素
public boolean remove(Object o) {
if (o == null) {
//如果o為null使用==進行判斷
//從索引為0的元素開始尋找
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
//否則使用equals判斷
//從索引為0的元素開始尋找
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}小結
- 如果我們的數(shù)據量很大，我們可以給List估算一個容量，然后進行初始化，否則會對效率有影響，畢竟一直進行數(shù)據遷移。
- 最開始Arraylist的容量為10，每次擴容為原先容量的1.5倍，但是如果我們已經擴容的數(shù)組，是不能進行縮容的，例如我們添加了10個元素，這個時候已經擴容了，但是我們刪除最后一個元素，他是不會進行縮容的
- 我們并沒有看到他方法上有synchronized關鍵字，所以他也不是線程安全的，我們可以使用Vector或者使用
Collections.synchronizedList(list)
LinkedList
對于LinkedList，它同樣繼承與AbstractList，在前面已經說過了，AbstractList是List的骨架，我們還可以看到它實現(xiàn)了Deque，所以LinkedList既可以看做一個鏈表也可以看做是一個隊列，同樣也可以看做一個棧，所以LinkedList比較全能
Node類
我們知道LinkedList是一個雙向鏈表，那么肯定有一個個的Node，所以我們先來看一看Node類
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;
}
}這部分代碼比較簡單就簡單說一下，Node節(jié)點有三個成員屬性，分別是value，前驅指針，后繼指針，以及一個全參構造方法
成員屬性
/** 元素個數(shù) */ transient int size = 0; /** 指向鏈表頭結點 */ transient Node<E> first; /** 指向鏈表尾節(jié)點 */ transient Node<E> last; /** 序列化ID */ private static final long serialVersionUID = 876323262645176354L;
構造函數(shù)
//空參構造，沒什么好說的
public LinkedList() {
}
//將集合c的元素添加到鏈表中
public LinkedList(Collection<? extends E> c) {
//調用空參構造
this();
//調用addAll()這個方法在下面講述
addAll(c);
}添加
public boolean add(E e) {
linkLast(e);//添加元素到末尾
return true;
}
//將元素添加到指定index位置
public void add(int index, E element) {
//檢查索引是否大于size或者小于0
checkPositionIndex(index);
//如果索引位置和size相等添加到末尾
if (index == size)
linkLast(element);
else
//添加到指定位置
linkBefore(element, node(index));
}
public void addFirst(E e) {
linkFirst(e);//添加元素到頭部
}
public void addLast(E e) {
linkLast(e);//添加元素到末尾
}
//添加到頭部
private void linkFirst(E e) {
//拿到頭指針
final Node<E> f = first;
//new一個Node節(jié)點，值為e，next為頭指針，pre為null
final Node<E> newNode = new Node<>(null, e, f);
//將頭指針替換為新的
first = newNode;
//將f的pre修改為現(xiàn)在的頭指針
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}
//添加到末尾
void linkLast(E e) {
//拿到尾指針
final Node<E> l = last;
//new一個Node節(jié)點，值為e，next為null，pre為尾指針
final Node<E> newNode = new Node<>(l, e, null);
//替換尾指針
last = newNode;
//將l的next修改為現(xiàn)在的尾指針
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
//將集合c的元素添加到list中
public boolean addAll(Collection<? extends E> c) {
//從尾部開始添加
return addAll(size, c);
}
//真正的addAll方法
public boolean addAll(int index, Collection<? extends E> c) {
//檢查index正確
checkPositionIndex(index);
//先把c轉換為數(shù)組
Object[] a = c.toArray();
//拿到c的長度
int numNew = a.length;
if (numNew == 0)
return false;
//定義兩個指針，一個前驅一個后繼
Node<E> pred, succ;
if (index == size) {
succ = null;
pred = last;
} else {
succ = node(index);
pred = succ.prev;
}
//遍歷數(shù)組a
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
//new一個Node節(jié)點，值為e，前驅為pred，后繼為null
Node<E> newNode = new Node<>(pred, e, null);
//pred為null，證明前驅為null，當前節(jié)點為鏈表的頭結點
if (pred == null)
first = newNode;
else
//前驅節(jié)點后繼指針指向頭結點
pred.next = newNode;
//前驅節(jié)點后移
pred = newNode;
}
//succ為null證明index索引位于鏈表最后
if (succ == null) {
last = pred;
} else {
//pred的后繼節(jié)點為succ
pred.next = succ;
//succ的前驅節(jié)點為pred
succ.prev = pred;
}
size += numNew;
modCount++;
return true;
}獲取
//這個方法是Node類的方法，我們可以看到上面的addAll方法也使用了這個方法
//這個方法作用是返回指定索引的非空節(jié)點
Node<E> node(int 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;
}
}
//獲取index位置的元素
public E get(int index) {
//檢查索引是否正常
checkElementIndex(index);
return node(index).item;
}
//獲取頭部元素
public E getFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}
//獲取尾部元素
public E getLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;
}刪除
//刪除index位置的元素
public E remove(int index) {
//檢查索引是否大于size或者小于0
checkElementIndex(index);
//刪除index位置的元素
return unlink(node(index));
}
//刪除頭部元素，這個方法是Node類的方法
private E unlinkFirst(Node<E> f) {
//拿到頭節(jié)點的值
final E element = f.item;
//拿到頭結點的next值
final Node<E> next = f.next;
//將頭結點的值置為null(幫助GC)
f.item = null;
//將頭結點的next置為null(幫助GC)
f.next = null;
//將頭結點修改為next
first = next;
if (next == null)
//此時鏈表沒有元素了
last = null;
else
next.prev = null;
size--;
modCount++;
return element;
}
//刪除尾部元素，這個方法是Node類的方法
private E unlinkLast(Node<E> l) {
//拿到尾節(jié)點的值
final E element = l.item;
//拿到尾節(jié)點的前驅
final Node<E> prev = l.prev;
//將尾結點的值置為null(幫助GC)
l.item = null;
//將尾結點的next置為null(幫助GC)
l.prev = null;
//將尾指針修改為prev
last = prev;
if (prev == null)
//此時鏈表沒有元素了
first = null;
else
prev.next = null;
size--;
modCount++;
return element;
}小結
- 雖然說鏈表的刪除的效率為O(1),但是在LinkedList中我們需要先利用node方法查詢到指定節(jié)點的位置，然后再去刪除，所以千萬不要誤認為LinkedList的remove方法是O(1)
- LinkedList刪除頭部和尾部的元素效率為O(1)
到此這篇關于Java集合ArrayList與LinkedList詳解的文章就介紹到這了,更多相關Java ArrayList與LinkedList內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
您可能感興趣的文章:
- JAVA LinkedList和ArrayList的使用及性能分析
- java中ArrayList和LinkedList的區(qū)別詳解
- Java中ArrayList和LinkedList的遍歷與性能分析
- java 集合之實現(xiàn)類ArrayList和LinkedList的方法
- java 中ArrayList與LinkedList性能比較
- java中ArrayList與LinkedList對比詳情
- 區(qū)分Java中的ArrayList和LinkedList
- Java面試崗常見問題之ArrayList和LinkedList的區(qū)別
- Java中ArrayList和LinkedList區(qū)別
- Java ArrayList與LinkedList使用方法詳解
- Java中ArrayList和LinkedList的區(qū)別
相關文章
這篇文章主要介紹了SpringBoot改動后0.03秒啟動,本文結合示例代碼給大家講解的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2022-12-12
這篇文章主要介紹了Springboot事務失效的原因及解決辦法詳解,spring中的事務是依賴AOP的,AOP是通過動態(tài)代理實現(xiàn)的,只有通過代理類訪問的方法才能被攔截,而addMultiFile直接內部調用了addFile方法,所以addFile中的事務就不會生效2023-10-10
在使用Java開發(fā)接口請求中，我們需要對請求進行進行統(tǒng)一返回值，這時候我們自己封裝一個統(tǒng)一的Result返回類，本文主要介紹了Java封裝公共Result結果返回類的實現(xiàn)，感興趣的可以了解一下2023-01-01
這篇文章主要介紹了spring中的ObjectPostProcessor詳解,Spring Security 的 Java 配置不會公開其配置的每個對象的每個屬性,這簡化了大多數(shù)用戶的配置,畢竟,如果每個屬性都公開,用戶可以使用標準 bean 配置,需要的朋友可以參考下2024-01-01
Netty分布式server啟動流程Nio創(chuàng)建源碼分析
這篇文章主要介紹了Netty分布式server啟動流程Nio創(chuàng)建源碼分析，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2022-03-03
這篇文章主要介紹了Java虛擬機類文件結構，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2019-03-03
SpringBoot整合RabbitMQ很容易，但是整合的目的是為了使用，那要使用RabbitMQ就要對其有一定的了解，不然容易整成一團漿糊。因為說到底，SpringBoot只是在封裝RabbitMQ的API，讓其更容易使用而已，廢話不多說，讓我們一起整它2023-03-03
通過AOP攔截Spring?Boot日志并將其存入數(shù)據庫功能實現(xiàn)
本文介紹了如何使用Spring Boot和AOP技術實現(xiàn)攔截系統(tǒng)日志并保存到數(shù)據庫中的功能，包括配置數(shù)據庫連接、定義日志實體類、定義日志攔截器、使用AOP攔截日志并保存到數(shù)據庫中等步驟，感興趣的朋友一起看看吧2023-08-08
詳解springcloud 基于feign的服務接口的統(tǒng)一hystrix降級處理
這篇文章主要介紹了詳解springcloud 基于feign的服務接口的統(tǒng)一hystrix降級處理，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2019-06-06
Java跨session實現(xiàn)token接口測試過程圖解
這篇文章主要介紹了Java跨session實現(xiàn)token接口測試過程圖解,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2020-04-04