线性表
线性表：零个或多个具有相同类型的数据元素的有限序列，数据元素的个数称为线性表的长度。
线性表的存储结构：分为顺序存储结构和链式存储结构两种
顺序存储结构
Android中以ArrayList为例，看看里面是怎么实现顺序存储的（基于JDK1.7源码）
- 构造方法
public class ArrayList<E> extends AbstractList<E> implements Cloneable, Serializable, RandomAccess {
......
/**
* 最小容量增长值
*/
private static final int MIN_CAPACITY_INCREMENT = 12;
/**
* 用一个变量记录数组存放元素的个数
*/
int size;
/**
* ArrayList基于数组实现
*/
transient Object[] array;
/**
* 指定容量大小的构造函数
*/
public ArrayList(int capacity) {
if (capacity < 0) {
throw new IllegalArgumentException("capacity < 0: " + capacity);
}
array = (capacity == 0 ? EmptyArray.OBJECT : new Object[capacity]);
}
/**
*默认构造函数，空数组
*/
public ArrayList() {
array = EmptyArray.OBJECT;
}
......
}
- 添加方法
add(E object),将元素添加到列表的尾部
@Override
public boolean add(E object) {
//将array赋值给一个局部数组
Object[] a = array;
//将数组元素个数赋值给一个局部变量
int s = size;
//当数组元素个数等于数组长度时需要扩容
//（如果创建ArrayList为无参构造函数（空数组，数组长度为0），
//那么第一次添加时：size（数组元素个数）为0，数组会扩容）
if (s == a.length) {
//新建一个指定容量大小的数组（当前的数组长度如果小于最小容量的一半
//那么新数组长度为旧数组长度加最小长度12，否则新数组长度为旧数组长度的1.5倍）
Object[] newArray = new Object[s +
(s < (MIN_CAPACITY_INCREMENT / 2) ?
MIN_CAPACITY_INCREMENT : s >> 1)];
//将旧数组的数组全部复制到新数组中
System.arraycopy(a, 0, newArray, 0, s);
array = a = newArray; //将新数组复制给旧数组和array
}
a[s] = object; //将元素添加到数组中
size = s + 1; //记录数组长度的变量加1
modCount++; // 数组元素发生变化加1
return true; //添加成功返回true
}
-
add(int index, E object),将元素添加到指定的位置
@Override
public void add(int index, E object) {
Object[] a = array;
int s = size;
if (index > s || index < 0) { //判断角标是否越界
throwIndexOutOfBoundsException(index, s);
}
if (s < a.length) {
//数组不需要扩容，将数据从index起始位置在原数组的
//基础上整体向后复制一份到index+1的起始位置
System.arraycopy(a, index, a, index + 1, s - index);
} else { //数组需要扩容
// assert s == a.length;
Object[] newArray = new Object[newCapacity(s)];//创建一个指定大小的新数组
//ps:源码arraycopy中index为长度，注释的index为角标
System.arraycopy(a, 0, newArray, 0, index);//先将原数组从[0,index)（角标）复制一份到新数组[0,index)（角标）
//ps:源码arraycopy中s - index为长度
System.arraycopy(a, index, newArray, index + 1, s - index);//再将原数组从[index,s-1)（角标）复制一份到新数组[index+1,s-1)（角标）
array = a = newArray;
}
a[index] = object;//新数组中间留有一个index位置给新元素添加进来
size = s + 1;
modCount++;
}
-
remove(int index)删除指定位置的元素
@Override
public E remove(int index) {
Object[] a = array;
int s = size;
if (index >= s) { //判断角标是否越界
throwIndexOutOfBoundsException(index, s);
}
@SuppressWarnings("unchecked") E result = (E) a[index];
//将数组从index+1位置复制到原数组的index位置（整体向前移动一个位置）
System.arraycopy(a, index + 1, a, index, --s - index);
a[s] = null; // 将数组最后的元素置空
size = s;
modCount++;
return result;
}
-
remove(Object object)删除列表中首次出现的指定元素（如果存在）
@Override
public boolean remove(Object object) {
Object[] a = array;
int s = size;
if (object != null) {
for (int i = 0; i < s; i++) {
if (object.equals(a[i])) {//找出元素所在的位置I
//将数组从i+1位置复制到原数组的i位置（整体向前移动一个位置）
System.arraycopy(a, i + 1, a, i, --s - i);
a[s] = null; // Prevent memory leak
size = s;
modCount++;
return true;
}
}
} else {
for (int i = 0; i < s; i++) {
if (a[i] == null) { //移除空元素
System.arraycopy(a, i + 1, a, i, --s - i);
a[s] = null; // Prevent memory leak
size = s;
modCount++;
return true;
}
}
}
return false;
}
- 查询方法
@Override
public boolean contains(Object object) {
Object[] a = array;
int s = size;
if (object != null) {
for (int i = 0; i < s; i++) {
if (object.equals(a[i])) { //从数组起始位置开始遍历整个数组，直到找到元素返回true
return true;
}
}
} else {
for (int i = 0; i < s; i++) {
if (a[i] == null) {
return true;
}
}
}
return false;
}
@Override
public int indexOf(Object object) {
Object[] a = array;
int s = size;
if (object != null) {
for (int i = 0; i < s; i++) {
//从数组起始位置正向遍历整个数组，直到找到元素返回元素角标
if (object.equals(a[i])) {
return i;
}
}
} else {
for (int i = 0; i < s; i++) {
if (a[i] == null) {
return i;
}
}
}
return -1; //如果没有找到对应的元素返回-1。
}
@Override public int lastIndexOf(Object object) {
Object[] a = array;
if (object != null) {
for (int i = size - 1; i >= 0; i--) {
//从数组末尾位置反向遍历整个数组，直到找到元素返回元素角标
if (object.equals(a[i])) {
return i;
}
}
} else {
for (int i = size - 1; i >= 0; i--) {
if (a[i] == null) {
return i;
}
}
}
return -1; //如果没有找到对应的元素返回-1。
}
-
iterator()迭代器
@Override public Iterator<E> iterator() {
return new ArrayListIterator();
}
private class ArrayListIterator implements Iterator<E> {
/** Number of elements remaining in this iteration */
private int remaining = size; //留下来的个数，默认为数组的长度
/** Index of element that remove() would remove, or -1 if no such elt */
private int removalIndex = -1;
/** The expected modCount value */
private int expectedModCount = modCount;
public boolean hasNext() {
return remaining != 0;
}
@SuppressWarnings("unchecked") public E next() {
ArrayList<E> ourList = ArrayList.this;
int rem = remaining;
if (ourList.modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
if (rem == 0) { //没有要遍历的元素还继续遍历就会抛异常
throw new NoSuchElementException();
}
remaining = rem - 1;//遍历一次留下来的个数减1
return (E) ourList.array[removalIndex = ourList.size - rem]; //默认从角标为0开始遍历
}
//迭代删除
public void remove() {
Object[] a = array;
int removalIdx = removalIndex;
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
if (removalIdx < 0) {
throw new IllegalStateException();
}
// 迭代删除时将数组整体向前移动一个位置，将数组末尾元素置空
System.arraycopy(a, removalIdx + 1, a, removalIdx, remaining);
a[--size] = null; // Prevent memory leak
removalIndex = -1;
expectedModCount = ++modCount;
}
}
总结
通过源码分析，可以看出ArrayList是基于数组实现的，而且是一个动态数组，数组的容量能自动增长。
1.可以通过下标索引直接查找到指定位置的元素，因此查找效率高，但每次插入或删除元素，就要大量地移动元素，元素越多，效率越低。
2.在声明数组时尽量指定长度，特别是存放数据较多时，从而减少扩容提高效率。
