list容器java_【Java容器】List容器使用方法及源码分析
List容器
ArrayList：使用動態數組保存元素，支持隨機訪問。
Vector：與ArrayList類似，但是它是線程安全的。
LinkedList：使用雙向鏈表保存元素，只能順序訪問，此外可以用作為棧、隊列和雙向隊列。
1 ArrayList
1.1 簡介
基于動態數組實現了List接口。除了List接口的所有方法之外，還提供了調整內部數組大小的方法。該類與Vector類大致相同，區別在于ArrayList是不支持同步的。
size，isEmpty，get，set，iterator和listIterator方法都只需時間復雜度為O(1)。其他的操作時間復雜度為O(n)。且常數因子與LinkedList類相比更低。
每個ArrayList實例都有一個capacity，描述了該列表中實際用于存儲元素的數組的大小。當向列表中添加元素時，capacity會自動增大。使用ensureCapacity方法，可以在向列表中添加大量元素之前先使數組擴容，避免列表自身多次自動擴容。
1.2 存儲結構
ArrayList內部使用一個數組來保存元素，ArrayList的容量就表示該數組的大小，
transient Object[] elementData; // non-private to simplify nested class access
任何空的ArrayList中的elementData數組用一個默認的空數組表示，
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
當向空ArrayList中添加第一個元素時，會擴容到DEFAULT_CAPACITY大小，
private static final int DEFAULT_CAPACITY = 10;
此外，ArrayList中還使用一個size記錄當前保存元素的個數,
private int size;
1.3 添加元素
add(E e)方法可以向ArrayList的末尾添加一個元素，
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
其中會先調用ensureCapacityInternal(int minCapacity)方法對elementData數組的大小進行檢查與擴容，
private void ensureCapacityInternal(int minCapacity) {
// ensureCapacity(int minCapacity)方法返回數組所需要的大小
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
然后調用ensureExplicitCapacity(int minCapacity)方法，
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
使用grow(int minCapacity)方法對數組進行擴容并復制舊數組的元素到新數組中，
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
// 先設置新容量為舊容量的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 如果新容量小于傳入的要求容量，則新容量以要求容量為準
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 如果新容量大于MAX_ARRAY_SIZE(2^31-1-8)
if (newCapacity - MAX_ARRAY_SIZE > 0)
// 判斷要求容量的大小是否大于MAX_ARRAY_SIZE(2^31-1-8)
// 若要求容量大于MAX_ARRAY_SIZE(2^31-1-8)，則新容量為Integer.MAX_VALUE(2^31-1)
// 否則新容量為MAX_ARRAY_SIZE(2^31-1-8)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
// 將舊數組元素復制到新數組中
elementData = Arrays.copyOf(elementData, newCapacity);
}
1.4 獲取元素
get(int index)方法返回列表中指定位置的元素，
public E get(int index) {
// 檢查下標是否合法
rangeCheck(index);
// 返回元素
return elementData(index);
}
1.5 刪除元素
remove(int index)方法刪除列表中指定位置的元素并將其返回，
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);
// 將數組最后一位設為null
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
1.6 fast-fail機制
fail-fast 機制是java集合(Collection)中的一種錯誤機制。作用是在集合的迭代器的迭代期間，如果發現集合被其他線程修改，則拋出異常，避免執行一些不確定的操作。
例如：當某一個線程A通過迭代器去遍歷某集合的過程中，若該集合的內容被其他線程所改變了，那么線程A訪問集合時，就會拋出ConcurrentModificationException異常，產生fail-fast事件。
實現方式：
AbstractList中有一個modCount字段用于記錄容器結構發生變化的次數，
protected transient int modCount = 0;
結構變化指添加或者刪除至少一個元素的所有操作，或者是調整內部數組的大小，若僅僅設置元素的值不算作結構發生變化，例如，
public boolean add(E e) {
ensureCapacityInternal(size + 1); // 增加modCount
elementData[size++] = e;
return true;
}
public E remove(int index) {
rangeCheck(index);
modCount++; // 增加modCount
E oldValue = elementData(index);
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
return oldValue;
}
在使用ArrayList的迭代器時，迭代器中會記錄當前列表的modCount，
private class Itr implements Iterator {
int cursor; // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
int expectedModCount = modCount; // 記錄創建迭代器時，容器的modCount
...
}
在使用迭代器的next()，remove()，previous()，set()或add()方法時，會通過檢測該字段，判斷容器是否被意外地修改了，
// 迭代器類中定義的檢查modCount的方法，在迭代時容器被意外修改時拋出異常
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
如果容器的modCount與迭代器中記錄的expectedModCount不一致，即容器在迭代器遍歷期間被修改，就會返回ConcurrentModificationException異常。
1.7 同步
使用Collections.synchronizedList方法可以獲得一個線程安全的List，
List list = Collections.synchronizedList(new ArrayList(...)); // 獲取線程安全的List
該方法根據輸入容器的具體類型，實例化一個SynchronizedCollection類的子類對象，
static class SynchronizedCollection implements Collection, Serializable {
private static final long serialVersionUID = 3053995032091335093L;
final Collection c; // 底層Collection容器
final Object mutex; // 用于加鎖的對象
//構造方法
SynchronizedCollection(Collection c) {
this.c = Objects.requireNonNull(c); // 輸入的Collection對象
mutex = this; // 自己作為鎖
}
...
}
在該類中，將原來非線程安全的容器與一個鎖組合，并對幾乎所有方法加synchronized關鍵詞，使得對容器的操作是線程安全的。
需要注意，當使用SynchronizedCollection類的迭代器時，需要用戶自己手動加鎖，因為iterator()沒有使用同步鎖，
static class SynchronizedCollection implements Collection, Serializable {
...
// 沒有加synchronized修飾
public Iterator iterator() {
return c.iterator(); // Must be manually synched by user!
}
...
}
2 Vector
2.1 簡介
Vector的實現與ArrayList相似，也是通過動態變化的數組存儲元素，不過使用了synchronized進行同步，
// 添加元素
public synchronized boolean add(E e) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = e;
return true;
}
// 獲取元素
public synchronized E get(int index) {
if (index >= elementCount)
throw new ArrayIndexOutOfBoundsException(index);
return elementData(index);
}
// 刪除元素
public synchronized E remove(int index) {
modCount++;
if (index >= elementCount)
throw new ArrayIndexOutOfBoundsException(index);
E oldValue = elementData(index);
int numMoved = elementCount - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--elementCount] = null; // Let gc do its work
return oldValue;
}
2.2 ArrayList與Vector
Vector是同步的，所以開銷比ArrayList大，性能較低。
Vector每次擴容默認請求的大小是原容量的2倍(可通過capacityIncrement設置)，ArrayList則是原容量1.5倍。
3 LinkedList
3.1 存儲結構
LinkedList使用雙向鏈表保存元素，因此在插入刪除操作的時候相比底層為數組的ArrayList更快，
// 節點的結構
private static class Node {
E item;
Node next;
Node prev;
Node(Node prev, E element, Node next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
// 頭節點
transient Node first;
// 尾節點
transient Node last;
3.2 LinkedList與ArrayList
ArrayList基于動態數組，LinkedList基于雙向鏈表。
ArrayList支持隨機訪問，LinkedList不支持。
LinkedList在任意位置添加刪除元素更快。
創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎總結
以上是生活随笔為你收集整理的list容器java_【Java容器】List容器使用方法及源码分析的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： java mvc模式_Java MVC模
- 下一篇： c盘扩容怎么操作(空间给C盘扩容)