在java編程過程中,許多人慣使用并常用的的幾個(gè)類型莫過于String安皱,ArrayList以及HashMap了,以至于并沒有關(guān)心過LinkedList及Hashtable等類型及它們的區(qū)別奋刽,致使寫出的程序看似漂亮但是并不高效。
現(xiàn)在我來分享下我了解的ArrayList和LinkedList的區(qū)別。從數(shù)據(jù)結(jié)構(gòu)上看,顧名思義凑懂,ArrayList是實(shí)現(xiàn)了基于動(dòng)態(tài)數(shù)組的結(jié)構(gòu),而LinkedList則是基于實(shí)現(xiàn)鏈表的數(shù)據(jù)結(jié)構(gòu)梧宫。而兩種數(shù)據(jù)結(jié)構(gòu)在程序上體現(xiàn)出來的優(yōu)缺點(diǎn)在于增刪和改查的速率接谨,就此摆碉,我們分別作出說明。
數(shù)據(jù)的更新和查找
ArrayList的所有數(shù)據(jù)是在同一個(gè)地址上,而LinkedList的每個(gè)數(shù)據(jù)都擁有自己的地址.所以在對(duì)數(shù)據(jù)進(jìn)行查找的時(shí)候疤坝,由于LinkedList的每個(gè)數(shù)據(jù)地址不一樣兆解,get數(shù)據(jù)的時(shí)候ArrayList的速度會(huì)優(yōu)于LinkedList,而更新數(shù)據(jù)的時(shí)候跑揉,雖然都是通過循環(huán)循環(huán)到指定節(jié)點(diǎn)修改數(shù)據(jù)锅睛,但LinkedList的查詢速度已經(jīng)是慢的,而且對(duì)于LinkedList而言历谍,更新數(shù)據(jù)時(shí)不像ArrayList只需要找到對(duì)應(yīng)下標(biāo)更新就好现拒,LinkedList需要修改指針,速率不言而喻
數(shù)據(jù)的增加和刪除
對(duì)于數(shù)據(jù)的增加元素望侈,ArrayList是通過移動(dòng)該元素之后的元素位置印蔬,其后元素位置全部+1,所以耗時(shí)較長脱衙,而LinkedList只需要將該元素前的后續(xù)指針指向該元素并將該元素的后續(xù)指針指向之后的元素即可侥猬。與增加相同,刪除元素時(shí)ArrayList需要將被刪除元素之后的元素位置-1捐韩,而LinkedList只需要將之后的元素前置指針指向前一元素退唠,前一元素的指針指向后一元素即可。當(dāng)然荤胁,事實(shí)上瞧预,若是單一元素的增刪,尤其是在List末端增刪一個(gè)元素仅政,二者效率不相上下垢油。
例
下面我們通過程序檢驗(yàn)結(jié)果:
public static final int N = 50000;
static void getTime(List list) {
insertByPosition(list);
readByPosition(list);
updateByPosition(list);
deleteByPosition(list);
}
// 向list的指定位置插入N個(gè)元素,并統(tǒng)計(jì)時(shí)間
private static void insertByPosition(List list) {
long startTime = System.currentTimeMillis();
for (int i = 0; i < N; i++)
list.add(0, i);
long endTime = System.currentTimeMillis();
long interval = endTime - startTime;
System.out.println(getListName(list) + "插入" + N + "條數(shù)據(jù)耗時(shí):" + interval
+ " ms");
}
//從list中讀取元素圆丹,并統(tǒng)計(jì)時(shí)間
private static void readByPosition(List list) {
long startTime = System.currentTimeMillis();
for (int i = 0; i < N; i++){
list.get(i);
}
long endTime = System.currentTimeMillis();
long interval = endTime - startTime;
System.out.println(getListName(list) + "查詢" + N + "條數(shù)據(jù)耗時(shí):" + interval
+ "ms");
}
// 從list的隨機(jī)位置修改元素滩愁,并統(tǒng)計(jì)時(shí)間
private static void updateByPosition(List list) {
long startTime = System.currentTimeMillis();
int M = 40000;
for(int i=0;i<40000;i++){
int j = (int)(1+Math.random()*(40000-1+1));
list.set(j, "list");
}
long endTime = System.currentTimeMillis();
long interval = endTime - startTime;
System.out.println(getListName(list) + "隨機(jī)修改" + M + "條數(shù)據(jù)耗時(shí)" + interval
+ " ms");
}
// 從list的指定位置刪除N個(gè)元素,并統(tǒng)計(jì)時(shí)間
private static void deleteByPosition(List list) {
long startTime = System.currentTimeMillis();
// 刪除list第一個(gè)位置元素
for (int i = 0; i < N; i++)
list.remove(0);
long endTime = System.currentTimeMillis();
long interval = endTime - startTime;
System.out.println(getListName(list) + "刪除" + N + "條數(shù)據(jù)耗時(shí)" + interval
+ " ms");
}
//獲取list類型名稱
private static String getListName(List list) {
if (list instanceof LinkedList) {
return "LinkedList";
} else if (list instanceof ArrayList) {
return "ArrayList";
} else {
return "error";
}
}
public static void main(String[] args) {
getTime(new ArrayList());
getTime(new LinkedList());
}
然后在我本機(jī)的運(yùn)行結(jié)果如下:
由此可見在程序執(zhí)行過程中运褪,對(duì)大量數(shù)據(jù)的增刪改查時(shí)就會(huì)面臨效率問題惊楼,所以對(duì)于ArrayList和LinkedList的選擇,多數(shù)情況下如果查詢操作較多ArrayList的效果更好.如果刪除,插入較多LinkedList的效果較好.當(dāng)然秸讹,具體怎么用還看具體的需求.