ArrayList和LinkedList的區(qū)別

在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é)果如下:

運(yùn)行結(jié)果

由此可見在程序執(zhí)行過程中运褪,對(duì)大量數(shù)據(jù)的增刪改查時(shí)就會(huì)面臨效率問題惊楼,所以對(duì)于ArrayList和LinkedList的選擇,多數(shù)情況下如果查詢操作較多ArrayList的效果更好.如果刪除,插入較多LinkedList的效果較好.當(dāng)然秸讹,具體怎么用還看具體的需求.

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末檀咙,一起剝皮案震驚了整個(gè)濱河市,隨后出現(xiàn)的幾起案子璃诀,更是在濱河造成了極大的恐慌弧可,老刑警劉巖,帶你破解...
    沈念sama閱讀 216,591評(píng)論 6 501
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件劣欢,死亡現(xiàn)場離奇詭異棕诵,居然都是意外死亡裁良,警方通過查閱死者的電腦和手機(jī),發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 92,448評(píng)論 3 392
  • 文/潘曉璐 我一進(jìn)店門校套,熙熙樓的掌柜王于貴愁眉苦臉地迎上來价脾,“玉大人,你說我怎么就攤上這事笛匙∏劝眩” “怎么了?”我有些...
    開封第一講書人閱讀 162,823評(píng)論 0 353
  • 文/不壞的土叔 我叫張陵妹孙,是天一觀的道長秋柄。 經(jīng)常有香客問我,道長蠢正,這世上最難降的妖魔是什么骇笔? 我笑而不...
    開封第一講書人閱讀 58,204評(píng)論 1 292
  • 正文 為了忘掉前任,我火速辦了婚禮嚣崭,結(jié)果婚禮上笨触,老公的妹妹穿的比我還像新娘。我一直安慰自己雹舀,他們只是感情好旭旭,可當(dāng)我...
    茶點(diǎn)故事閱讀 67,228評(píng)論 6 388
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著葱跋,像睡著了一般。 火紅的嫁衣襯著肌膚如雪源梭。 梳的紋絲不亂的頭發(fā)上娱俺,一...
    開封第一講書人閱讀 51,190評(píng)論 1 299
  • 那天,我揣著相機(jī)與錄音废麻,去河邊找鬼荠卷。 笑死,一個(gè)胖子當(dāng)著我的面吹牛烛愧,可吹牛的內(nèi)容都是我干的油宜。 我是一名探鬼主播,決...
    沈念sama閱讀 40,078評(píng)論 3 418
  • 文/蒼蘭香墨 我猛地睜開眼怜姿,長吁一口氣:“原來是場噩夢啊……” “哼慎冤!你這毒婦竟也來了?” 一聲冷哼從身側(cè)響起沧卢,我...
    開封第一講書人閱讀 38,923評(píng)論 0 274
  • 序言:老撾萬榮一對(duì)情侶失蹤蚁堤,失蹤者是張志新(化名)和其女友劉穎,沒想到半個(gè)月后但狭,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體披诗,經(jīng)...
    沈念sama閱讀 45,334評(píng)論 1 310
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡撬即,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 37,550評(píng)論 2 333
  • 正文 我和宋清朗相戀三年,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了呈队。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片剥槐。...
    茶點(diǎn)故事閱讀 39,727評(píng)論 1 348
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡,死狀恐怖宪摧,靈堂內(nèi)的尸體忽然破棺而出粒竖,到底是詐尸還是另有隱情,我是刑警寧澤绍刮,帶...
    沈念sama閱讀 35,428評(píng)論 5 343
  • 正文 年R本政府宣布温圆,位于F島的核電站,受9級(jí)特大地震影響孩革,放射性物質(zhì)發(fā)生泄漏岁歉。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 41,022評(píng)論 3 326
  • 文/蒙蒙 一膝蜈、第九天 我趴在偏房一處隱蔽的房頂上張望锅移。 院中可真熱鬧,春花似錦饱搏、人聲如沸非剃。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,672評(píng)論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽备绽。三九已至,卻和暖如春鬓催,著一層夾襖步出監(jiān)牢的瞬間肺素,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 32,826評(píng)論 1 269
  • 我被黑心中介騙來泰國打工宇驾, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留倍靡,地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 47,734評(píng)論 2 368
  • 正文 我出身青樓课舍,卻偏偏與公主長得像塌西,于是被迫代替她去往敵國和親。 傳聞我的和親對(duì)象是個(gè)殘疾皇子筝尾,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 44,619評(píng)論 2 354

推薦閱讀更多精彩內(nèi)容

  • 一般大家都知道ArrayList和LinkedList的大致區(qū)別:1.ArrayList是實(shí)現(xiàn)了基于動(dòng)態(tài)數(shù)組的數(shù)據(jù)...
    myparamita閱讀 874評(píng)論 0 7
  • 大致的區(qū)別: ArrayList是實(shí)現(xiàn)了基于動(dòng)態(tài)數(shù)組的數(shù)據(jù)結(jié)構(gòu), LinkedList基于鏈表的數(shù)據(jù)結(jié)構(gòu) 對(duì)于隨機(jī)...
    chcvn閱讀 2,480評(píng)論 0 1
  • ArrayList是動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)而LinkedList是鏈表是數(shù)據(jù)結(jié)構(gòu)捡需。ArrayList采用的是數(shù)組形式來保存對(duì)...
    AiSheiShei閱讀 266評(píng)論 0 0
  • 1.ArrayList和LinkedList可想從名字分析,它們一個(gè)是Array(動(dòng)態(tài)數(shù)組)的數(shù)據(jù)結(jié)構(gòu)忿等,一個(gè)是Li...
    戴馬閱讀 902評(píng)論 0 0
  • 1.底層實(shí)現(xiàn)層面: ArrayList底層是由數(shù)組實(shí)現(xiàn)栖忠,是一個(gè)動(dòng)態(tài)數(shù)組,而LinkedList底層是一個(gè)雙向鏈表。...
    是一動(dòng)不動(dòng)的friend閱讀 393評(píng)論 0 1