Java集合ArrayList與LinkedList詳解

更新時(shí)間：2022年08月10日 09:35:16 作者：亞雷???????

這篇文章主要介紹了Java集合ArrayList與LinkedList詳解，對(duì)于ArrayList和LinkedList，他們都是List接口的一個(gè)實(shí)現(xiàn)類，并且我們知道他們的實(shí)現(xiàn)方式各不相同，例如ArrayList底層實(shí)現(xiàn)是一個(gè)數(shù)組

前言

對(duì)于Java程序員，可以說對(duì)于ArrayList和LinkedList可謂是十分熟悉了

對(duì)于ArrayList和LinkedList，他們都是List接口的一個(gè)實(shí)現(xiàn)類，并且我們知道他們的實(shí)現(xiàn)方式各不相同，例如ArrayList底層實(shí)現(xiàn)是一個(gè)數(shù)組，而LinkedList底層實(shí)現(xiàn)是鏈表，對(duì)于數(shù)組來說，插入慢但是查詢快，而對(duì)于鏈表來說查詢慢，插入快

今天我們就來分析分析他們的源碼

ArrayList

我們先看一看ArrayList的類圖。他繼承于AbstractList，而這個(gè)類是List類的的骨架，可以說這個(gè)類是List類的基石

成員屬性

/**
序列化ID
**/
private static final long serialVersionUID = 8683452581122892189L;
/**
默認(rèn)容量
**/
private static final int DEFAULT_CAPACITY = 10;
/**
如果傳入的容量為0，那么將使用這個(gè)空元素?cái)?shù)組
**/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
默認(rèn)空元素?cái)?shù)組，長度為0，傳入元素時(shí)會(huì)初始化為默認(rèn)元素大小
**/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
真正存儲(chǔ)數(shù)據(jù)的數(shù)組
**/
transient Object[] elementData;
/**
列表中元素的個(gè)數(shù)
**/
private int size;

這里需要主要關(guān)注的成員屬性為size和elementData，一個(gè)是元素個(gè)數(shù)，一個(gè)是真正存儲(chǔ)數(shù)據(jù)的數(shù)組

構(gòu)造函數(shù)

/**
指定數(shù)組長度構(gòu)造
**/
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);
    }
}
/**
空參構(gòu)造
**/
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/**
傳入一個(gè)集合，將該集合的元素初始化到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;
    }
}

擴(kuò)容機(jī)制

我們知道ArrayList是一個(gè)動(dòng)態(tài)數(shù)組，但是他的底層實(shí)現(xiàn)是一個(gè)數(shù)組，那他是怎樣保證動(dòng)態(tài)的呢？

ArrayList每次添加元素之前，都會(huì)檢查添加元素后的元素個(gè)數(shù)是否超過數(shù)組長度，如果超出，那么就會(huì)進(jìn)行擴(kuò)容，而數(shù)組擴(kuò)容通過一個(gè)公開的方法實(shí)現(xiàn)，我們也可以手動(dòng)進(jìn)行擴(kuò)容

    public void ensureCapacity(int minCapacity) {
        //判斷數(shù)組是否等于默認(rèn)空數(shù)組，不等于則給minExpand賦值為10
        int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
            ? 0 : DEFAULT_CAPACITY;
        //判斷參數(shù)是否大于minExpand大于的時(shí)候才會(huì)去擴(kuò)容
        if (minCapacity > minExpand) {           
            ensureExplicitCapacity(minCapacity);
        }
    }
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;//記錄數(shù)組修改次數(shù) + 1
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
    //真正擴(kuò)容的方法
    private void grow(int minCapacity) {
        //獲取原來的容量
        int oldCapacity = elementData.length;
        //計(jì)算新容量，新容量大小 = 舊容量大小的1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //如果需要的容量比新容量還小就用需要的容量
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        //如果新容量大于最大容量就用最大的容量
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        //數(shù)據(jù)拷貝
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

我們可以發(fā)現(xiàn)每次擴(kuò)容，ArrayList都會(huì)擴(kuò)容1.5倍，通過位運(yùn)算完成計(jì)算擴(kuò)容大小的，我們知道，擴(kuò)容之后進(jìn)行數(shù)據(jù)遷移這個(gè)操作是很費(fèi)時(shí)間的，比如我們有10w條數(shù)據(jù)，這樣的話，進(jìn)行數(shù)據(jù)遷移的時(shí)候，我們會(huì)耗費(fèi)很長時(shí)間，所以我們建議再初始化的時(shí)候就定義一個(gè)容量，這樣可以讓ArrayList的效率提高很多

add方法

//添加元素到尾部
public boolean add(E e) {
    //檢查是否需要擴(kuò)容
    ensureCapacityInternal(size + 1); 
    //將元素添加到數(shù)組末尾，并把size++
    elementData[size++] = e;
    return true;
}
//添加元素到指定索引
public void add(int index, E element) {
    //檢查index是否越界
    rangeCheckForAdd(index);
    //檢查是否需要擴(kuò)容
    ensureCapacityInternal(size + 1);
    //將index以及之后的元素向后挪動(dòng)一位
    //這樣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轉(zhuǎn)換為數(shù)組
    Object[] a = c.toArray();
    //拿到c的長度
    int numNew = a.length;
    //檢查是否需要擴(kuò)容
    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轉(zhuǎn)換為數(shù)組
    Object[] a = c.toArray();
    //獲取數(shù)組a的長度
    int numNew = a.length;
    //檢查是否需要擴(kuò)容
    ensureCapacityInternal(size + numNew);  // Increments modCount
    //計(jì)算需要移動(dòng)的長度
    int numMoved = size - index;
    if (numMoved > 0)
        //向后移動(dòng)
        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);
    //返回對(duì)應(yīng)數(shù)組中指定索引的元素
    return elementData(index);
}

remove方法

//刪除指定索引的元素
public E remove(int index) {
    //判斷index是否越界
    rangeCheck(index);
    //將數(shù)組修改次數(shù)+1
    modCount++;
    //拿到對(duì)應(yīng)索引的元素
    E oldValue = elementData(index);
    計(jì)算移動(dòng)位置
    int numMoved = size - index - 1;
    if (numMoved > 0)
        //移動(dòng)數(shù)組
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    //size-1，并把尾部元素置為null，這里把尾部置為null主要是為了讓GC起作用
    elementData[--size] = null;

    return oldValue;
}
//刪除第一個(gè)滿足o.equals(elementData[index]的元素
public boolean remove(Object o) {
    if (o == null) {
        //如果o為null使用==進(jìn)行判斷
        //從索引為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;
}

小結(jié)

如果我們的數(shù)據(jù)量很大，我們可以給List估算一個(gè)容量，然后進(jìn)行初始化，否則會(huì)對(duì)效率有影響，畢竟一直進(jìn)行數(shù)據(jù)遷移。
最開始Arraylist的容量為10，每次擴(kuò)容為原先容量的1.5倍，但是如果我們已經(jīng)擴(kuò)容的數(shù)組，是不能進(jìn)行縮容的，例如我們添加了10個(gè)元素，這個(gè)時(shí)候已經(jīng)擴(kuò)容了，但是我們刪除最后一個(gè)元素，他是不會(huì)進(jìn)行縮容的
我們并沒有看到他方法上有synchronized關(guān)鍵字，所以他也不是線程安全的，我們可以使用Vector或者使用Collections.synchronizedList(list)

LinkedList

對(duì)于LinkedList，它同樣繼承與AbstractList，在前面已經(jīng)說過了，AbstractList是List的骨架，我們還可以看到它實(shí)現(xiàn)了Deque，所以LinkedList既可以看做一個(gè)鏈表也可以看做是一個(gè)隊(duì)列，同樣也可以看做一個(gè)棧，所以LinkedList比較全能

Node類

我們知道LinkedList是一個(gè)雙向鏈表，那么肯定有一個(gè)個(gè)的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é)點(diǎn)有三個(gè)成員屬性，分別是value，前驅(qū)指針，后繼指針，以及一個(gè)全參構(gòu)造方法

成員屬性

/**
元素個(gè)數(shù)
 */
transient int size = 0;
/**
指向鏈表頭結(jié)點(diǎn)
 */
transient Node<E> first;
/**
指向鏈表尾節(jié)點(diǎn)
 */
transient Node<E> last;
/**
序列化ID
 */
private static final long serialVersionUID = 876323262645176354L;

構(gòu)造函數(shù)

//空參構(gòu)造，沒什么好說的
public LinkedList() {
}
//將集合c的元素添加到鏈表中
public LinkedList(Collection<? extends E> c) {
    //調(diào)用空參構(gòu)造
    this();
    //調(diào)用addAll()這個(gè)方法在下面講述
    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一個(gè)Node節(jié)點(diǎn)，值為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一個(gè)Node節(jié)點(diǎn)，值為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轉(zhuǎn)換為數(shù)組
    Object[] a = c.toArray();
    //拿到c的長度
    int numNew = a.length;
    if (numNew == 0)
        return false;
    //定義兩個(gè)指針，一個(gè)前驅(qū)一個(gè)后繼
    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一個(gè)Node節(jié)點(diǎn)，值為e，前驅(qū)為pred，后繼為null
        Node<E> newNode = new Node<>(pred, e, null);
        //pred為null，證明前驅(qū)為null，當(dāng)前節(jié)點(diǎn)為鏈表的頭結(jié)點(diǎn)
        if (pred == null)
            first = newNode;
        else
            //前驅(qū)節(jié)點(diǎn)后繼指針指向頭結(jié)點(diǎn)
            pred.next = newNode;
        //前驅(qū)節(jié)點(diǎn)后移
        pred = newNode;
    }
    //succ為null證明index索引位于鏈表最后
    if (succ == null) {
        last = pred;
    } else {
        //pred的后繼節(jié)點(diǎn)為succ
        pred.next = succ;
        //succ的前驅(qū)節(jié)點(diǎn)為pred
        succ.prev = pred;
    }

    size += numNew;
    modCount++;
    return true;
}

獲取

//這個(gè)方法是Node類的方法，我們可以看到上面的addAll方法也使用了這個(gè)方法
//這個(gè)方法作用是返回指定索引的非空節(jié)點(diǎn)
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));
}
//刪除頭部元素，這個(gè)方法是Node類的方法
private E unlinkFirst(Node<E> f) {
    //拿到頭節(jié)點(diǎn)的值
    final E element = f.item;
    //拿到頭結(jié)點(diǎn)的next值
    final Node<E> next = f.next;
    //將頭結(jié)點(diǎn)的值置為null(幫助GC)
    f.item = null;
    //將頭結(jié)點(diǎn)的next置為null(幫助GC)
    f.next = null;
    //將頭結(jié)點(diǎn)修改為next
    first = next;
    if (next == null)
        //此時(shí)鏈表沒有元素了
        last = null;
    else
        next.prev = null;
    size--;
    modCount++;
    return element;
}
//刪除尾部元素，這個(gè)方法是Node類的方法
private E unlinkLast(Node<E> l) {
    //拿到尾節(jié)點(diǎn)的值
    final E element = l.item;
    //拿到尾節(jié)點(diǎn)的前驅(qū)
    final Node<E> prev = l.prev;
    //將尾結(jié)點(diǎn)的值置為null(幫助GC)
    l.item = null;
    //將尾結(jié)點(diǎn)的next置為null(幫助GC)
    l.prev = null;
    //將尾指針修改為prev
    last = prev;
    if (prev == null)
        //此時(shí)鏈表沒有元素了
        first = null;
    else
        prev.next = null;
    size--;
    modCount++;
    return element;
}