Java集合 - List介紹及源碼解析

(源碼版本為 JDK 8)

集合類在java.util包中，類型大體可以分為3種：Set、List、Map。

JAVA 集合關系（簡圖）#

集合.jpg

（圖檔來源網絡）

List集合和Set集合都是繼承Collection接口，是List和Set的最上級接口，包含如下方法:

Collection接口.png

List 集合#

List是一個有序集合(也稱為序列)，你可以控制每個元素被插入的位置，和根據索引通路清單中元素。List集合元素可以重複，也可以存入 null 元素。

List集合是可以根據索引來操縱集合，是以List接口在Collection接口基礎增加了一些根據索引操縱集合的接口方法。

List接口.png

集合接口的實作類#

List 集合有兩個常用實作，ArrayList和LinkedList，内部采用不同資料結構來實作，不同場景下有不同的使用選擇。

ArrayList

ArrayList類-1.png

ArrayList類除了繼承和實作集合接口外，還實作了RandomAccess, Cloneable接口。說明ArrayList支援克隆和快速随機通路。

ArrayList 的内部資料結構是數組。

ArrayList内部資料結構-數組.png

預設初始化容量為10

預設初始化容量.png

從查找，增加，删除，修改元素方法看ArrayList集合

查找元素方法：get，indexOf

Copy

// 直接根據索引查找元素，效率較高

public E get(int index) {

rangeCheck(index);
return elementData(index); // 根據索引直接傳回數組中元素

}

// 根據元素查索引位置，元素不存在傳回 -1 ，使用了循環周遊查找元素，查找效率取決于集合大小，元素所處的位置。

public int indexOf(Object o) {

if (o == null) {
    for (int i = 0; i < size; i++)
        if (elementData[i]==null)
            return i;
} else {
    for (int i = 0; i < size; i++)
        if (o.equals(elementData[i]))
            return i;
}
return -1;

}

增加元素方法：add

// 增加元素，存在擴容，資料拷貝等問題，效率會變低，如果要向集合中大量的添加元素可以通過構造方法指定較大的初始容量。

public boolean add(E e) {

ensureCapacityInternal(size + 1);  // 增加 modCount!!
elementData[size++] = e;
return true;

private void ensureCapacityInternal(int minCapacity) {

ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));

// 計算容量

private static int calculateCapacity(Object[] elementData, int minCapacity) {

if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
    return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;

// 確定容量安全

private void ensureExplicitCapacity(int minCapacity) {

modCount++; // 集合結構修改計數器（結構修改是指那些改變清單的大小或位置等）
// 當所需最小容量比數組容量大需要擴容
if (minCapacity - elementData.length > 0)
    grow(minCapacity);

// 擴容

private void grow(int minCapacity) {

// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1); // 容量變為原來的1.5倍
if (newCapacity - minCapacity < 0)
    newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
    newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);

删除元素方法：remove

// 根據索引删除元素，如果從開頭和中間位置删除元素，删除位置後面的元素會向前移動，效率會比删除末尾元素低。

public E remove(int index) {

rangeCheck(index);

modCount++;
E oldValue = elementData(index);

int numMoved = size - index - 1;
if (numMoved > 0)
    // 元素的移動拷貝
    System.arraycopy(elementData, index+1, elementData, index,
                     numMoved);
elementData[--size] = null; // 指派為null 明确的讓垃圾回收，--size 删除元素後修改集合長度

return oldValue;

// 根據集合元素删除，先循環找出要删除的元素位置索引，然後再根據索引删除。和根據索引删除方法比較，多了一步通過循環查找元素索引位置的過程。

public boolean remove(Object o) {

if (o == null) {
    for (int index = 0; index < size; index++)
        if (elementData[index] == null) {
            fastRemove(index);
            return true;
        }
} else {
    for (int index = 0; index < size; index++)
        if (o.equals(elementData[index])) {
            fastRemove(index);
            return true;
        }
}
return false;

// 删除集合元素

private void fastRemove(int index) {

modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)
    System.arraycopy(elementData, index+1, elementData, index,
                     numMoved);
elementData[--size] = null; // clear to let GC do its work

修改元素方法：set

// 根據索引修改元素，直接索引指向新的元素值。

public E set(int index, E element) {

rangeCheck(index);

E oldValue = elementData(index);
elementData[index] = element;
return oldValue;

通過上面代碼可以發現，ArrayList 集合檢索元素效率較高，比較适合，而對于增删效率較低。

LinkedList

LinkedList集合.png

LinkedList 類還實作了Deque 接口（Deque 代表算端隊列，與 List 接口不同，此接口不支援通過索引通路元素），是以LinkedList 是一個List集合也是一個雙端隊列。

LinkedList類-1.png

private static class Node {

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;
}

LinkedList 是一個連結清單資料結構，其中維護了一個内部類Node做為連結清單中的節點，first 是指向首節點，last 是指向尾節點。每個Node節點都記錄上一個節點、下一個節點的引用，和目前節點所存儲的元素。

連結清單結構如圖：

雙向連結清單結構圖.png

從查找，增加，删除，修改元素部分方法看LinkedList集合适合哪些操作（從底層資料結構就能夠發現）

查找元素方法：get

// 根據索引查找元素，由于連結清單沒有索引，是以需要從頭部或尾部周遊查找。ArrayList 和 LinkedList底層資料結構不同導緻的 ArrayList集合中查找元素效率更高，因為ArrayList底層是數組，可以直接根據index索引擷取元素。

checkElementIndex(index);
return node(index).item;

Node node(int index) {

// 如果要找的元素位置小于集合長度的1/2,就從前向後周遊，否則從後向前周遊，由此可知越向中間效率越低
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;
}

由于底層資料結構不同，LinkedList增加元素效率要比ArrayList效率高，ArrayList存在擴容和拷貝等操作。

// 向尾部添加元素

linkLast(e);
return true;

void linkLast(E e) {

final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null); // 建立一個新節點
last = newNode; // 将新節點指向尾節點（last）
if (l == null) 
    first = newNode;//  如果newNode是集合中唯一進制素（初始是空集合），那麼也将newNode指向首節點（first）
else
    l.next = newNode; // 原last節點下一個元素的引用指向新的節點（newNode）
size++;
modCount++;

// 在指定位置添加元素，index 位置越靠近中間插入效率越低，随着集合長度增大而增大

public void add(int index, E element) {

checkPositionIndex(index);

if (index == size) // index==size 說明集合為空或者在集合末尾添加元素
    linkLast(element);
else
    linkBefore(element, node(index));

// 連結清單和數組不同，不能直接根據索引獲得元素，連結清單需要從頭或尾部循環周遊到指定位置獲得元素

// 如果要找的元素位置小于集合長度的1/2,就從前向後周遊，否則從後向前周遊，是以向中間效率越低
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;
}

// 在 succ節點之前插入元素

void linkBefore(E e, Node succ) {

final Node<E> pred = succ.prev; 
final Node<E> newNode = new Node<>(pred, e, succ);// 建立一個新節點
succ.prev = newNode; // 
if (pred == null)
   // 說明 succ 是首節點
    first = newNode;
else
    pred.next = newNode;
size++;
modCount++;

LinkedList修改元素時需要先周遊找到元素，ArrayList可以直接根據索引獲得元素，是以LinkedList效率較低，當元素越靠近中間位置越明顯。

checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;

// 根據索引周遊出元素節點

// 如果要找的元素位置小于集合長度的1/2,就從前向後周遊，否則從後向前周遊，是以向中間效率越低

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;
}

和ArrayList相比不存在移動拷貝情況，是以LinkedList删除元素效率比ArrayList高

checkElementIndex(index);
return unlink(node(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;
}

E unlink(Node x) {

// assert x != null;
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;

if (prev == null) {
    first = next;
} else {
    prev.next = next;
    x.prev = null;
}

if (next == null) {
    last = prev;
} else {
    next.prev = prev;
    x.next = null;
}

x.item = null;
size--;
modCount++;
return element;

LinkedList 實作了Deque接口，是一個雙端隊列，是以LinkedList又包含如下常用方法：

Deque接口部分方法.png

源碼中“有趣”的設計#

方法重複定義

源碼中Collection接口中的多個方法在List接口中又重複定義了一次，既然List 已經繼承了Collection接口，為什麼重複定義，曆史原因？先有List後有Collection？

Collection接口-1.png

List接口-1.png

重複實作接口

AbstractList 已經實作List接口，ArrayList繼承 AbstractList，然而ArrayList源碼又實作了 List接口。

ArrayList類.png

AbstractListl類.png

網上搜了下答案：

重複實作接口.png

意思是他問過這塊的開發者,這是一個錯誤。很久以前認為有價值的。

不知道這個答案是否正确？

https://stackoverflow.com/questions/2165204/why-does-linkedhashsete-extend-hashsete-and-implement-sete

小結#

List集合和Set集合都是繼承Collection接口，Collection是List和Set的最上級接口，List接口下有兩個常用的實作類，分别為ArrayList和LinkedList，而LinkedList又實作Deque接口，是以LinkedList即是List集合也是一個雙端隊列。

ArrayList是基于數組資料結構而實作的，而LinkedList是基于連結清單資料結構實作的，從資料結構特點和源碼實作上來看，ArrayList可以根據索引快速擷取到元素，而增加元素時需要數組的擴容和拷貝，删除元素時需要數組的移動拷貝，是以ArrayList集合對查找和修改元素效率較好，對增删效率略低。

LinkedList的連結清單資料結構不能根據索引直接快速擷取元素節點，必須從頭部，或者尾部周遊到索引位置（如果索引值小于集合長度的1/2時就從頭部開始周遊，否則從尾部開始周遊，是以索引值處于中間時周遊效率會比位于兩端要差。）而增加或删除元素時隻需要将上下節點重新指向新的節點對象引用即可，不存在擴容，移動等情況，是以LinkedList和ArrayList相比更适合增加和删除元素操作，對查找操作效率較低。

轉載請注明出處：

https://www.cnblogs.com/newobjectcc/p/10789188.html#

Java集合 - List介紹及源碼解析

繼續閱讀

關于Gradle配置的小結

Java小案例——随機數猜測随機數猜測

nginx location中斜線的位置的重要性

27 Best Free Eclipse Plug-ins for Java Developer to be ProductiveCode Quality PluginsText Editor PluginsDependency ManagementVersion Control Integration PluginsFramework Development Continuous Integration Related PluginsOther Utility Plugins

Java String.format方法的簡單使用

neo4j之cypher使用文檔

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

spark/scala關于【資源檔案】加載方法概述外部檔案加載方案測試資源檔案打包入jar包中小結

mybatis_入門程式Mybatis入門

AOP程式設計_Android優雅權限架構(1)概念基礎，2021金三銀四前言正文大綱正文

Effective Java 8:通用程式設計

OOM三種類型

工廠模式-三種類型

【遞歸】高效率求2的n次幂

win10本地scala和spark安裝安裝scala安裝spark

scala (3) Function 和 Method