一：简述
List集合代表一个有序集合，集合中每个元素都有其对应的顺序索引。List集合允许使用重复元素，可以通过索引来访问指定位置的集合元素。
List接口继承于Collection接口，它可以定义一个允许重复的有序集合。因为List中的元素是有序的，所以我们可以通过使用索引（元素在List中的位置，类似于数组下标）来访问List中的元素，这类似于Java的数组。
List接口为Collection直接接口。List所代表的是有序的Collection，即它用某种特定的插入顺序来维护元素顺序。用户可以对列表中每个元素的插入位置进行精确地控制，同时可以根据元素的整数索引（在列表中的位置）访问元素，并搜索列表中的元素。实现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这个接口中，提供了对集合进行操作的增、删、改、查方法，我们知道，ArrayList和LinkedList都实现了List接口，但它们的底层实现分别是线性表与链表，所以，对应的增、删、改、查方法肯定也不一样，下面的分析也将从这几个方法入手。
ArrayList
1、成员变量
在ArrayList的源码中，成员变量并不多，下面就截出其中几个重要的变量进行说明。
public class ArrayList<E> extends AbstractList<E>implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
// 序列版本号
private static final long serialVersionUID = 8683452581122892189L;
// 默认初始化容量
private static final int DEFAULT_CAPACITY = 10;
// 空数组，用来实例化不带容量大小的构造函数
private static final Object[] EMPTY_ELEMENTDATA = {};
// 保存ArrayList中数据的数组
private transient Object[] elementData;
// ArrayList中实际数据的数量
private int size;
DEFAULT_CAPACITY：默认的数组长度
EMPTY_ELEMENTDATA：默认的空数组
DEFAULTCAPACITY_EMPTY_ELEMENTDATA：默认的空数组（与EMPTY_ELEMENTDATA有点区别，在不同的构造函数中用到）
elementData：真正用于存放数据的数组
size：数组元素个数
ArrayList的底层实现是数组，数组必定是有限长度的，ArrayList中默认的数组大小是10。
2、构造函数
public ArrayList() {
super();
this.elementData = EMPTY_ELEMENTDATA;
}
这个构造函数是开发最常用的，可以看到，它仅仅只是让elementData等于一个空数组（DEFAULTCAPACITY_EMPTY_ELEMENTDATA）而已。
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
this.elementData = new Object[initialCapacity];
}
这个构造函数可以指定初始化数组的长度，当initialCapacity大于0时，为elementData创建一个长度为initialCapacity的Object数组；当initialCapacity等于0时，则让elementData等于一个空数组（EMPTY_ELEMENTDATA）。
3、增
1）add(E e)
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
在前面已经提到了，size是一个成员变量，表示ArrayList中的元素个数。在这个方法中，先调用了ensureCapacityInternal()方法确保数组有足够的容量，再对将元素添加到elementData数组中。下面就来看看ensureCapacityInternal()方法是如何确保数组有足够的容量的。
private void ensureCapacityInternal(int minCapacity) {
// 如果是个空数组
if (elementData == EMPTY_ELEMENTDATA) {
// 取minCapacity和10的较大者
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
// 如果数组已经有数据了
ensureExplicitCapacity(minCapacity);
}
// 确保数组容量大于ArrayList中元素个数
private void ensureExplicitCapacity(int minCapacity) {
modCount++; // 将“修改统计数”+1
// 如果实际数据容量大于数组容量，就给数组扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
该方法结合ensureExplicitCapacity()方法，总的来说就是计算并扩大最小的容器体积。
这里就用到了DEFAULTCAPACITY_EMPTY_ELEMENTDATA这个空数组，如果此时elementData与DEFAULTCAPACITY_EMPTY_ELEMENTDATA相等，说明开发者使用的是无参构造函数创建了集合，而且是添加第一个元素，此时的容器大小为0。
// 确保数组容量大于ArrayList中元素个数
private void ensureExplicitCapacity(int minCapacity) {
modCount++; // 将“修改统计数”+1
// 如果实际数据容量大于数组容量，就给数组扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
当minCapacity - elementData.length > 0时，说明当前数组（容器）的空间不够了，需要扩容，所以调用grow()方法。
modCount只是一个计数变量而已，源码中有很多地方出现，无须理会。
// 增大数组空间
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1); // 在原来容量的基础上加上
// 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集合进行扩容的，它计算出新的容器大小（即newCapacity），并确保了newCapacity不会比minCapacity小，最后调用Arrays.copyOf()创建一个新的数组并将数据拷贝到新数组中，最后让elementData进行引用。
oldCapacity >> 1 等价于 oldCapacity / 2，也就是说ArrayList默认的扩容大小是当前数组大小的一半。
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++;
}
经过对add(E e)方法进行分析，这个增加方法就很容易理解了，它先确保容器有足够大的空间，没有就扩容，然后将elementData数组中从index位置开始的所有元素往后"移动"1位，再对数组的index位置进行元素赋值，最后将记录集合中元素个数的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表示在执行删除操作时数组需要移动的元素个数，将elementData数组中从index后一位开始的所有元素（即numMoved个元素）往前"移动"1位（这样一移动，index位置的元素会被后面的元素覆盖，间接起到了删除元素的作用），然后把最后的那个元素置空，同时将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()方法的代码不是可以复用么。。。）
5、查 & 改
ArrayList的修改和获取元素的方法相当简单，就是对elementData数组进行简单操作罢了，这里就列出源码看看就好了。
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.定义实现类
package com.example.xg.util;
import java.util.Arrays;
public class XywArrayList<T> implements XywList<T> {
//ArrayList中数据的数组
private transient Object[] elementData;
/*数组实际容量*/
private int size;
/*初始化容量为10*/
public XywArrayList() {
this(10);
}
public XywArrayList(int initialCapacity) {
if(initialCapacity < 0) {
throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
}
// 初始化数组容量
elementData = new Object[initialCapacity];
}
@Override
public void add(T t) {
// TODO Auto-generated method stub
//1.如果存入的对象超出size大小 就需要扩容
int minCapacity=size+1;
if(size == elementData.length) {
// 获取原来数组的长度 2
int oldCapacity = elementData.length;
// oldCapacity >> 1 理解成 oldCapacity/2 新数组的长度是原来长度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
/*通过下标获取到对象*/
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("数组越界啦!");
}
}
}
这里就完成里集合基本方法
测试
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));
}
}
结果：
***************小郭
***************小张
***************小李
测试删除方法
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));
}
}
结果
***************小张
***************小李
四：总结
ArrayList底层实现是数组。
当使用无参数构造函数创建ArrayList对象时，ArrayList对象中的数组初始长度为0（是一个空数组）。
ArrayList的扩容策略是每次都增加当前数组长度的一半（非固定分配）1.5倍。
ArrayList的扩容方式是直接创建一个新的数组，并将数据拷贝到新数组中。
默认初始容量为10
jdk 1.7之后 数组默认数据大小代码存放在add方法 (JDK1.6的时候 默认构造函数初始化elementData大小)
网友评论