線性表
線性表：零個(gè)或多個(gè)具有相同類型的數(shù)據(jù)元素的有限序列，數(shù)據(jù)元素的個(gè)數(shù)稱為線性表的長(zhǎng)度歌豺。
線性表的存儲(chǔ)結(jié)構(gòu)：分為順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)兩種
順序存儲(chǔ)結(jié)構(gòu)
用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的各個(gè)數(shù)據(jù)元素
Android中以ArrayList為例脂崔，看看里面是怎么實(shí)現(xiàn)順序存儲(chǔ)的（基于JDK1.7源碼）
- 構(gòu)造方法
public class ArrayList<E> extends AbstractList<E> implements Cloneable, Serializable, RandomAccess {
......
/**
* 最小容量增長(zhǎng)值
*/
private static final int MIN_CAPACITY_INCREMENT = 12;
/**
* 用一個(gè)變量記錄數(shù)組存放元素的個(gè)數(shù)
*/
int size;
/**
* ArrayList基于數(shù)組實(shí)現(xiàn)
*/
transient Object[] array;
/**
* 指定容量大小的構(gòu)造函數(shù)
*/
public ArrayList(int capacity) {
if (capacity < 0) {
throw new IllegalArgumentException("capacity < 0: " + capacity);
}
array = (capacity == 0 ? EmptyArray.OBJECT : new Object[capacity]);
}
/**
*默認(rèn)構(gòu)造函數(shù)国葬，空數(shù)組
*/
public ArrayList() {
array = EmptyArray.OBJECT;
}
......
}
- 添加方法
add(E object),將元素添加到列表的尾部
@Override
public boolean add(E object) {
//將array賦值給一個(gè)局部數(shù)組
Object[] a = array;
//將數(shù)組元素個(gè)數(shù)賦值給一個(gè)局部變量
int s = size;
//當(dāng)數(shù)組元素個(gè)數(shù)等于數(shù)組長(zhǎng)度時(shí)需要擴(kuò)容
//（如果創(chuàng)建ArrayList為無(wú)參構(gòu)造函數(shù)（空數(shù)組安吁，數(shù)組長(zhǎng)度為0），
//那么第一次添加時(shí)：size（數(shù)組元素個(gè)數(shù)）為0睛琳，數(shù)組會(huì)擴(kuò)容）
if (s == a.length) {
//新建一個(gè)指定容量大小的數(shù)組（當(dāng)前的數(shù)組長(zhǎng)度如果小于最小容量的一半
//那么新數(shù)組長(zhǎng)度為舊數(shù)組長(zhǎng)度加最小長(zhǎng)度12盒蟆，否則新數(shù)組長(zhǎng)度為舊數(shù)組長(zhǎng)度的1.5倍）
Object[] newArray = new Object[s +
(s < (MIN_CAPACITY_INCREMENT / 2) ?
MIN_CAPACITY_INCREMENT : s >> 1)];
//將舊數(shù)組的數(shù)組全部復(fù)制到新數(shù)組中
System.arraycopy(a, 0, newArray, 0, s);
array = a = newArray; //將新數(shù)組復(fù)制給舊數(shù)組和array
}
a[s] = object; //將元素添加到數(shù)組中
size = s + 1; //記錄數(shù)組長(zhǎng)度的變量加1
modCount++; // 數(shù)組元素發(fā)生變化加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) { //判斷角標(biāo)是否越界
throwIndexOutOfBoundsException(index, s);
}
if (s < a.length) {
//數(shù)組不需要擴(kuò)容，將數(shù)據(jù)從index起始位置在原數(shù)組的
//基礎(chǔ)上整體向后復(fù)制一份到index+1的起始位置
System.arraycopy(a, index, a, index + 1, s - index);
} else { //數(shù)組需要擴(kuò)容
// assert s == a.length;
Object[] newArray = new Object[newCapacity(s)];//創(chuàng)建一個(gè)指定大小的新數(shù)組
//ps:源碼arraycopy中index為長(zhǎng)度掸掏，注釋的index為角標(biāo)
System.arraycopy(a, 0, newArray, 0, index);//先將原數(shù)組從[0,index)（角標(biāo)）復(fù)制一份到新數(shù)組[0,index)（角標(biāo)）
//ps:源碼arraycopy中s - index為長(zhǎng)度
System.arraycopy(a, index, newArray, index + 1, s - index);//再將原數(shù)組從[index,s-1)（角標(biāo)）復(fù)制一份到新數(shù)組[index+1,s-1)（角標(biāo)）
array = a = newArray;
}
a[index] = object;//新數(shù)組中間留有一個(gè)index位置給新元素添加進(jìn)來(lái)
size = s + 1;
modCount++;
}
-
remove(int index)刪除指定位置的元素
@Override
public E remove(int index) {
Object[] a = array;
int s = size;
if (index >= s) { //判斷角標(biāo)是否越界
throwIndexOutOfBoundsException(index, s);
}
@SuppressWarnings("unchecked") E result = (E) a[index];
//將數(shù)組從index+1位置復(fù)制到原數(shù)組的index位置（整體向前移動(dòng)一個(gè)位置）
System.arraycopy(a, index + 1, a, index, --s - index);
a[s] = null; // 將數(shù)組最后的元素置空
size = s;
modCount++;
return result;
}
-
remove(Object object)刪除列表中首次出現(xiàn)的指定元素（如果存在）
@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
//將數(shù)組從i+1位置復(fù)制到原數(shù)組的i位置（整體向前移動(dòng)一個(gè)位置）
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])) { //從數(shù)組起始位置開始遍歷整個(gè)數(shù)組茁影，直到找到元素返回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++) {
//從數(shù)組起始位置正向遍歷整個(gè)數(shù)組，直到找到元素返回元素角標(biāo)
if (object.equals(a[i])) {
return i;
}
}
} else {
for (int i = 0; i < s; i++) {
if (a[i] == null) {
return i;
}
}
}
return -1; //如果沒有找到對(duì)應(yīng)的元素返回-1丧凤。
}
@Override public int lastIndexOf(Object object) {
Object[] a = array;
if (object != null) {
for (int i = size - 1; i >= 0; i--) {
//從數(shù)組末尾位置反向遍歷整個(gè)數(shù)組，直到找到元素返回元素角標(biāo)
if (object.equals(a[i])) {
return i;
}
}
} else {
for (int i = size - 1; i >= 0; i--) {
if (a[i] == null) {
return i;
}
}
}
return -1; //如果沒有找到對(duì)應(yīng)的元素返回-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; //留下來(lái)的個(gè)數(shù)愿待，默認(rèn)為數(shù)組的長(zhǎng)度
/** 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) { //沒有要遍歷的元素還繼續(xù)遍歷就會(huì)拋異常
throw new NoSuchElementException();
}
remaining = rem - 1;//遍歷一次留下來(lái)的個(gè)數(shù)減1
return (E) ourList.array[removalIndex = ourList.size - rem]; //默認(rèn)從角標(biāo)為0開始遍歷
}
//迭代刪除
public void remove() {
Object[] a = array;
int removalIdx = removalIndex;
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
if (removalIdx < 0) {
throw new IllegalStateException();
}
// 迭代刪除時(shí)將數(shù)組整體向前移動(dòng)一個(gè)位置浩螺，將數(shù)組末尾元素置空
System.arraycopy(a, removalIdx + 1, a, removalIdx, remaining);
a[--size] = null; // Prevent memory leak
removalIndex = -1;
expectedModCount = ++modCount;
}
}
總結(jié)
通過(guò)源碼分析，可以看出ArrayList是基于數(shù)組實(shí)現(xiàn)的仍侥，而且是一個(gè)動(dòng)態(tài)數(shù)組要出，數(shù)組的容量能自動(dòng)增長(zhǎng)。
1.可以通過(guò)下標(biāo)索引直接查找到指定位置的元素农渊，因此查找效率高患蹂，但每次插入或刪除元素，就要大量地移動(dòng)元素砸紊，元素越多传于，效率越低。
2.在聲明數(shù)組時(shí)盡量指定長(zhǎng)度醉顽，特別是存放數(shù)據(jù)較多時(shí)沼溜，從而減少擴(kuò)容提高效率。
