List ADT有兩種流行的實(shí)現(xiàn)方式，Java中ArrayList類提供了可增長數(shù)組的實(shí)現(xiàn)穆碎，LinkedList提供了雙鏈表實(shí)現(xiàn)。
使用ArrayList的有點(diǎn)在于，對get和set操作花費(fèi)常數(shù)時(shí)間橄仍。其缺點(diǎn)是新元素的插入和元素的刪除付出的代價(jià)非常昂貴，除非變動(dòng)實(shí)在末端進(jìn)行牍戚。
為說明增長數(shù)組實(shí)現(xiàn)的一些思想侮繁，本篇文章將編寫ArrayList的簡單實(shí)現(xiàn)。為避免與類庫中的ArrayList類相混淆如孝，這里將把實(shí)現(xiàn)的類叫做MyArrayList宪哩，即MyArrayList是獨(dú)立的。
MyArrayList的一些細(xì)節(jié)：
- 維護(hù)數(shù)組的元素（elementData）第晰，數(shù)組的容量(elementData.length)锁孟，數(shù)組當(dāng)前的存儲(chǔ)的元素個(gè)數(shù)(size)彬祖。
- 提供一種機(jī)制來動(dòng)態(tài)改變數(shù)組的容量。通過建立新的數(shù)組品抽，將老數(shù)組的元素拷貝到新數(shù)組中储笑，然后允許虛擬機(jī)回收老數(shù)組。
- 提供set和get操作的實(shí)現(xiàn)圆恤。
- 提供基本操作突倍，例如：size()，isEmpty()盆昙，和Clear()羽历。提供remove(...)操作和add(...)操作 。
- MyArrayList實(shí)現(xiàn)Iterable接口淡喜，并提供了一個(gè)實(shí)現(xiàn)Iterator接口的實(shí)現(xiàn)類MyListIterator秕磷，該類實(shí)現(xiàn)了hasNext()，next()和remove()操作拆火。最后通過實(shí)現(xiàn)的iterator放回一個(gè)Iterator實(shí)例跳夭。
代碼####
public class MyArrayList<E> implements Iterable<E> {
private static final int DEFULT_CAPASITY = 10;
private int size; // 維護(hù)數(shù)組當(dāng)前元素的個(gè)數(shù)
private E[] elementData; // 存儲(chǔ)當(dāng)前List的元素
// 構(gòu)造器
public MyArrayList() {
doClear();
}
// 清空List
public void clear() {
doClear();
}
// 清空List操作，設(shè)置size為0们镜，elementData容量為默認(rèn)值10
private void doClear() {
size = 0;
ensureCapacity(DEFULT_CAPASITY);
}
// 獲取size
public int size() {
return size;
}
// 判斷是否為空
public boolean isEmpty() {
return size == 0;
}
// 為了避免浪費(fèi)空間币叹，設(shè)置容量為size
public void trimToSize() {
ensureCapacity(size);
}
// 通過索引獲取元素
public E get(int index) {
CheckRange(index);
return elementData[index];
}
// 修改某個(gè)位子的元素
public E set(int index, E element) {
CheckRange(index);
E old = elementData[index];
elementData[index] = element;
return old;
}
// 保證對List的操作時(shí)有足夠的空間。比如add操作模狭，如果數(shù)組的容量和size相同颈抚，則沒有位子可以添加元素。
// 傳入一個(gè)新的容量minCapacity嚼鹉，表示需要的最小容量贩汉。
// 如果size>=newCapacity，則說明容量足夠锚赤，不作處理匹舞。
// 如果size<newCapacity，則將elementData擴(kuò)容至minCapacity线脚。
@SuppressWarnings("unchecked")
public void ensureCapacity(int minCapacity) {
if (size >= minCapacity) {
return;
}
E[] old = elementData; // 將elementData拷貝到old
elementData = (E[]) new Object[minCapacity]; // 把elementData擴(kuò)容至minCapacity
for (int i = 0; i < size; i++) {
elementData[i] = old[i]; // 還原elementData原來的元素
}
}
// 在List的末尾添加元素赐稽，實(shí)際調(diào)用了add(int index, E element)方法。
public void add(E element) {
add(size, element);
}
// 在某個(gè)位子添加元素浑侥。
public void add(int index, E element) {
CheckRangeForAdd(index); // 數(shù)組越界檢查
// 如果數(shù)組的容量等于size姊舵，即數(shù)組被填滿，則需要擴(kuò)容
if (elementData.length == size) {
ensureCapacity(size + 1); // 擴(kuò)容一個(gè)元素的空間
}
for (int i = size; i > index; i--) {
elementData[i] = elementData[i - 1]; // index及其后面的元素后移
}
elementData[index] = element;
size++;
}
// 刪除某位子的元素
public void remove(int index) {
CheckRange(index); // 數(shù)組越界檢查
for (int i = index; i < size - 1; i++) {
elementData[i] = elementData[i + 1]; // 索引大于index的元素遷移
}
size--;
}
// 越界檢查寓落，智能訪問0~size-1的范圍
private void CheckRange(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
}
// 針對add操作的數(shù)組越界檢查括丁，因?yàn)榭梢栽贚ist末尾添加元素，所以其訪問范圍為0~size
private void CheckRangeForAdd(int index) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException();
}
}
// iterator方法伶选，返回一個(gè)MyIterator實(shí)例
public Iterator<E> iterator() {
return new MyIterator();
}
// MyArrayList的內(nèi)部類史飞，實(shí)現(xiàn)了Iterator接口尖昏，用來實(shí)現(xiàn)遍歷List的操作
private class MyIterator implements Iterator<E> {
// 遍歷數(shù)組，默認(rèn)從0開始
private int currentIndex = 0;
// 如果沒有超過size祸憋，則說明還有下一元素
public boolean hasNext() {
return currentIndex < size;
}
// 每一次調(diào)用都返當(dāng)前元素会宪，比如第一調(diào)用next()返回第一元素，第二次調(diào)用則返回第二個(gè)元素
public E next() {
if (!hasNext()) {
throw new NoSuchElementException();
}
return elementData[currentIndex++];
}
// 刪除當(dāng)前元素蚯窥。實(shí)際上是調(diào)用了MyAarrayList的remove方法掸鹅。
@SuppressWarnings("unused")
public void remove() {
MyArrayList.this.remove(--currentIndex);
}
}
}
測試代碼####
public static void main(String[] args) {
MyArrayList<String> myArrayList = new MyArrayList<String>();
Iterator<String> sIterator = myArrayList.iterator();
// 在末尾添加元素
System.out.println("添加元素：b,c,d");
myArrayList.add("b");
myArrayList.add("c");
myArrayList.add("d");
// 遍歷數(shù)組元素
System.out.print("iterator遍歷List:");
while (sIterator.hasNext()) {
System.out.print(sIterator.next());
}
System.out.println();
// size()
System.out.println();
System.out.println("此時(shí)List中元素的個(gè)數(shù)為：" + myArrayList.size());
System.out.println();
// 在指定位置添加元素，并輸出結(jié)果
System.out.println("在List首部添加元素:a");
myArrayList.add(0, "a");
System.out.print("iterator遍歷List:");
sIterator = myArrayList.iterator();
while (sIterator.hasNext()) {
System.out.print(sIterator.next());
}
System.out.println();
// 刪除指定位子元素(刪除d)
System.out.println();
System.out.println("刪除index為3的元素(d)");
myArrayList.remove(3);
System.out.print("iterator遍歷List:");
sIterator = myArrayList.iterator();
while (sIterator.hasNext()) {
System.out.print(sIterator.next());
}
System.out.println();
System.out.println();
// set()和get()
System.out.println("修改List的第一個(gè)元素為z.");
myArrayList.set(0, "z");
System.out.println("獲取第一個(gè)元素" + myArrayList.get(0));
System.out.println();
// iterator.remove()
System.out.println("測試iterator的remove方法：遍歷List拦赠，每次遍歷刪除當(dāng)前元素");
Iterator<String> rIterator = myArrayList.iterator();
while (rIterator.hasNext()) {
if (rIterator.next() != null) {
rIterator.remove();
}
}
System.out.println("刪除后的List長度為" + myArrayList.size());
}
測試結(jié)果####
測試結(jié)果
本篇只給出了ArrayList的一些基本操作巍沙，如果大家想更深入的了解，可以去查看ArrayList的源碼荷鼠，下面是一篇ArrayList源碼分析很好的文章：
http://blog.csdn.net/jzhf2012/article/details/8540410
大家可以思考兩個(gè)問題：
- 為什么MyArrayList有了remove方法句携，為什么iterator中還要實(shí)現(xiàn)remove方法。
- 為什么MyIterator要作為MyArrayList的內(nèi)部類允乐，還有其他實(shí)現(xiàn)方式嗎矮嫉？
如果有答案，歡迎大家在評論區(qū)討論牍疏。
