前言

android 開發(fā)適配器里面存放數(shù)據(jù)用的最多的就是ArrayList，大家有看過ArrayList源碼嗎，ArrayList的優(yōu)點(diǎn)和確定是什么，有沒有什么數(shù)據(jù)結(jié)構(gòu)可以替換ArrayList呢？本篇文章帶領(lǐng)大家從源碼角度出發(fā)一起看看ArrayList和LinkedList。

1. ArrayList

ArrayList本質(zhì)是數(shù)組。它里面的元素都保存在elementdata[] 這樣一個(gè)數(shù)組里面

public void add(int index, E element) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

    ensureCapacityInternal(size + 1);  // Increments modCount!! 給ArrayList擴(kuò)容
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;
}

add的核心代碼是System.arraycopy(elementData, index, elementData, index + 1, size - index);

private static void arraycopy(char[] src, int srcPos, char[] dst, int dstPos, int length) {
    if (src == null) {
        throw new NullPointerException("src == null");
    }
    if (dst == null) {
        throw new NullPointerException("dst == null");
    }
    if (srcPos < 0 || dstPos < 0 || length < 0 ||
        srcPos > src.length - length || dstPos > dst.length - length) {
        throw new ArrayIndexOutOfBoundsException(
            "src.length=" + src.length + " srcPos=" + srcPos +
            " dst.length=" + dst.length + " dstPos=" + dstPos + " length=" + length);
    }
    if (length <= ARRAYCOPY_SHORT_CHAR_ARRAY_THRESHOLD) {
        // Copy char by char for shorter arrays.
        if (src == dst && srcPos < dstPos && dstPos < srcPos + length) {
            // Copy backward (to avoid overwriting elements before
            // they are copied in case of an overlap on the same
            // array.)
            for (int i = length - 1; i >= 0; --i) {
                dst[dstPos + i] = src[srcPos + i];
            }
        } else {
            // Copy forward.
            for (int i = 0; i < length; ++i) {
                dst[dstPos + i] = src[srcPos + i];
            }
        }
    } else {
        // Call the native version for longer arrays.
        arraycopyCharUnchecked(src, srcPos, dst, dstPos, length);
    }
}

為了方便大家了解，我畫了一個(gè)圖

image

所以copy的操作元素就是遍歷元素，然后進(jìn)行替換操作。
同理，remove()方法也是用了System.copy()方法，只不過是把元素往前挪位置了

掌握了ArrayList方法的原理后我們不難發(fā)現(xiàn)，如果我們要往ArrayList中添加元素的時(shí)候，如果是往最后一個(gè)位置添加元素的時(shí)候速度是最快的，往中間添加元素，因?yàn)樯婕暗皆匚灰撇僮?，所以效率相?duì)較低。由于arraylist本質(zhì)是數(shù)組，數(shù)組在內(nèi)存中是連續(xù)的空間，所以get(index)是很快的，直接通過elementdata[index]這個(gè)數(shù)組就能拿到。

從時(shí)間復(fù)雜度來說，ArrayList插入和刪除的時(shí)候時(shí)間復(fù)雜度為O(n)，獲取元素的時(shí)間復(fù)雜度為O(1)。

那么有沒有插入和刪除相對(duì)較快的數(shù)據(jù)結(jié)構(gòu)呢。

2. LinkedList

LinkedList是一個(gè)雙鏈表。

public void add(int index, E element) {
    checkPositionIndex(index);

    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}

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;
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    size++;
    modCount++;
}

就是把之前的鏈斷開，前面的元素的尾結(jié)點(diǎn)指向新添加的元素，新添加的元素的頭結(jié)點(diǎn)指向前一個(gè)元素。后一個(gè)元素的頭結(jié)點(diǎn)指向當(dāng)前元素，當(dāng)前元素的尾結(jié)點(diǎn)指向后一個(gè)元素。

同樣的畫個(gè)圖方便大家了解
<meta charset="utf-8">

2.png

接下來看下get()方法

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

...

Node<E> node(int index) {
    // assert isElementIndex(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;
    }
}

get()方法最終用for()循環(huán)是輪詢獲取元素，所以效率較低。

從時(shí)間復(fù)雜度來說，LinkedList插入和刪除的時(shí)候時(shí)間復(fù)雜度為O(1)，獲取元素的時(shí)間復(fù)雜度為O(n)。

有沒有一種數(shù)據(jù)結(jié)構(gòu)能夠結(jié)合以上兩個(gè)的優(yōu)點(diǎn)呢，下篇文章咱們一起學(xué)習(xí)下HashMap的原理。