JDK 普通操作 之 List 合集

hello，大家好啊，不知道大家在平時的作業、學習中List用的多不多，這個我猜比Thread用的人多多了，人均會用

今天就和大家一起看一下一些List的原始碼

用的最最最最最多的List之ArrayList：

先看看ArrayList里面有哪些屬性

/** 默認容量，當不傳入初始化容量時默認為10，但是不是在構造時初始化的，是在第一次添加時擴容的 */
private static final int DEFAULT_CAPACITY = 10;

/** 空實體的空實作(用于建構式傳入初始化容量為0或傳入的集合長度為0) */
private static final Object[] EMPTY_ELEMENTDATA = {};

/** 如果不傳入初始化容量默認elementData為這個 */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/** 用上面這兩個空陣列確定是有參構造還是無參構造 */

/** 陣列 */
transient Object[] elementData; // non-private to simplify nested class access

/** 省略 */
private int size;

接下來看其添加操作：

整個add()方法非常簡單，ensureCapacityInternal()確定內部容量（是否需要擴容），在陣列的下一個位置放入該元素即可

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

這個直接跳過，我們看其內部的兩個具體方法

private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

計算容量：也就是看當前陣列是否初始化了，沒初始化就回傳DEFAULT_CAPACITY

private static int calculateCapacity(Object[] elementData, int minCapacity) {
    // 這里的minCapacity = 當前size + 1
    // 如果是無參構造創建的,即當前內部陣列并沒有初始化
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        // 回傳DEFAULT_CAPACITY
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

確定是否要擴容：

判斷添加元素（size + 1）過后 是否大于 當前 陣列長度 ，大于則擴容

如果上一步是未初始化回傳DEFAULT_CAPACITY，這里的當前陣列長度就為0，也是需要擴容的

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

這是真正的擴容方法，前面都只是前戲😀

首先按照當前容量擴大1.5倍，看看夠不夠，不夠就取當前需要的容量

當然不能太大，最多就Integer.MAX_VALUE，不能再多了

復制一個新的陣列，容量為新容量

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    // 把當前容量擴大1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 擴大1.5倍都還不夠
    if (newCapacity - minCapacity < 0)
        // 就取minCapacity
        newCapacity = minCapacity;
    // 大于上限了
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        // 要不的要不得，最高就Integer.MAX_VALUE,不能再高了
        newCapacity = hugeCapacity(minCapacity);
    // 復制一個新的陣列,容量為新容量
    elementData = Arrays.copyOf(elementData, newCapacity);
}

接下來看一下另一個add()方法：在指定index添加一個元素

首先檢查指定的下標是否合理（是否越界或者小于0）

然后檢查是否需要擴容，和上面同理

把當前陣列的元素從index開始，都給👴往后挪一位，把index這個位置騰出來給新元素

public void add(int index, E element) {
    // check陣列下標是否合理,也就是是否越界或者小于0
    rangeCheckForAdd(index);

    // 是否需要擴容
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 把這個陣列的元素都往后挪一位,讓出地方
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    // 騰出的這個位置給新元素
    elementData[index] = element;
    size++;
}

在看一看獲取操作：

無聊，沒意思，亂懂

public E get(int index) {
    rangeCheck(index);

    return elementData(index);
}

E elementData(int index) {
    return (E) elementData[index];
}

最后看一眼洗掉操作：

整個流程也比較簡單

public E remove(int index) {
    // 這里和上面的check略有不同,不檢查是否小于0,我也不知道為什么,反正小于0就會拋例外
    rangeCheck(index);

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

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

    return oldValue;
}

換個姿勢的remove：

簡單來說就是遍歷陣列，待洗掉元素為null就洗掉元素為null的，不為null就洗掉equals的元素，注意，這里只洗掉第一次出現的元素

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

fastRemove()：和上面remove異曲同工之妙

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
}

下面再看經常被拿出來和ArrayList比較特點的LinkedList

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

再看一下其內部屬性

/** size */
transient int size = 0;

/** 頭節點指標 */
transient Node<E> first;

/** 尾節點指標 */
transient Node<E> last;

添加操作：

擺設，默認會添加到當前鏈表的尾部

public boolean add(E e) {
    linkLast(e);
    return true;
}

整個程序非常之簡單

就是新增一個Node，將新Node prev指標指向尾節點，再把尾節點指向new Node

如果之前尾節點為null，則把頭節點也指向當前節點，說明此時整個鏈表就只有一個節點

如果之前尾節點不為null，則將之前尾節點 的 next 指標指向new Node

void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

另一種添加操作呢：

會判斷index是否為當前鏈表長度，是的話就添加到最后

否則會添加到指定index處

public void add(int index, E element) {
    // check index是否越界
    checkPositionIndex(index);
	
    // 如果待插入元素的index為當前鏈表長度,就把其添加到最后
    if (index == size)
        linkLast(element);
    else
        // 否則
        linkBefore(element, node(index));
}

node()方法：回傳指定index下標處的Node

首先會判斷index在鏈表的前半部分還是后半部分，相當于二分一下

在前半部分就從前往后找，在后半部分就從后往前找

Node<E> node(int index) {
    // assert isElementIndex(index);

    // 這里做了一個優化,判斷index是否為size的一半,相當于二分一下
    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;
    }
}

將一個Node添加到另一個Node前面，基本操作

void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    final Node<E> pred = succ.prev;
    final Node<E> newNode = new Node<>(pred, e, succ);
    succ.prev = newNode;
    // 如果之前的前驅節點為null,說明他是head節點
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    size++;
    modCount++;
}

獲取方法：

和上面一樣，是有一個二分的優化

public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

洗掉操作：

public E remove(int index) {
    // 判斷index是否大于0小于size
    checkElementIndex(index);
    return unlink(node(index));
}

將一個節點洗掉：

E unlink(Node<E> 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;
}

最后講一下一個很高大上的List之CopyOnWriteArrayList：

先看一下其屬性：

/** lock鎖實作 */
final transient ReentrantLock lock = new ReentrantLock();

/** 內部元素陣列 */
private transient volatile Object[] array;

這個屬性array只能通過這兩個方法訪問和賦值，好家伙，這是連類內部都要封裝

final Object[] getArray() {
    return array;
}

final void setArray(Object[] a) {
    array = a;
}

添加操作：

先加鎖，然后將當前陣列擴容1，賦值新元素給最后一個下標處，再把當前內部陣列替換，最后解鎖

public boolean add(E e) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        Object[] elements = getArray();
        int len = elements.length;
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        newElements[len] = e;
        setArray(newElements);
        return true;
    } finally {
        lock.unlock();
    }
}

其他添加操作和洗掉操作就不過多bb了，大同小異，主要依靠ReentrantLock控制當前只能有一個執行緒進行寫操作

獲取操作：

沒有加鎖，整個獲取操作是可以多執行緒并行訪問的
因為內部陣列并無修改，只有替換，且用了volatile修飾，保證了執行緒可見性
即如果另一個執行緒替換了內部陣列，其他執行緒會立馬知曉這個執行緒的修改，也就是獲取到的都是最新的值

public E get(int index) {
    return get(getArray(), index);
}

private E get(Object[] a, int index) {
    return (E) a[index];
}

OK，這就是JDK比較經典的List實作類，這不在評論區總結一下？