0. 序言
- 數(shù)組是線性表的代表，是很多復(fù)雜數(shù)據(jù)結(jié)構(gòu)的底層實(shí)現(xiàn)；對(duì)數(shù)組的特性認(rèn)識(shí)越深刻浩村，對(duì)學(xué)習(xí)和設(shè)計(jì)復(fù)雜的數(shù)據(jù)結(jié)構(gòu)大有裨益喘漏，總之不要小瞧數(shù)組护蝶。
- 本文為了處理“索引沒(méi)有語(yǔ)意”的情況，即當(dāng)索引沒(méi)有語(yǔ)意的時(shí)候翩迈，如何表示剩余的數(shù)組空間空元素這種情況持灰，以及如何添加元素和如何刪除元素（Java中給出的數(shù)組是沒(méi)有添加元素和刪除元素的功能的，為了處理索引沒(méi)有語(yǔ)意的情況以及更好的理解Java的數(shù)組负饲，我們二次封裝了自己的數(shù)組類堤魁，實(shí)現(xiàn)增刪改查【一些復(fù)雜數(shù)據(jù)結(jié)構(gòu)的背后都有數(shù)組的身影，而且通過(guò)數(shù)組的二次封裝實(shí)現(xiàn)增刪改查】返十，為后面學(xué)習(xí)棧妥泉、隊(duì)列等做準(zhǔn)備）。
- 這里我們實(shí)現(xiàn)一個(gè)動(dòng)態(tài)數(shù)組洞坑，來(lái)實(shí)現(xiàn)增刪改查以及實(shí)現(xiàn)動(dòng)態(tài)擴(kuò)容和縮容涛漂，避免內(nèi)存空間的浪費(fèi)。而這里所說(shuō)的“動(dòng)態(tài)數(shù)組”检诗，當(dāng)你看完這篇文章后，你會(huì)發(fā)現(xiàn)這個(gè)動(dòng)態(tài)數(shù)組的底層其實(shí)是一個(gè)靜態(tài)數(shù)組瓢剿，只不過(guò)是通過(guò)resize來(lái)解決固定容量的問(wèn)題逢慌。
- 如果你覺(jué)得我對(duì)第二段話不是很理解，那么不妨一點(diǎn)點(diǎn)往下看间狂，終有柳暗花明又一村的那一刻攻泼。
1. 數(shù)組基礎(chǔ)
- 本質(zhì)：數(shù)組是典型的線性表，由N個(gè)具有相同類型的數(shù)據(jù)元素組成的有限序列鉴象。
- 特征：元素之間的關(guān)系是一對(duì)一的關(guān)系忙菠，即除了第一個(gè)和最后一個(gè)元素之外，其他元素都是首尾相接的纺弊。
- 類型：數(shù)組是靜態(tài)數(shù)據(jù)結(jié)構(gòu)牛欢，在內(nèi)存中的空間分配是連續(xù)的，用于區(qū)分各個(gè)元素的數(shù)字編號(hào)稱為下標(biāo)或索引淆游。
2. 數(shù)組優(yōu)缺點(diǎn)
- 優(yōu)點(diǎn)：
① 設(shè)計(jì)時(shí)相當(dāng)簡(jiǎn)單傍睹。
② 讀取和修改列表中的任一元素的時(shí)間都是固定的。 - 缺點(diǎn)：
① 刪除和添加數(shù)據(jù)時(shí)需要移動(dòng)大量的數(shù)據(jù)犹菱。
② 在編譯器就要把內(nèi)存分配給相關(guān)變量拾稳，所以在創(chuàng)建初期，必須事先聲明最大可能需要的固定存儲(chǔ)空間腊脱，這就可能造成內(nèi)存的浪費(fèi)访得。
3.數(shù)組代碼展示
- 聲明
int[] arr = new int[10];
int[] scores = new int[]{100,99,98};
- 大小
arr.length
- 遍歷
for (int i = 0; i <arr.length; i++) {
}
for (int score:scores) {
System.out.println(score);
}
- 增加和修改
arr[i] = i;
4. 數(shù)組需注意的地方
- 數(shù)組最大的優(yōu)點(diǎn)：快速查詢
因?yàn)槭庆o態(tài)數(shù)據(jù)結(jié)構(gòu)，在內(nèi)存中是連續(xù)分配的空間陕凹，根據(jù)索引就可以區(qū)分元素所帶來(lái)的好處就是根據(jù)索引就可以快速查詢?cè)亍?/li> - 數(shù)組最好應(yīng)用于“索引有語(yǔ)意"的情況
比如查詢學(xué)生的成績(jī)悍抑，只需要讓學(xué)號(hào)作為索引鳄炉，根據(jù)學(xué)號(hào)來(lái)查成績(jī)。但如果索引沒(méi)有語(yǔ)意的話传趾，就無(wú)法根據(jù)索引快速查詢?cè)亍?/li> - 并非所有有語(yǔ)意的索引都適用于數(shù)組
比如查詢學(xué)生的成績(jī)迎膜，你可以把身份證號(hào)作為索引來(lái)區(qū)分學(xué)生的成績(jī)，這明顯是有語(yǔ)意的浆兰。但如果索引是身份證號(hào)磕仅，在創(chuàng)建數(shù)組的時(shí)候就需要開(kāi)辟超級(jí)大的內(nèi)存空間，顯然這是不合理的簸呈。
5. 動(dòng)態(tài)數(shù)組的設(shè)計(jì)
public class Array {
private int[] data;
private int size;
// 構(gòu)造函數(shù)榕订，傳入數(shù)組的容量capacity構(gòu)造Array
public Array(int capacity) {
data = new int[capacity];
size = 0;
}
// 無(wú)參數(shù)的構(gòu)造函數(shù)，默認(rèn)數(shù)組的容量capacity = 10
public Array() {
this(10);
}
// 獲取數(shù)組中的元素個(gè)數(shù)
public int getSize() {
return size;
}
// 獲取數(shù)組的容量
public int getCapacity() {
return data.length;
}
// 返回?cái)?shù)組是否為空
public boolean isEmpty() {
return size == 0;
}
}
說(shuō)明：
① capacity是創(chuàng)建數(shù)組時(shí)設(shè)置的數(shù)組的最大可容納的元素?cái)?shù)蜕便，即數(shù)組的length劫恒。
② size是當(dāng)前數(shù)組中元素的個(gè)數(shù)，數(shù)組初始化的時(shí)候轿腺，size = 0 两嘴，指向數(shù)組中索引為0的地方。
③ data是我們定義的數(shù)組族壳，如果沒(méi)有給定數(shù)組的大小憔辫，默認(rèn)大小是10.
④ isEmpty是判斷數(shù)組是否為空。
6. 添加元素
當(dāng)添加一個(gè)元素的時(shí)候仿荆，size的個(gè)數(shù)是1贰您，此時(shí)指向索引是1的地方。注意：我們不允許在索引0沒(méi)有元素的情況下拢操，往索引1的位置添加元素锦亦，也就是添加元素的時(shí)候，索引不能大于size令境。
假設(shè)數(shù)組中有4個(gè)元素杠园，當(dāng)往索引1的位置添加元素的時(shí)候，元素99需要首先先往后移動(dòng)1位舔庶，以此類推返劲，元素88再往后移動(dòng)1位，元素77再往后移動(dòng)1位栖茉，這個(gè)時(shí)候索引為1的地方的元素值依然是77篮绿，然后把索引為1的位置的元素77替換為我們想要設(shè)置的元素值即可，當(dāng)然最后需要把size往后移動(dòng)1位吕漂。
// 在第index個(gè)位置插入一個(gè)新元素e
public void add(int index, int e) {
if (size == data.length) // 1
throw new IllegalArgumentException("AddLast failed. Array is full");
if (index < 0 || index > size) { // 2
throw new IllegalArgumentException("Add failed. Require index >=0 and index <= size.");
}
for (int i = size - 1; i >= index; i--) // 3
data[i + 1] = data[i];
data[index] = e; // 4
size++; // 5
}
說(shuō)明：
① 代碼1：當(dāng)數(shù)組中的元素個(gè)數(shù)達(dá)到數(shù)組的最大存儲(chǔ)空間的時(shí)候亲配，不允許添加元素并拋出異常。
② 代碼2：不允許向索引小于0以及索引比size大的地方添加數(shù)據(jù)并拋出異常。
③ 代碼3：size-1位置到等于我們指定的添加元素的索引的位置的元素全部往后挪動(dòng)1位吼虎，即賦值給后1位且從后開(kāi)始執(zhí)行犬钢。
④ 代碼4：把index位置的元素替換為我們想要設(shè)置的元素e。
⑤ 代碼5：size的位置往后移動(dòng)1位思灰。
既然有了添加元素的方法玷犹，那么可以衍生出來(lái)往數(shù)組第一個(gè)位置和最后一個(gè)位置添加元素的方法：
// 向第一個(gè)索引位置添加一個(gè)元素
public void addFirst(int e) {
add(0, e);
}
// 向所有元素后添加一個(gè)新元素
public void addLast(int e) {
add(size, e);
}
7. 查詢和修改元素
- 查詢數(shù)組內(nèi)容
@Override
public String toString() {
StringBuffer res = new StringBuffer();
res.append(String.format("Array: size = %d,capacity = %d\n", size, data.length));
res.append('[');
for (int i = 0; i < size; i++) {
res.append(data[i]);
if (i != size - 1)
res.append(", ");
}
res.append(']');
return res.toString();
}
在這里我們重寫了類的toString方法，用來(lái)打印data數(shù)組中的內(nèi)容洒疚，以便我們進(jìn)行我們的方法測(cè)試歹颓。
- 檢測(cè)
public class TestArray {
public static void main(String[] args){
Array array = new Array(20);
for (int i = 0; i < 10 ; i++) {
array.addLast(i);
}
System.out.println(array);
array.add(1,100);
System.out.println(array);
array.addFirst(-1);
System.out.println(array);
}
}
Array: size = 10,capacity = 20
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Array: size = 11,capacity = 20
[0, 100, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Array: size = 12,capacity = 20
[-1, 0, 100, 1, 2, 3, 4, 5, 6, 7, 8, 9]
通過(guò)以上測(cè)試：添加元素的三個(gè)方法都是正確的。
- 查詢?cè)?/li>
// 獲取index索引位置的元素
int get(int index) {
if (index < 0 || index >= size)
throw new IllegalArgumentException("Get failed. Index is illegal.");
return data[index];
}
// 獲取數(shù)組中最后一個(gè)元素
public E getLast() {
return get(size - 1);
}
// 獲取數(shù)組中第一個(gè)元素
public E getFirst() {
return get(0);
}
- 修改元素
// 修改index索引位置的元素為e
void set(int index, int e) {
if (index < 0 || index >= size)
throw new IllegalArgumentException("Get failed. Index is illegal.");
data[index] = e;
}
8. 包含油湖、搜索和刪除
- 包含和搜索
// 查找數(shù)組中是否有元素e
public boolean contains(int e){
for (int i = 0; i < size ; i++) {
if (data[i] == e)
return true;
}
return false;
}
// 查找數(shù)組中元素e所在的索引巍扛，如果不存在元素e，則返回-1
public int find(int e){
for (int i = 0; i < size ; i++) {
if (data[i] == e)
return i;
}
return -1;
}
當(dāng)包含元素e的時(shí)候返回true乏德，否則返回false撤奸。當(dāng)數(shù)組中含有元素e的時(shí)候，返回e元素所在的索引喊括，否則返回-1胧瓜。
-
刪除指定索引的元素
刪除指定位置的元素
當(dāng)要?jiǎng)h除索引為1的元素的時(shí)候，索引2郑什、3和4位置的元素都會(huì)往前面移動(dòng)1位府喳，所謂移動(dòng)1位指的是索引為2的元素值賦值給索引1的元素，索引為3的元素值賦值給索引2的元素蹦误，索引為4的元素值賦值給索引3的元素。最后別忘記size往前移動(dòng)1位肉津。
刪除指定位置的元素.jpg
可能你會(huì)說(shuō)size一般指向的沒(méi)有元素的索引强胰，這里size指向了100，會(huì)不會(huì)有問(wèn)題呢妹沙？答案是否定的偶洋，因?yàn)槲覀儾僮魉饕系脑氐臅r(shí)候，會(huì)校驗(yàn)索引的合法性距糖。
// 從數(shù)組中刪除index位置的元素玄窝，返回刪除的元素
public int remove(int index) {
if (index < 0 || index >= size)
throw new IllegalArgumentException("Remove failed. Index is illegal.");
int ret = data[index];
for (int i = index + 1; i < size; i++)
data[i - 1] = data[i];
size--;
return ret;
}
有了刪除的方法，可以設(shè)計(jì)刪除數(shù)組中第一個(gè)元素和最后一個(gè)元素的方法：
// 從數(shù)組中刪除第一個(gè)元素悍引，返回刪除的元素
public int removeFirst(){
return remove(0);
}
// 從數(shù)組中刪除最后一個(gè)元素恩脂，返回刪除的元素
public int removeLast(){
return remove(size-1);
}
- 刪除指定的元素
// 從數(shù)組中刪除元素e
public void removeElement(int e){
int index = find(e);
if (index != -1)
remove(index);
}
這里有兩點(diǎn)需要注意：
① 這里的刪除元素的方法，只能刪除一個(gè)元素趣斤，即可能存在相同的兩個(gè)或多個(gè)元素俩块，而這個(gè)方法只會(huì)刪除其中一個(gè)元素。同樣，find方法也存在相同的問(wèn)題玉凯，感興趣的可以對(duì)方法重新設(shè)計(jì)势腮。
② 可能你會(huì)說(shuō)這個(gè)方法沒(méi)有返回成功或者失敗。這個(gè)你也可以自行設(shè)計(jì)漫仆。
而兩項(xiàng)只是設(shè)計(jì)上的問(wèn)題捎拯，方法并沒(méi)有問(wèn)題，暫時(shí)先這樣盲厌，因?yàn)檫@不是重點(diǎn)署照。
- 檢測(cè)
// [-1, 0, 100, 1, 2, 3, 4, 5, 6, 7, 8, 9]
array.remove(2);
System.out.println(array);
array.removeElement(4);
System.out.println(array);
array.removeFirst();
System.out.println(array);
array.removeLast();
System.out.println(array);
int i = array.find(0);
System.out.println(i);
boolean contains = array.contains(0);
System.out.println(contains);
int i1 = array.get(0);
System.out.println(i1);
array.set(0,10);
System.out.println(array);
Array: size = 11,capacity = 20
[-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Array: size = 10,capacity = 20
[-1, 0, 1, 2, 3, 5, 6, 7, 8, 9]
Array: size = 9,capacity = 20
[0, 1, 2, 3, 5, 6, 7, 8, 9]
Array: size = 8,capacity = 20
[0, 1, 2, 3, 5, 6, 7, 8]
0
true
Array: size = 8,capacity = 20
[10, 1, 2, 3, 5, 6, 7, 8]
通過(guò)檢測(cè)，會(huì)發(fā)現(xiàn)以上的方法正確狸眼，讓我們繼續(xù)藤树。
9. 泛型
以上我的數(shù)組類Array，只能放置int數(shù)據(jù)類型的數(shù)據(jù)拓萌，為了讓Array可以放置“任何”數(shù)據(jù)類型岁钓，我們選擇使用泛型，當(dāng)然“任何”二字之所以加引號(hào)微王，是因?yàn)閿?shù)據(jù)類型不可以是基本數(shù)據(jù)類型屡限，只能是類對(duì)象，所以我們定義基本數(shù)據(jù)類型的包裝類即可炕倘，這樣當(dāng)遇到基本數(shù)據(jù)類型的時(shí)候钧大，Java會(huì)自動(dòng)裝箱為對(duì)應(yīng)的包裝類。
public class Array<E> {
private E[] data;
private int size;
// 構(gòu)造函數(shù)罩旋，傳入數(shù)組的容量capacity構(gòu)造Array
public Array(int capacity) {
data = (E[]) new Object[capacity]; // 4
size = 0;
}
// 無(wú)參數(shù)的構(gòu)造函數(shù)啊央，默認(rèn)數(shù)組的容量capacity = 10
public Array() {
this(10);
}
// 獲取數(shù)組中的元素個(gè)數(shù)
public int getSize() {
return size;
}
// 獲取數(shù)組的容量
public int getCapacity() {
return data.length;
}
// 返回?cái)?shù)組是否為空
public boolean isEmpty() {
return size == 0;
}
// 向第一個(gè)索引位置添加一個(gè)元素
public void addFirst(E e) {
add(0, e);
}
// 向所有元素后添加一個(gè)新元素
public void addLast(E e) {
add(size, e);
}
// 在第index個(gè)位置插入一個(gè)新元素e
public void add(int index, E e) {
if (size == data.length)
throw new IllegalArgumentException("AddLast failed. Array is full");
if (index < 0 || index > size) {
throw new IllegalArgumentException("Add failed. Require index >=0 and index <= size.");
}
for (int i = size - 1; i >= index; i--)
data[i + 1] = data[i];
data[index] = e;
size++;
}
// 獲取index索引位置的元素
public E get(int index) {
if (index < 0 || index >= size)
throw new IllegalArgumentException("Get failed. Index is illegal.");
return data[index];
}
// 修改index索引位置的元素為e
public void set(int index, E e) {
if (index < 0 || index >= size)
throw new IllegalArgumentException("Set failed. Index is illegal.");
data[index] = e;
}
// 查找數(shù)組中是否有元素e
public boolean contains(E e) {
for (int i = 0; i < size; i++) {
if (data[i].equals(e)) // 1
return true;
}
return false;
}
// 查找數(shù)組中元素e所在的索引，如果不存在元素e涨醋，則返回-1
public int find(E e) {
for (int i = 0; i < size; i++) {
if (data[i] .equals(e) ) // 2
return i;
}
return -1;
}
// 從數(shù)組中刪除index位置的元素瓜饥，返回刪除的元素
public E remove(int index) {
if (index < 0 || index >= size)
throw new IllegalArgumentException("Remove failed. Index is illegal.");
E ret = data[index];
for (int i = index + 1; i < size; i++)
data[i - 1] = data[i];
size--;
data[size] = null; // 程序優(yōu)化——實(shí)際上是一個(gè)閑散的對(duì)象！=內(nèi)存泄露 // 3
return ret;
}
// 從數(shù)組中刪除第一個(gè)元素浴骂，返回刪除的元素
public E removeFirst() {
return remove(0);
}
// 從數(shù)組中刪除最后一個(gè)元素乓土，返回刪除的元素
public E removeLast() {
return remove(size - 1);
}
// 從數(shù)組中刪除元素e
public void removeElement(E e) {
int index = find(e);
if (index != -1)
remove(index);
}
@Override
public String toString() {
StringBuffer res = new StringBuffer();
res.append(String.format("Array: size = %d,capacity = %d\n", size, data.length));
res.append('[');
for (int i = 0; i < size; i++) {
res.append(data[i]);
if (i != size - 1)
res.append(", ");
}
res.append(']');
return res.toString();
}
}
有兩個(gè)地方需要注意：
① 代碼1和代碼2：類對(duì)象之間的對(duì)比用的是equals而不是“=”
② 代碼3：size此時(shí)指向的是一個(gè)對(duì)象的引用，出于程序優(yōu)化的目的溯警，這里選擇把它置為null趣苏。這個(gè)對(duì)象的引用并非是內(nèi)存泄露，因?yàn)槲覀冊(cè)跀?shù)組后面插入數(shù)據(jù)后梯轻，data[size]所指代的對(duì)象引用就會(huì)發(fā)生變化食磕，之前的對(duì)象的引用就會(huì)引起垃圾回收機(jī)制的注意，根據(jù)垃圾回收機(jī)制會(huì)被回收掉喳挑》椅總之它是一個(gè)閑散的對(duì)象萄金，而非內(nèi)存泄露，處理它是出于程序優(yōu)化的目的媚朦。
③ 代碼4：泛型并不能new出來(lái)氧敢，而是需要new一個(gè)Object對(duì)象，然后強(qiáng)轉(zhuǎn)為泛型對(duì)象询张。
Array<Integer> array = new Array<>(20);
之前我們測(cè)試數(shù)組孙乖，就可以修改為Interger類型即可。
public class Student {
private String name;
private int score;
public Student(String name, int score) {
this.name = name;
this.score = score;
}
@Override
public String toString() {
return String.format("Student(name:%s,score:%d",name,score);
}
public static void main(String[] args){
Array<Student> array = new Array<>();
array.addLast(new Student("小明",99));
array.addLast(new Student("小紅",100));
System.out.println(array);
}
}
Array: size = 2,capacity = 10
[Student(name:小明,score:99, Student(name:小紅,score:100]
證明我們的泛型添加正確份氧，達(dá)到了預(yù)期效果唯袄。
10. 動(dòng)態(tài)數(shù)組
現(xiàn)在我們的數(shù)組Array依然是一個(gè)靜態(tài)數(shù)組，如果開(kāi)的太大可能造成空間的浪費(fèi)蜗帜，如果開(kāi)的太小可能空間不夠恋拷，所以這里我們讓數(shù)組Array容量動(dòng)態(tài)伸縮，即讓Array成為一個(gè)動(dòng)態(tài)數(shù)組厅缺。
原來(lái)的數(shù)組為data蔬顾，數(shù)組中有6個(gè)元素，當(dāng)我們想再添加新的元素的時(shí)候湘捎，由于數(shù)組空間不夠诀豁，所以我們新創(chuàng)建一個(gè)數(shù)組newdata，數(shù)組容量大小是data數(shù)組的2倍窥妇，然后遍歷data數(shù)組中的元素舷胜，賦值到newdata中，然后把data數(shù)組的引入指向newdata數(shù)組活翩，這樣以來(lái)data數(shù)組就擁有了動(dòng)態(tài)擴(kuò)容的技能烹骨。而為什么是之前數(shù)組容量的2倍，而不是10或者1000呢材泄？是因?yàn)檫@里不想引入一個(gè)常數(shù)沮焕，因?yàn)?0可能擴(kuò)容得太小，1000可能擴(kuò)容的太大脸爱，而2倍可以和之前的數(shù)組容量相關(guān)遇汞，它們處在一個(gè)數(shù)量級(jí)上未妹，所以更加合適簿废，而為什么是2倍，而不是1.5倍等等络它，后續(xù)會(huì)詳細(xì)探討這部分內(nèi)容族檬。
// 在第index個(gè)位置插入一個(gè)新元素e
public void add(int index, E e) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("Add failed. Require index >=0 and index <= size.");
}
if (size == data.length)
resize(2 * data.length);
for (int i = size - 1; i >= index; i--)
data[i + 1] = data[i];
data[index] = e;
size++;
}
// 數(shù)組的擴(kuò)容
private void resize(int newCapacity) {
E[] newData = (E[]) new Object[newCapacity];
for (int i = 0; i < size ; i++)
newData[i] = data[i];
data = newData;
}
添加元素，如果發(fā)現(xiàn)size == data.length化戳，那么就執(zhí)行擴(kuò)容函數(shù)resize单料，數(shù)組的擴(kuò)容大小是之前的2倍埋凯，然后把之前的數(shù)組元素賦值給新的數(shù)組，然后讓原來(lái)的數(shù)組引用指向新創(chuàng)建的數(shù)組扫尖，由于newData是局部變量但荤，在函數(shù)執(zhí)行完以后它就失效了典蜕，而data是成員變量，所以data依然有效。
Array<Integer> array = new Array<>();
for (int i = 0; i < 10 ; i++) {
array.addLast(i);
}
System.out.println(array);
array.add(1,100);
System.out.println(array);
array.addFirst(-1);
System.out.println(array);
Array: size = 10,capacity = 10
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Array: size = 11,capacity = 20
[0, 100, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Array: size = 12,capacity = 20
[-1, 0, 100, 1, 2, 3, 4, 5, 6, 7, 8, 9]
從以上示例來(lái)看弱左，數(shù)組Array自動(dòng)擴(kuò)容了纯露，非城分希酷！那擴(kuò)容實(shí)現(xiàn)了铸屉，縮容也很簡(jiǎn)單钉蒲，當(dāng)我們刪除元素，發(fā)現(xiàn)現(xiàn)有的數(shù)組的元素size是容量capacity的一半的時(shí)候彻坛，我們調(diào)用下resize顷啼，讓數(shù)組的容量變?yōu)橹暗?/2：
// 從數(shù)組中刪除index位置的元素，返回刪除的元素
public E remove(int index) {
if (index < 0 || index >= size)
throw new IllegalArgumentException("Remove failed. Index is illegal.");
E ret = data[index];
for (int i = index + 1; i < size; i++)
data[i - 1] = data[i];
size--;
data[size] = null; // 程序優(yōu)化——實(shí)際上是一個(gè)閑散的對(duì)象小压！=內(nèi)存泄露
if (size == data.length / 2)
resize(data.length/2);
return ret;
}
讓我們測(cè)試下：
array.remove(2);
System.out.println(array);
array.removeElement(4);
System.out.println(array);
array.removeFirst();
System.out.println(array);
Array: size = 11,capacity = 20
[-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Array: size = 10,capacity = 10
[-1, 0, 1, 2, 3, 5, 6, 7, 8, 9]
Array: size = 9,capacity = 10
[0, 1, 2, 3, 5, 6, 7, 8, 9]
Array: size = 8,capacity = 10
[0, 1, 2, 3, 5, 6, 7, 8]
當(dāng)數(shù)組的size為11的時(shí)候线梗，數(shù)組的容量并沒(méi)有發(fā)生變化，當(dāng)數(shù)組的size為10的時(shí)候怠益，數(shù)組容量縮小到了10.非骋巧Γ酷！
11. 復(fù)雜度分析
如果對(duì)復(fù)雜度分析不了解蜻牢，請(qǐng)?zhí)D(zhuǎn)閱讀：http://www.reibang.com/p/2d5e5f1bc77e
如果對(duì)平均時(shí)間復(fù)雜度不了解烤咧，請(qǐng)?zhí)D(zhuǎn)閱讀：http://www.reibang.com/p/08d1d509c5db
如果對(duì)均攤時(shí)間復(fù)雜度不了解，請(qǐng)?zhí)D(zhuǎn)閱讀：http://www.reibang.com/p/59f380c6ffcd
- 添加操作
① addLast(e)---O(1)
② addFirst(e)---O(n)
因?yàn)樾枰M(jìn)行數(shù)據(jù)的搬移工作抢呆，所以時(shí)間復(fù)雜度為O(n)
③ add(index,e)---O(n)
④ resize---O(n)
一共是n個(gè)索引煮嫌，索引范圍是0～n-1，索引添加數(shù)據(jù)而造成的搬移數(shù)據(jù)量分別是1+2+3+...+n-1+n抱虐，每個(gè)位置被插入數(shù)據(jù)的概率是1/2,所以平均數(shù)據(jù)搬移量是1/2乘以（1+2+3+...+n-1+n)/n = (n+1)/4個(gè)數(shù)據(jù)昌阿，用大O時(shí)間復(fù)雜度表示法表示平均時(shí)間復(fù)雜度為O(n).
綜上：根據(jù)時(shí)間復(fù)雜度分析之加法法則，添加操作的時(shí)間復(fù)雜度為O(n) - 刪除操作
① removeLast(e)---O(1)
② removeFirst(e)---O(n)
③ remove(index,e)---O(n)(同添加操作分析)
④ resize---O(n)
綜上：根據(jù)時(shí)間復(fù)雜度分析之加法法則恳邀，添加操作的時(shí)間復(fù)雜度為O(n) - 修改操作
set(index,e)---O(1)
數(shù)組支持隨機(jī)訪問(wèn)懦冰，這是數(shù)組最大的優(yōu)勢(shì)。 - 查找操作
① get(index)---O(1)
② contains(e)---O(n)
③ find(e)---O(n)
綜上：
- 增：O(n)
- 刪：O(n)
- 改：已知索引O(1);未知索引O(n)
- 查：已知索引O(1);未知索引O(n)
12.addLast+resize的時(shí)間復(fù)雜度
添加操作的addLast的時(shí)間復(fù)雜度是O(1),resize的時(shí)間復(fù)雜度是O(n),而resize只有滿足條件的時(shí)候才會(huì)觸發(fā)谣沸，所以不能簡(jiǎn)單的說(shuō)addLast+reszie的時(shí)間復(fù)雜度就是O(n),這個(gè)時(shí)候就應(yīng)該用均攤時(shí)間復(fù)雜度分析刷钢，不了解均攤時(shí)間復(fù)雜度分析的，請(qǐng)?zhí)D(zhuǎn)閱讀：http://www.reibang.com/p/59f380c6ffcd
假設(shè)capacity = 8 乳附，并且每次添加操作都使用addLast内地，那9次的addLast操作伴澄，才會(huì)觸發(fā)resize，總共進(jìn)行了17次基本操作阱缓。根據(jù)均攤復(fù)雜度分析非凌，平均每次addLast操作進(jìn)行2次基本操作。即假設(shè)capacity=n荆针，n+1次addLast清焕，觸發(fā)resize，總共進(jìn)行2n+1次操作祭犯，平均每次addLast操作秸妥，進(jìn)行2次基本操作。
綜上：addLast+resize沃粗，根據(jù)均攤時(shí)間復(fù)雜度分析粥惧，得知時(shí)間復(fù)雜度為O(1)。同理最盅，removeLast操作突雪，均攤復(fù)雜度也為O(1)。
13. 復(fù)雜度震蕩
看下我們之間的addLast和removeLast操作涡贱，會(huì)發(fā)現(xiàn)有點(diǎn)問(wèn)題咏删。addLast當(dāng)size == capacity的時(shí)候會(huì)進(jìn)行擴(kuò)容操作，而此時(shí)執(zhí)行removeLast操作问词，由于size =capacity/2會(huì)執(zhí)行縮容的操作督函，循環(huán)往復(fù)的話，就非常不合理激挪，addLast和removeLast都導(dǎo)致了時(shí)間復(fù)雜度為O(n)的操作辰狡，我們稱這種情況為復(fù)雜度震蕩。
解決方案：每次removeLast時(shí)垄分，size = capacity/4的時(shí)候再進(jìn)行縮容操作—稱為L(zhǎng)azy解決方案：
// 從數(shù)組中刪除index位置的元素宛篇，返回刪除的元素
public E remove(int index) {
if (index < 0 || index >= size)
throw new IllegalArgumentException("Remove failed. Index is illegal.");
E ret = data[index];
for (int i = index + 1; i < size; i++)
data[i - 1] = data[i];
size--;
data[size] = null; // 程序優(yōu)化——實(shí)際上是一個(gè)閑散的對(duì)象！=內(nèi)存泄露
if (size == data.length / 4 && data.length/2 !=0) // 1
resize(data.length/2);
return ret;
}
代碼1處薄湿，需要注意data.length/2可能為0叫倍，畢竟數(shù)組容量不能初始化為0，所以這里要注意豺瘤。
14. 后續(xù)
如果大家喜歡這篇文章吆倦，歡迎點(diǎn)贊！
如果想看更多 數(shù)據(jù)結(jié)構(gòu) 方面的文章炉奴，歡迎關(guān)注!
