所謂數(shù)組，就是在內(nèi)存中連續(xù)存儲多個元素的結構，在內(nèi)存中的分配也是連續(xù)的。數(shù)組中的元素通過數(shù)組下標進行訪問，數(shù)組下標從0開始。
本文轉載自微信公眾號「活在信息時代」，作者活在信息時代。轉載本文請聯(lián)系活在信息時代公眾號。
同為基礎的數(shù)據(jù)結構，數(shù)組與鏈表是最為常用的兩個大類之一。
所謂數(shù)組，就是在內(nèi)存中連續(xù)存儲多個元素的結構，在內(nèi)存中的分配也是連續(xù)的。數(shù)組中的元素通過數(shù)組下標進行訪問，數(shù)組下標從0開始。
而鏈表是物理存儲單元上非連續(xù)的、非順序的存儲結構，數(shù)據(jù)元素的邏輯順序是通過鏈表的指針地址實現(xiàn)，每個元素包含兩個結點，一個是存儲元素的數(shù)據(jù)域 (內(nèi)存空間)，另一個是指向下一個結點地址的指針域。
根據(jù)兩者的不同特點，我們可以看到，對于數(shù)組而言，數(shù)據(jù)是可以直接訪問的，也就是說如果我想訪問排序為6的數(shù)據(jù)，只需要眼看著訪問地址為6的內(nèi)存，就可以得到結果了。
而如果想訪問鏈表中排序為6的數(shù)據(jù)，則需要從頭開始，查找到第六個，才能獲取到結果。
而插入數(shù)據(jù)的話，在數(shù)組中插入一條數(shù)據(jù)，則需要把插入之后的數(shù)據(jù)全部往后挪一遍。
而對于鏈表來說，插入一條數(shù)據(jù)，只需要將要插入位置的鏈解開，將前一節(jié)的下一個指針指向插入的節(jié)點，而將新節(jié)點的下一個指針指向原來的后一節(jié)就行了。非常簡單。
那么，兩者的效率空間會差多少呢？我們可以寫個代碼來驗證一下。
我們知道，在Java中，ArrayList是基于數(shù)組實現(xiàn)的List，而LinkedList則是基于鏈表而實現(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ù)組插入耗時: "+ (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("鏈表插入耗時: "+ (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ù)組查詢耗時: "+ (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("鏈表查詢耗時: "+ (end - start));
在將index設置為100000的情況下，結果如下：
可見差距還是很明顯的。
