建站
咨詢
售后
建站咨詢
新聞中心
本文轉(zhuǎn)載自微信公眾號(hào)「活在信息時(shí)代」，作者活在信息時(shí)代。轉(zhuǎn)載本文請(qǐng)聯(lián)系活在信息時(shí)代公眾號(hào)。
同為基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)，數(shù)組與鏈表是最為常用的兩個(gè)大類(lèi)之一。
所謂數(shù)組，就是在內(nèi)存中連續(xù)存儲(chǔ)多個(gè)元素的結(jié)構(gòu)，在內(nèi)存中的分配也是連續(xù)的。數(shù)組中的元素通過(guò)數(shù)組下標(biāo)進(jìn)行訪問(wèn)，數(shù)組下標(biāo)從0開(kāi)始。
而鏈表是物理存儲(chǔ)單元上非連續(xù)的、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過(guò)鏈表的指針地址實(shí)現(xiàn)，每個(gè)元素包含兩個(gè)結(jié)點(diǎn)，一個(gè)是存儲(chǔ)元素的數(shù)據(jù)域 (內(nèi)存空間)，另一個(gè)是指向下一個(gè)結(jié)點(diǎn)地址的指針域。
根據(jù)兩者的不同特點(diǎn)，我們可以看到，對(duì)于數(shù)組而言，數(shù)據(jù)是可以直接訪問(wèn)的，也就是說(shuō)如果我想訪問(wèn)排序?yàn)?的數(shù)據(jù)，只需要眼看著訪問(wèn)地址為6的內(nèi)存，就可以得到結(jié)果了。
而如果想訪問(wèn)鏈表中排序?yàn)?的數(shù)據(jù)，則需要從頭開(kāi)始，查找到第六個(gè)，才能獲取到結(jié)果。
而插入數(shù)據(jù)的話，在數(shù)組中插入一條數(shù)據(jù)，則需要把插入之后的數(shù)據(jù)全部往后挪一遍。
而對(duì)于鏈表來(lái)說(shuō)，插入一條數(shù)據(jù)，只需要將要插入位置的鏈解開(kāi)，將前一節(jié)的下一個(gè)指針指向插入的節(jié)點(diǎn)，而將新節(jié)點(diǎn)的下一個(gè)指針指向原來(lái)的后一節(jié)就行了。非常簡(jiǎn)單。
那么，兩者的效率空間會(huì)差多少呢？我們可以寫(xiě)個(gè)代碼來(lái)驗(yàn)證一下。
我們知道，在Java中，ArrayList是基于數(shù)組實(shí)現(xiàn)的List，而LinkedList則是基于鏈表而實(shí)現(xiàn)的。那么，我們就可以寫(xiě)一段代碼來(lái)測(cè)試一下他們的效率了。
插入代碼如下：
數(shù)組：
ListarrayList = new ArrayList ();
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();
ListlinkedList = new LinkedList ();
for (int i =0; i< index; i ++) {
linkedList.add(0, i);
}
Long end = System.currentTimeMillis();
System.out.println("鏈表插入耗時(shí): "+ (end - start));
查詢代碼如下：
數(shù)組：
ListarrayList = new ArrayList ();
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));
鏈表：
ListlinkedList = new LinkedList ();
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é)果如下：
可見(jiàn)差距還是很明顯的。
當(dāng)前名稱(chēng)：數(shù)組與鏈表，性能到底差多少？
文章出自：http://fisionsoft.com.cn/article/dpisoch.html
