ArrayList
底层实现是数组，访问元素效率高 (查询快，插入、修改、删除元素慢)
与LinkedList相比，它效率高，但线程不安全。
ArrayList数组是一个可变数组，可以存取包括null在内的所有元素
底层使用数组实现
transient Object[] elementData;
构造方法
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
transient Object[] elementData;
private int size;
// 构造一个空列表
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA ;
}
// 构造一个指定初始容量的空列表
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);
}
}
// 构造一个指定Collection元素的列表，这些元素按照Connection元素的迭代返回顺序进行排列
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;
}
}
存储
// 在列表的指定位置的元素用element替代，并且返回该位置原来的元素
public E set(int index, E element) {
rangeCheck(index); // 检查数组容量，抛出：IndexOutOfBoundsException
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
// 在列表的尾部添加指定元素
public boolean add(E e) {
ensureCapacityInternal(size + 1); // 数组扩容
elementData[size++] = e;
return true;
}
// 在列表的指定位置添加元素
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
// src:源数组,srcPro:源数组中的起始位置
// dest:目标数组，destPost:目标数组的起始位置，length:要复制的数组元素数量
// 将当前位于该位置的元素以及所有后续元素后移一个位置
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
// 用element替换index位置的元素
elementData[index] = element;
size++;
}
// 在列表的尾部添加Connection中的元素，元素顺序按照Connection迭代器返回的顺序
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray(); // 转化为一个数组
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
// Increments modCount!!
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}
// 在列表的指定位置添加Connection中的元素，元素顺序按照Connection迭代器返回的顺序
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
int numMoved = size - index;
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}
读取
// 移除此列表指定位置上的元素
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;
}
// 移除此列表中的某个元素
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;
}
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
}
数组扩容
每当向数组中添加元素时，都需要去检查添加元素后元素的个数是否超出当前数组的长度，如果超出，数组将会进行扩容，以满足添加数据的需求。
public void ensureCapacity(int minCapacity) {
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA )
? 0 : DEFAULT_CAPACITY;
if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA ) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = 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);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
手写ArrayList
public class MyArrayList /*implements List<E>*/{
private transient Object[] elementData;
private int size; //元素个数
public MyArrayList(){
this(10);
}
public MyArrayList(int initialCapacity) {
if (initialCapacity<0) {
try {
throw new Exception();
} catch (Exception e) {
e.printStackTrace();
}
}
elementData = new Object[initialCapacity];
}
public int size() {
return size;
}
public boolean isEmpty(){
return size == 0;
}
//根据index删掉对象
public void remove(int index) throws Exception {
rangeCheck(index);
int numMoved = size-index-1;
if (numMoved > 0) {
System.arraycopy(elementData, index+1, elementData, index, numMoved);
}
elementData[--size] = null;
}
//删掉对象
public boolean remove(Object obj) throws Exception {
for (int i = 0; i < size; i++) {
if (get(i).equals(obj)) {
remove(i);
}
return true;
}
return true;
}
//修改元素
public Object set(int index , Object obj ) throws Exception{
rangeCheck(index);
Object oldValue = elementData[index];
elementData[index] = obj;
return oldValue;
}
//在指定位置插入元素
public void add(int index,Object obj) throws Exception {
rangeCheck(index);
ensureCapacity();
System.arraycopy(elementData, index, elementData, index+1, size-index);
elementData[index] = obj;
size ++;
}
public void add(Object object) {
ensureCapacity();
/*elementData[size] = object;
size ++;*/
elementData[size++] = object; //先赋值，后自增
}
public Object get(int index) throws Exception {
rangeCheck(index);
return elementData[index];
}
public void rangeCheck(int index) throws Exception {
if (index<0 || index >=size) {
throw new Exception();
}
}
//扩容
public void ensureCapacity() {
//数组扩容和内容拷贝
if (size==elementData.length) {
//elementData = new Object[size*2+1]; 这么写原来数组里的内容丢失
Object[] newArray = new Object[size*2+1];
//拷贝数组里的内容
/*for (int i = 0; i < newArray.length; i++) {
newArray[i] = elementData[i];
}*/
System.arraycopy(elementData, 0, newArray, 0, elementData.length);
elementData = newArray;
}
}
// 测试
public static void main(String[] args) {
MyArrayList myArrayList = new MyArrayList(3);
myArrayList.add("111");
myArrayList.add("222");
myArrayList.add("333");
myArrayList.add("444");
myArrayList.add("555");
try {
myArrayList.remove(2);
myArrayList.add(3, "新值");
myArrayList.set(1, "修改");
} catch (Exception e1) {
// TODO Auto-generated catch block
e1.printStackTrace();
}
System.out.println(myArrayList.size());
for (int i = 0; i < myArrayList.size(); i++) {
try {
System.out.println(myArrayList.get(i));
} catch (Exception e) {
e.printStackTrace();
}
}
}
}
