前面描述了线性表的顺序存储结构顺序表的各种操作,Java中ArrayList的实现就是数组
ArrayList
- 基于顺序表数组实现,允许空值以及null,可自动扩容
- 线程不安全
基本操作
List<String> list = new ArrayList();
list.add("data1");
list.add(0,"data2");
list.get(0);
list.remove(0);
list.clear();
构造方法
//默认初始容量
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 boolean add(E e) {
ensureCapacityInternal(size + 1);//判定并给出可以放置新元素的空间
elementData[size++] = e;//赋值
return true;
}
- 指定位置插入
public void add(int index, E element) {
//检查index的合法性
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
//判定并给出可以放置新元素的空间
ensureCapacityInternal(size + 1);
//将index之后的数据后移一位
System.arraycopy(elementData, index, elementData, index + 1, size - index);
elementData[index] = element;//赋值
size++;
}
- 判定并给出可以放置新元素的空间有两种可能
- 空间足够,直接赋值
- 空间不够了,需扩容后赋值
//计算最小容量
private void ensureCapacityInternal(int minCapacity) {
//刚初始化状态下,首次添加数据时默认先给数组DEFAULT_CAPACITY空间
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;//根据api解释,modCount是指操作list多少次
//当新计算的最小容量比当前数组容量大时,扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {//扩容方法
int oldCapacity = elementData.length;//原数组长度
int newCapacity = oldCapacity + (oldCapacity >> 1);//扩容至原数组的1.5倍
//扩容后的长度仍比最小容量小,直接使用最小容量,一般在空list刚添加第一条数据时触发
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)//数组太大了,一般也不会触发吧
newCapacity = hugeCapacity(minCapacity);//溢出判定
//建立一个新的数组,将原数组中的数组复制进来
elementData = Arrays.copyOf(elementData, newCapacity);
}
获取元素
public E get(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
return (E) elementData[index];
}
删除元素
public E remove(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
modCount++;
E oldValue = (E) 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 void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}
清空
public void clear() {
modCount++;
// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}