一：簡述

List集合代表一個(gè)有序集合沪停，集合中每個(gè)元素都有其對應(yīng)的順序索引。List集合允許使用重復(fù)元素谈竿，可以通過索引來訪問指定位置的集合元素匪燕。

List接口繼承于Collection接口，它可以定義一個(gè)允許重復(fù)的有序集合侮叮。因?yàn)長ist中的元素是有序的避矢，所以我們可以通過使用索引（元素在List中的位置，類似于數(shù)組下標(biāo)）來訪問List中的元素，這類似于Java的數(shù)組审胸。

List接口為Collection直接接口分尸。List所代表的是有序的Collection，即它用某種特定的插入順序來維護(hù)元素順序歹嘹。用戶可以對列表中每個(gè)元素的插入位置進(jìn)行精確地控制箩绍，同時(shí)可以根據(jù)元素的整數(shù)索引（在列表中的位置）訪問元素，并搜索列表中的元素尺上。實(shí)現(xiàn)List接口的集合主要有：ArrayList材蛛、LinkedList、Vector怎抛、Stack卑吭。

二：分析

List

在分析ArrayList之前，我們先來看看集合的接口——List马绝。

public interface List?extends Collection{?

boolean add(E e);

void add(intindex, E element);

boolean remove(Object o);

E remove(intindex);

E set(intindex, E element);

E get(intindex);?

在List這個(gè)接口中豆赏，提供了對集合進(jìn)行操作的增、刪富稻、改掷邦、查方法，我們知道椭赋，ArrayList和LinkedList都實(shí)現(xiàn)了List接口抚岗，但它們的底層實(shí)現(xiàn)分別是線性表與鏈表，所以哪怔，對應(yīng)的增宣蔚、刪、改认境、查方法肯定也不一樣胚委，下面的分析也將從這幾個(gè)方法入手。

ArrayList

1叉信、成員變量

在ArrayList的源碼中亩冬，成員變量并不多，下面就截出其中幾個(gè)重要的變量進(jìn)行說明茉盏。

public class ArrayList<E> extends AbstractList<E>implements List<E>, RandomAccess, Cloneable, java.io.Serializable {

// 序列版本號

private static final long serialVersionUID = 8683452581122892189L;

// 默認(rèn)初始化容量

private static final int DEFAULT_CAPACITY = 10;

// 空數(shù)組鉴未，用來實(shí)例化不帶容量大小的構(gòu)造函數(shù)

private static final Object[] EMPTY_ELEMENTDATA = {};

// 保存ArrayList中數(shù)據(jù)的數(shù)組

private transient Object[] elementData;

// ArrayList中實(shí)際數(shù)據(jù)的數(shù)量

private int size;

DEFAULT_CAPACITY：默認(rèn)的數(shù)組長度

EMPTY_ELEMENTDATA：默認(rèn)的空數(shù)組

DEFAULTCAPACITY_EMPTY_ELEMENTDATA：默認(rèn)的空數(shù)組（與EMPTY_ELEMENTDATA有點(diǎn)區(qū)別，在不同的構(gòu)造函數(shù)中用到）

elementData：真正用于存放數(shù)據(jù)的數(shù)組

size：數(shù)組元素個(gè)數(shù)

ArrayList的底層實(shí)現(xiàn)是數(shù)組鸠姨，數(shù)組必定是有限長度的，ArrayList中默認(rèn)的數(shù)組大小是10淹真。

2讶迁、構(gòu)造函數(shù)

public ArrayList() {

super();

this.elementData = EMPTY_ELEMENTDATA;

}

這個(gè)構(gòu)造函數(shù)是開發(fā)最常用的，可以看到核蘸，它僅僅只是讓elementData等于一個(gè)空數(shù)組（DEFAULTCAPACITY_EMPTY_ELEMENTDATA）而已巍糯。

public ArrayList(int initialCapacity) {

super();

if (initialCapacity < 0)

throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);

this.elementData = new Object[initialCapacity];

}

這個(gè)構(gòu)造函數(shù)可以指定初始化數(shù)組的長度啸驯，當(dāng)initialCapacity大于0時(shí)，為elementData創(chuàng)建一個(gè)長度為initialCapacity的Object數(shù)組祟峦；當(dāng)initialCapacity等于0時(shí)罚斗，則讓elementData等于一個(gè)空數(shù)組（EMPTY_ELEMENTDATA）。

3宅楞、增

1）add(E e)

public boolean add(E e) {

ensureCapacityInternal(size + 1); // Increments modCount!!

elementData[size++] = e;

return true;

}

在前面已經(jīng)提到了针姿，size是一個(gè)成員變量，表示ArrayList中的元素個(gè)數(shù)厌衙。在這個(gè)方法中距淫，先調(diào)用了ensureCapacityInternal()方法確保數(shù)組有足夠的容量，再對將元素添加到elementData數(shù)組中婶希。下面就來看看ensureCapacityInternal()方法是如何確保數(shù)組有足夠的容量的榕暇。

private void ensureCapacityInternal(int minCapacity) {

// 如果是個(gè)空數(shù)組

if (elementData == EMPTY_ELEMENTDATA) {

// 取minCapacity和10的較大者

minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);

}

// 如果數(shù)組已經(jīng)有數(shù)據(jù)了

ensureExplicitCapacity(minCapacity);

}

// 確保數(shù)組容量大于ArrayList中元素個(gè)數(shù)

private void ensureExplicitCapacity(int minCapacity) {

modCount++; // 將“修改統(tǒng)計(jì)數(shù)”+1

// 如果實(shí)際數(shù)據(jù)容量大于數(shù)組容量，就給數(shù)組擴(kuò)容

if (minCapacity - elementData.length > 0)

grow(minCapacity);

}

該方法結(jié)合ensureExplicitCapacity()方法喻杈，總的來說就是計(jì)算并擴(kuò)大最小的容器體積彤枢。

這里就用到了DEFAULTCAPACITY_EMPTY_ELEMENTDATA這個(gè)空數(shù)組，如果此時(shí)elementData與DEFAULTCAPACITY_EMPTY_ELEMENTDATA相等筒饰，說明開發(fā)者使用的是無參構(gòu)造函數(shù)創(chuàng)建了集合堂污，而且是添加第一個(gè)元素，此時(shí)的容器大小為0龄砰。

// 確保數(shù)組容量大于ArrayList中元素個(gè)數(shù)

private void ensureExplicitCapacity(int minCapacity) {

modCount++; // 將“修改統(tǒng)計(jì)數(shù)”+1

// 如果實(shí)際數(shù)據(jù)容量大于數(shù)組容量盟猖，就給數(shù)組擴(kuò)容

if (minCapacity - elementData.length > 0)

grow(minCapacity);

}

當(dāng)minCapacity - elementData.length > 0時(shí)，說明當(dāng)前數(shù)組（容器）的空間不夠了换棚，需要擴(kuò)容式镐，所以調(diào)用grow()方法。

modCount只是一個(gè)計(jì)數(shù)變量而已固蚤，源碼中有很多地方出現(xiàn)娘汞，無須理會(huì)。

// 增大數(shù)組空間

private void grow(int minCapacity) {

// overflow-conscious code

int oldCapacity = elementData.length;

int newCapacity = oldCapacity + (oldCapacity >> 1); // 在原來容量的基礎(chǔ)上加上

// oldCapacity/2

if (newCapacity - minCapacity < 0)

newCapacity = minCapacity; // 最少保證容量和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);

}

grow()方法是用來給ArrayList集合進(jìn)行擴(kuò)容的夕玩，它計(jì)算出新的容器大心阆摇（即newCapacity），并確保了newCapacity不會(huì)比minCapacity小燎孟，最后調(diào)用Arrays.copyOf()創(chuàng)建一個(gè)新的數(shù)組并將數(shù)據(jù)拷貝到新數(shù)組中禽作，最后讓elementData進(jìn)行引用。

oldCapacity >> 1 等價(jià)于 oldCapacity / 2揩页，也就是說ArrayList默認(rèn)的擴(kuò)容大小是當(dāng)前數(shù)組大小的一半旷偿。

2）add(int index, E element)

public void add(int index, E element) {

rangeCheckForAdd(index);

ensureCapacityInternal(size + 1); // Increments modCount!!

System.arraycopy(elementData, index, elementData, index + 1, size - index);

elementData[index] = element;

size++;

}

經(jīng)過對add(E e)方法進(jìn)行分析，這個(gè)增加方法就很容易理解了，它先確保容器有足夠大的空間萍程，沒有就擴(kuò)容幢妄，然后將elementData數(shù)組中從index位置開始的所有元素往后"移動(dòng)"1位，再對數(shù)組的index位置進(jìn)行元素賦值茫负，最后將記錄集合中元素個(gè)數(shù)的size變量加1蕉鸳。

4、刪

1）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);

elementData[--size] = null; // clear to let GC do its work

return oldValue;

}

numMoved表示在執(zhí)行刪除操作時(shí)數(shù)組需要移動(dòng)的元素個(gè)數(shù)忍法，將elementData數(shù)組中從index后一位開始的所有元素（即numMoved個(gè)元素）往前"移動(dòng)"1位（這樣一移動(dòng)潮尝，index位置的元素會(huì)被后面的元素覆蓋，間接起到了刪除元素的作用）缔赠，然后把最后的那個(gè)元素置空衍锚，同時(shí)將size變量減1。

2）remove(Object o)

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;

}

該方法的操作與remove(int index)基本一致嗤堰，這里就不再說明了戴质。（fastRemove()方法的代碼不是可以復(fù)用么。踢匣。告匠。）

5、查 & 改

ArrayList的修改和獲取元素的方法相當(dāng)簡單离唬，就是對elementData數(shù)組進(jìn)行簡單操作罷了后专，這里就列出源碼看看就好了。

1）get(int index)

public E get(int index) {

rangeCheck(index);

checkForComodification();

return JDKArrayList.this.elementData(offset + index);

}

2）set(int index, E element)

public void set(E e) {

if (lastRet < 0)

throw new IllegalStateException();

checkForComodification();

try {

ArrayList.this.set(offset + lastRet, e);

} catch (IndexOutOfBoundsException ex) {

throw new ConcurrentModificationException();

}

三：開始手寫

1.先定義集合接口-XywList

package com.example.xg.util;

public interface XywList<T> {

public void add(T t);

public T get(int index);

public T remove(int index);

public int getSize();

}

2.定義實(shí)現(xiàn)類

package com.example.xg.util;

import java.util.Arrays;

public class XywArrayList<T> implements XywList<T> {

//ArrayList中數(shù)據(jù)的數(shù)組

private transient Object[] elementData;

/*數(shù)組實(shí)際容量*/

private int size;

/*初始化容量為10*/

public XywArrayList() {

this(10);

}

public XywArrayList(int initialCapacity) {

if(initialCapacity < 0) {

throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);

}

// 初始化數(shù)組容量

elementData = new Object[initialCapacity];

}

@Override

public void add(T t) {

// TODO Auto-generated method stub

//1.如果存入的對象超出size大小就需要擴(kuò)容

int minCapacity=size+1;

if(size == elementData.length) {

// 獲取原來數(shù)組的長度 2

int oldCapacity = elementData.length;

// oldCapacity >> 1 理解成 oldCapacity/2 新數(shù)組的長度是原來長度1.5倍

int newCapacity = oldCapacity + (oldCapacity >> 1); // 3

if (newCapacity < minCapacity) {

// 最小容量比新容量要小的,則采用初始容量minCapacity

newCapacity = minCapacity;

}

// System.out.println("oldCapacity:" + oldCapacity + ",newCapacity:"

// + newCapacity);

elementData = Arrays.copyOf(elementData, newCapacity);

}

elementData[size++] = t;

}

@SuppressWarnings("unchecked")

@Override

public T get(int index) {

// TODO Auto-generated method stub

rangeCheck(index);

return (T) elementData[index];

}

@Override

public T remove(int index) {

// TODO Auto-generated method stub

/*通過下標(biāo)獲取到對象*/

T t=get(index);

int numMoved = elementData.length - index - 1;

if(numMoved > 0)

System.arraycopy(elementData, index + 1, elementData, index, numMoved);

elementData[--size] = null;

return t;

}

@Override

public int getSize() {

// TODO Auto-generated method stub

return size;

}

private void rangeCheck(int index) {

if (index >= size) {

throw new IndexOutOfBoundsException("數(shù)組越界啦!");

}

這里就完成里集合基本方法

測試

public static void main(String[] args) {

XywArrayList<Object> list=new XywArrayList<>(2);

list.add("小郭");

list.add("小張");

list.add("小李");

for (int i=0;i<list.getSize();i++) {

System.out.println("***************"+list.get(i));

}

結(jié)果：

***************小郭

***************小張

***************小李

測試刪除方法

public static void main(String[] args) {

XywArrayList<Object> list=new XywArrayList<>(2);

list.add("小郭");

list.add("小張");

list.add("小李");

list.remove(0);

for (int i=0;i<list.getSize();i++) {

System.out.println("***************"+list.get(i));

}

結(jié)果

***************小張

***************小李

四：總結(jié)

ArrayList底層實(shí)現(xiàn)是數(shù)組输莺。

當(dāng)使用無參數(shù)構(gòu)造函數(shù)創(chuàng)建ArrayList對象時(shí)戚哎，ArrayList對象中的數(shù)組初始長度為0（是一個(gè)空數(shù)組）。

ArrayList的擴(kuò)容策略是每次都增加當(dāng)前數(shù)組長度的一半（非固定分配）1.5倍嫂用。

ArrayList的擴(kuò)容方式是直接創(chuàng)建一個(gè)新的數(shù)組型凳，并將數(shù)據(jù)拷貝到新數(shù)組中。

默認(rèn)初始容量為10

jdk 1.7之后數(shù)組默認(rèn)數(shù)據(jù)大小代碼存放在add方法 (JDK1.6的時(shí)候默認(rèn)構(gòu)造函數(shù)初始化elementData大小)

java集合源碼分析-手寫arrayList集合框架

java集合源碼分析-手寫arrayList集合框架

一：簡述

二：分析

三：開始手寫

四：總結(jié)