本文轉(zhuǎn)載自微信公眾號(hào)「活在信息時(shí)代」，作者活在信息時(shí)代。轉(zhuǎn)載本文請聯(lián)系活在信息時(shí)代公眾號(hào)。

同為基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)，數(shù)組與鏈表是最為常用的兩個(gè)大類之一。

所謂數(shù)組，就是在內(nèi)存中連續(xù)存儲(chǔ)多個(gè)元素的結(jié)構(gòu)，在內(nèi)存中的分配也是連續(xù)的。數(shù)組中的元素通過數(shù)組下標(biāo)進(jìn)行訪問，數(shù)組下標(biāo)從0開始。

而鏈表是物理存儲(chǔ)單元上非連續(xù)的、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表的指針地址實(shí)現(xiàn)，每個(gè)元素包含兩個(gè)結(jié)點(diǎn)，一個(gè)是存儲(chǔ)元素的數(shù)據(jù)域 (內(nèi)存空間)，另一個(gè)是指向下一個(gè)結(jié)點(diǎn)地址的指針域。

根據(jù)兩者的不同特點(diǎn)，我們可以看到，對于數(shù)組而言，數(shù)據(jù)是可以直接訪問的，也就是說如果我想訪問排序?yàn)?的數(shù)據(jù)，只需要眼看著訪問地址為6的內(nèi)存，就可以得到結(jié)果了。

而如果想訪問鏈表中排序?yàn)?的數(shù)據(jù)，則需要從頭開始，查找到第六個(gè)，才能獲取到結(jié)果。

而插入數(shù)據(jù)的話，在數(shù)組中插入一條數(shù)據(jù)，則需要把插入之后的數(shù)據(jù)全部往后挪一遍。

而對于鏈表來說，插入一條數(shù)據(jù)，只需要將要插入位置的鏈解開，將前一節(jié)的下一個(gè)指針指向插入的節(jié)點(diǎn)，而將新節(jié)點(diǎn)的下一個(gè)指針指向原來的后一節(jié)就行了。非常簡單。

那么，兩者的效率空間會(huì)差多少呢？我們可以寫個(gè)代碼來驗(yàn)證一下。

我們知道，在Java中，ArrayList是基于數(shù)組實(shí)現(xiàn)的List，而LinkedList則是基于鏈表而實(shí)現(xiàn)的。那么，我們就可以寫一段代碼來測試一下他們的效率了。

插入代碼如下：

數(shù)組：

List<Integer> arrayList = new ArrayList<Integer>();
long start = System.currentTimeMillis();
for (int i = 0; i< index; i++) {
arrayList.add(0, i);
}
long end = System.currentTimeMillis();
System.out.println("數(shù)組插入耗時(shí): "+ (end - start));

鏈表：

Long start = System.currentTimeMillis();
List<Integer> linkedList = new LinkedList<Integer>();
for (int i =0; i< index; i ++) {
linkedList.add(0, i);
}
Long end = System.currentTimeMillis();
System.out.println("鏈表插入耗時(shí): "+ (end - start));

查詢代碼如下：

數(shù)組：

List<Integer> arrayList = new ArrayList<Integer>();
for (int i = 0; i< index; i++) {
arrayList.add(i);
}
long start = System.currentTimeMillis();
for (int i : arrayList) {
int j = arrayList.get(i);
}
long end = System.currentTimeMillis();
System.out.println("數(shù)組查詢耗時(shí): "+ (end - start));

鏈表：

List<Integer> linkedList = new LinkedList<Integer>();
for (int i =0; i< index; i ++) {
linkedList.add(i);
}
Long start = System.currentTimeMillis();
for (int i : linkedList) {
linkedList.get(i);
}
Long end = System.currentTimeMillis();
System.out.println("鏈表查詢耗時(shí): "+ (end - start));

在將index設(shè)置為100000的情況下，結(jié)果如下：

可見差距還是很明顯的。