幾個(gè)遺留的問(wèn)題：
- 迭代器沒(méi)加進(jìn)來(lái)，還在研究中
- ArrayList 繼承關(guān)系沒(méi)說(shuō)明脸侥，后期專門寫一篇博客
import java.util.Collection;
/**
* 手寫arrayList,內(nèi)部實(shí)現(xiàn)：數(shù)組
* 操作涯冠，對(duì)每個(gè)節(jié)點(diǎn)的增刪改查
* <p>
* 構(gòu)造方法
*/
public class ArrayList<E> {
/**
* 集合的屬性
* 1.大小
* 2.節(jié)點(diǎn)
* 3.
*/
//大小
// transient關(guān)鍵字解釋：被該關(guān)鍵字修飾的變量只保存在內(nèi)存中昔穴，不會(huì)被寫到磁盤中雪情，影響變量的生命周期
private int size;
//數(shù)組默認(rèn)長(zhǎng)度
private static final int DEFAULT_CAPACITY = 10;
//數(shù)組中的元素
private Object[] array;
//空參構(gòu)造方法
public ArrayList() {
array = new Object[0];
}
//帶參構(gòu)造方法
public ArrayList(int capacity) {
//如果數(shù)組長(zhǎng)度小于0湾盗，拋出異常
if (capacity < 0) {
throw new IllegalArgumentException("list size must be positive ,current size is " + capacity);
}
array = new Object[capacity];
}
//參數(shù)是一個(gè)集合的構(gòu)造方法
public ArrayList(Collection<? extends E>/*E或者E的子類*/ c) {
//先把集合轉(zhuǎn)換成數(shù)組，然后再一個(gè)個(gè)裝到已有的數(shù)組中
Object[] a = c.toArray();
//三種獲取字節(jié)碼文件的方法馅巷，這里出現(xiàn)了兩種
if (a.getClass() != Object[].class) {//由于繼承引起的多態(tài)膛虫，表明o不是E類型的數(shù)組
//如果c不是E類型，而是E的子類钓猬，就不能簡(jiǎn)單的將c賦值給array稍刀，因?yàn)闀?huì)改變array的數(shù)據(jù)類型
Object[] newArray = new Object[a.length];
/**
* 數(shù)組復(fù)制，參數(shù)說(shuō)明
* 參數(shù)1：原數(shù)組
* 參數(shù)2：原數(shù)組起始位置
* 參數(shù)3：目標(biāo)數(shù)組
* 參數(shù)4：目標(biāo)數(shù)組起始位置
* 參數(shù)5：需要復(fù)制的數(shù)組的長(zhǎng)度
*/
System.arraycopy(a, 0, newArray, 0, a.length);
a = newArray;
}
array = a;
size = a.length;
}
/**
* 擴(kuò)容：為什么要擴(kuò)容：arrayList是用數(shù)組實(shí)現(xiàn)的敞曹，數(shù)組是有長(zhǎng)度的账月，當(dāng)數(shù)組的長(zhǎng)度不夠時(shí)，就需要增加數(shù)組的長(zhǎng)度澳迫，即擴(kuò)容
*
* @param currCapacity 當(dāng)前數(shù)組的容量
* @return 擴(kuò)容后的數(shù)組長(zhǎng)度
*/
private static int newCapacity(int currCapacity) {
/**
*需要增加的長(zhǎng)度
* 舉例：如果currCapacity=4局齿，增加的長(zhǎng)度為DEFAULT_CAPACITY即10，
* 如果currCapacity=6橄登，增加的長(zhǎng)度為currCapacity >> 1即5
* 這樣做是為了無(wú)論在哪種情況下抓歼，保證數(shù)組的長(zhǎng)度不會(huì)出現(xiàn)太大的變化
*/
int increment = (currCapacity < DEFAULT_CAPACITY / 2) ? DEFAULT_CAPACITY : currCapacity >> 1;
return currCapacity + increment;
}
/**
* 添加
*
* @param e 要添加的元素
* @return 是否添加成功
*/
public boolean add(E e) {
/**
* 這里將array 賦值給局部變量，然后操作局部變量
* 原因：
* 1.線程安全考慮拢锹，防止兩個(gè)線程同時(shí)操作array出現(xiàn)bug谣妻，賦值給局部變量后，各自操作的是各自的局部變量卒稳，規(guī)避了風(fēng)險(xiǎn)
* 2.數(shù)組是引用數(shù)據(jù)類型蹋半，操作a，就相當(dāng)于操作了array,
* 通過(guò)局部變量就達(dá)到了修改成員變量的值的目的展哭，而且a,s使用完成后就被回收湃窍，不會(huì)占用內(nèi)存
* note：這里就是一個(gè)很重要的思想，先將成員變量賦值給<>局部變量</>匪傍，通過(guò)操作局部變量來(lái)達(dá)到修改成員變量值的目的
*/
Object[] a = array;
int s = size;
if (s == a.length) {
//擴(kuò)容
int newLength = newCapacity(s);
//創(chuàng)建新的數(shù)據(jù)
Object[] newArray = new Object[newLength];
//賦值
System.arraycopy(a, 0, newArray, 0, a.length);
//改變整個(gè)數(shù)組的長(zhǎng)度
array = a = newArray;
}
//將要添加的元素加進(jìn)來(lái)
a[s] = e;
size = s + 1;
return true;
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;//注意size和length的區(qū)別
}
/**
* 根據(jù)元素查找元素對(duì)應(yīng)的下表
* todo 這里有個(gè)疑惑：源碼中的參數(shù)是Object類型您市，但是arrayList是E類型,這里為什么要放object類型,而不是E類型
* 先按照源碼來(lái)寫，有懂的朋友回復(fù)一下
*/
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 {
//數(shù)組里面可以存null役衡，比如二維數(shù)組
for (int i = 0; i < s; i++) {
if (null == a[i]) {
return i;
}
}
}
return -1;
}
/**
* 某元素最后一次出現(xiàn)的角標(biāo)
*
* @return
*/
public int lastIndexOf(Object object) {
Object[] a = array;
int s = size;
if (object != null) {
for (int i = s; i > 0; i--) {
if (object.equals(a[i])) {
return i;
}
}
} else {
for (int i = s; i > 0; i--) {
if (a[i] == null) {
return i;
}
}
}
return -1;
}
/**
* 刪除某個(gè)元素
*
* @return
*/
public E remove(int index) {
Object[] a = array;
int s = size;
//邊界檢測(cè)
if (index < 0) {
throw new IllegalArgumentException();
}
if (index >= s) {//這里加不加“=”都不會(huì)報(bào)錯(cuò)茵休，因?yàn)楫?dāng)index==a.length時(shí)進(jìn)行了擴(kuò)容，存在這個(gè)角標(biāo)，size角標(biāo)的元素實(shí)際上為null榕莺，我自己喜歡加上俐芯，為了統(tǒng)一記憶
throw new ArrayIndexOutOfBoundsException();
}
E e = (E) a[index];
/**
* 為什么是s-1,而不是s
* 舉例：size=5,index=2;
* 此時(shí)需要將index=3和4的元素前移一個(gè)位置，此時(shí)要移動(dòng)的元素的長(zhǎng)度為2=5-1-2,即length=s-1-index;
* 本質(zhì)上是因?yàn)閿?shù)組角標(biāo)是從0開(kāi)始導(dǎo)致的钉鸯。
*/
System.arraycopy(a, index + 1, a, index, s - 1 - index);
a[s] = null;//將最后一個(gè)角標(biāo)的元素置空
s--;
size = s;
return e;
/**
* 上面幾行代碼寫法二：
* System.arraycopy(a, index + 1, a, index, --s - index);
* a[s] = null;//將最后一個(gè)角標(biāo)的元素置空
* size = s;
* return e;
*/
}
public E remove(Object object) {
int index = indexOf(object);
E e = remove(index);
return e;
}
public E set(int index, E e) {
Object[] a = array;
int s = size;
if (index >= s) {
throw new IndexOutOfBoundsException();
}
//源碼中沒(méi)加吧史，自己加的判斷
if (index < 0) {
throw new IllegalArgumentException();
}
E oldE = (E) a[index];
a[index] = e;
return oldE;
}
public void set(E e) {
Object[] a = array;
int s = size;
if (e == null) {
throw new IllegalArgumentException();
}
if (s == a.length) {
//擴(kuò)容
Object[] newArray = new Object[newCapacity(s)];
System.arraycopy(a, 0, newArray, 0, a.length);
newArray[a.length] = e;
array = a = newArray;
size++;
} else {
a[s] = e;
size++;
}
}
public E get(int index) {
Object[] a = array;
int s = size;
if (index >= s) {
throw new IndexOutOfBoundsException();
}
E e = (E) a[index];
return e;
}
}
