當(dāng)向ArrayList中添加和刪除元素時(shí)都需要進(jìn)行元素的移動(dòng)峭范，當(dāng)添加和刪除的是動(dòng)態(tài)數(shù)組的頭部元素策幼，需要將數(shù)組中所有元素進(jìn)行移動(dòng)榕茧，其最壞情況的復(fù)雜度為O(n)扛禽。
那么能不能在添加和刪除元素時(shí)不進(jìn)行移動(dòng)或者少移動(dòng)元素呢？
我們可以在動(dòng)態(tài)數(shù)組的基礎(chǔ)上增加一個(gè)int front來記錄一下首元素的位置侈净。
在進(jìn)行添加和刪除尊勿，肯定需要修改front，下面先來看下ArrayList的add和remove方法畜侦。
1运怖、ArrayList的add方法
先來看下之前動(dòng)態(tài)數(shù)組的實(shí)現(xiàn)
public void add(int index, E element) {
checkIndexForAdd(index);
ensureCapacity(size+1);
for (int i = size - 1; i >= index; i--) {
elements[i + 1] = elements[i];
}
elements[index] = element;
size++;
}
可以看到這里是先將元素向后移動(dòng)，然后將數(shù)據(jù)設(shè)置到index的位置夏伊，過程如下
image.png
如果使用了front摇展，在進(jìn)行元素添加時(shí)如何實(shí)現(xiàn)不移動(dòng)元素或者少移動(dòng)元素呢？下面分三種情況進(jìn)行分析：
1.1溺忧、當(dāng)向數(shù)組頭部添加元素
即調(diào)用add(0,element)咏连。
image.png
由圖可知，在調(diào)用add(0,11)時(shí)鲁森，我們可以將元素添加到
index=0的位置祟滴，然后將front減一此時(shí)front變成0。
image.png
如果再次調(diào)用add(0,55)歌溉，那么此時(shí)可以向
index=5的位置添加元素垄懂。
image.png
有上面分析可知骑晶，在每次調(diào)用add(0,element)時(shí)，都會(huì)將元素添加到數(shù)組中角標(biāo)=front-1的位置草慧，即
elements[front-1]=element桶蛔。當(dāng)front-1<0時(shí)，將元素添加到(front-1)+elements.length的位置漫谷。代碼如下：
if (index == 0) {
front = index(-1);
elements[front] = element;
}
// 修正index
private int index(int index) {
index += front;
if (index < 0)
index += elements.length;
else
index = index % elements.length;
return index;
}
1.2仔雷、當(dāng)向數(shù)組末尾添加元素
image.png
此時(shí)size=4，調(diào)用add(size,66)方法舔示，會(huì)向index=5的位置添加元素碟婆，即
elements[front+size]=66。
image.png
此時(shí)size=5惕稻，接著調(diào)用add(size,77)竖共，會(huì)向index=0的位置添加元素，即
elements[(front+size)%elements.length]=77俺祠。代碼如下：
if (index == size) {
elements[index(size)] = element;
}
1.3肘迎、當(dāng)向數(shù)組中其他位置添加元素
- 如果index大于等于size的一半，則將元素向后移動(dòng)锻煌，然后設(shè)置指定位置的元素；如：向index=3,添加元素
image.png - 如果index小于size的一半姻蚓，則將元素向前移動(dòng)宋梧，并將front減一，然后設(shè)置指定位置的元素狰挡；
image.png
具體代碼如下：
if (index >= size >> 1) { // 向后移動(dòng)
for (int i = size - 1; i >= index; i--) {
elements[index(i + 1)] = elements[index(i)];
}
elements[index(index)] = element;
} else { // 向前移動(dòng)
for (int i = 0; i < index; i++) {
elements[index(i-1)] = elements[index(i)];
}
front = index(-1);
elements[index(index)] = element;
}
從上面代碼可知捂龄，在向數(shù)組頭部添加元素其實(shí)也是屬于index<size>>1的情況，只不過不需要移動(dòng)元素加叁；
在向數(shù)組尾部添加元素屬于index>=size>>1的情況倦沧，只不過不需要移動(dòng)元素。
1.4它匕、add方法完整代碼如下
public void add(int index, E element) {
checkIndexForAdd(index);
ensureCapacity(size + 1);
if (index >= size >> 1) { // 向后移動(dòng)
for (int i = size - 1; i >= index; i--) {
elements[index(i + 1)] = elements[index(i)];
}
} else { // 向前移動(dòng)
for (int i = 0; i < index; i++) {
elements[index(i-1)] = elements[index(i)];
}
front = index(-1);
}
elements[index(index)] = element;
size++;
}
// 修正index
private int index(int index) {
index += front;
if (index < 0)
index += elements.length;
else
index = index % elements.length;
return index;
}
2展融、ArrayList的remove方法
2.1、刪除數(shù)組頭部元素
刪除數(shù)組頭部元素很簡(jiǎn)單豫柬，只需要將頭部的數(shù)據(jù)置成null告希，然后將front向后移動(dòng)一位即可。
image.png
代碼如下
if (index == 0) {
elements[front] = null;
front = index(1);
}
2.2烧给、刪除數(shù)組尾部元素
刪除尾部元素和動(dòng)態(tài)數(shù)組完全一樣燕偶，直接將index=size-1位置的元素置成null即可。
代碼如下
if (index == size - 1) {
elements[index(size - 1)] = null;
}
2.3础嫡、刪除其他位置的元素
- 如果index大于等于size的一半指么，則將元素向前移動(dòng)，然后設(shè)置指定位置的元素；如：向index=3,添加元素
image.png - 如果index小于size的一半伯诬，則將元素向后移動(dòng)晚唇，并將front加一；
如刪除index=2的元素
image.png
代碼如下：
if (index >= size >> 1) { // 向前移動(dòng)
for (int i = index; i < size - 1; i++) {
elements[index(i)] = elements[index(i + 1)];
}
elements[index(size - 1)] = null;
} else { // 向后移動(dòng)
for (int i = index; i > 0; i--) {
elements[index(i)] = elements[index(i - 1)];
}
elements[front] = null;
front = index(1);
}
2.4姑廉、remove的完整代碼如下
public E remove(int index) {
checkIndex(index);
E oldE = elements[index(index)];
if (index >= size >> 1) { // 向前移動(dòng)
for (int i = index; i < size - 1; i++) {
elements[index(i)] = elements[index(i + 1)];
}
elements[index(size - 1)] = null;
} else { // 向后移動(dòng)
for (int i = index; i > 0; i--) {
elements[index(i)] = elements[index(i - 1)];
}
elements[front] = null;
front = index(1);
}
size--;
if (size == 0)
front = 0;
trim();
return oldE;
}
3缺亮、總結(jié)
加入front后的動(dòng)態(tài)數(shù)組的增刪改查邏輯其實(shí)也很簡(jiǎn)單，在編寫邏輯時(shí)先認(rèn)為front不存在桥言，然后按照普通動(dòng)態(tài)數(shù)組的邏輯編寫代碼萌踱，最后將牽扯到的index位置的地方，使用我們編寫的矯正index的方法對(duì)index進(jìn)行矯正号阿，獲取其真實(shí)的index即可并鸵。
完整代碼如下：
public class ArrayList2<E> extends AbstractList<E> {
private E[] elements;
private static final int DEFAULT_CAPACTITY = 10;
// 記錄數(shù)組中首元素的位置，默認(rèn)為0
private int front;
public ArrayList2() {
this(DEFAULT_CAPACTITY);
}
public ArrayList2(int capacity) {
if (capacity <= DEFAULT_CAPACTITY)
capacity = DEFAULT_CAPACTITY;
elements = (E[]) new Object[capacity];
}
/**
* 向指定位置添加元素
*
* @param index
* @param element
*/
public void add(int index, E element) {
checkIndexForAdd(index);
ensureCapacity(size + 1);
if (index >= size >> 1) { // 向后移動(dòng)
for (int i = size - 1; i >= index; i--) {
elements[index(i + 1)] = elements[index(i)];
}
} else { // 向前移動(dòng)
for (int i = 0; i < index; i++) {
elements[index(i - 1)] = elements[index(i)];
}
front = index(-1);
}
elements[index(index)] = element;
size++;
}
// 修正index
private int index(int index) {
index += front;
if (index < 0)
index += elements.length;
else
index = index % elements.length;
return index;
}
/**
* 擴(kuò)容
*
* @param capactity
*/
private void ensureCapacity(int capactity) {
if (capactity >= elements.length) {
int newCapacity = capactity + (capactity >> 1);
System.out.println("擴(kuò)容 oldCapactity:" + elements.length + " newCapacity:" + newCapacity);
E[] newElements = (E[]) new Object[newCapacity];
for (int i = 0; i < size; i++) {
newElements[i] = elements[index(i)];
}
elements = newElements;
front = 0;
}
}
/**
* 獲取指定位置的元素
*
* @param index
* @return
*/
public E get(int index) {
checkIndex(index);
return elements[index(index)];
}
/**
* 設(shè)置index位置的元素
*
* @param index
* @param element
*/
@Override
public void set(int index, E element) {
checkIndex(index);
elements[index(index)] = element;
}
/**
* 刪除指定位置的元素
*
* @param index
* @return
*/
public E remove(int index) {
checkIndex(index);
E oldE = elements[index(index)];
if (index >= size >> 1) { // 向前移動(dòng)
for (int i = index; i < size - 1; i++) {
elements[index(i)] = elements[index(i + 1)];
}
elements[index(size - 1)] = null;
} else { // 向后移動(dòng)
for (int i = index; i > 0; i--) {
elements[index(i)] = elements[index(i - 1)];
}
elements[front] = null;
front = index(1);
}
size--;
if (size == 0)
front = 0;
trim();
return oldE;
}
/**
* 縮容：當(dāng)size==capactity/2時(shí)就進(jìn)行縮容,縮小為容量的一半
*/
private void trim() {
int newCapacity = elements.length >> 1;
if (size <= newCapacity && elements.length > DEFAULT_CAPACTITY) {
E[] newElement = (E[]) new Object[newCapacity];
for (int i = 0; i < size; i++) {
newElement[i] = elements[index(i)];
}
System.out.println(elements.length + "縮容為" + newCapacity);
front = 0;
elements = newElement;
}
}
/**
* 刪除元素
*
* @param element
* @return
*/
public E remove(E element) {
return remove(indexOf(element));
}
/**
* 返回指定元素的位置
*
* @param element
* @return 返回-1扔涧，表示未找到元素
*/
public int indexOf(E element) {
for (int i = 0; i < size; i++) {
if (element == null) {
if (elements[index(i)] == null)
return i;
} else {
if (element.equals(elements[index(i)]))
return i;
}
}
return -1;
}
/**
* 清空元素
*/
public void clear() {
for (E e : elements)
e = null;
size = 0;
front = 0;
// 縮容
if (elements != null && elements.length > DEFAULT_CAPACTITY)
elements = (E[]) new Object[DEFAULT_CAPACTITY];
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("size=" + size + " capactity=" + elements.length + " front=" + front + " [");
for (int i = 0; i < elements.length; i++) {
sb.append(elements[i]);
if (i != elements.length - 1)
sb.append(",");
}
sb.append("]");
return sb.toString();
}
}
