LinkedList和ArrayList區(qū)別

　　1. LinkedList

　　2. ArrayList

　　那么這兩者有什么異同呢

　　首先是代碼測(cè)試：

　　import java.util.ArrayList;

　　import java.util.LinkedList;

　　import java.util.List;

　　import bean.Answer;

　　import bean.User;

　　/**

　　* 測(cè)試類

　　*

　　* @author hxz

　　*

　　*/

　　public class MyTestUtil {

　　public static void addTest(List list) {

　　System.out.println(list.getClass().getName() + "開始查詢");

　　long start = System.currentTimeMillis();

　　System.out.println("開始時(shí)間：" + start);

　　list.add("需要查找的數(shù)據(jù)");

　　list.add("eeee");

　　list.add("aaee");

　　list.add("abbb");

　　for (int i = 0; i < 10000000; i++) {

　　for (int j = 0; j < list.size(); j++) {

　　list.get(j).contains("e");

　　System.out.print("");

　　}

　　}

　　long end = System.currentTimeMillis();

　　System.out.println("結(jié)束時(shí)間：" + end);

　　System.out.println("總耗時(shí)：" + (end - start));

　　}

　　public static void main(String[] args) {

　　List a = new ArrayList<>();

　　List b = new LinkedList<>();

　　addTest(a);

　　addTest(b);

　　}

　　}

　　???不是說(shuō)ArrayList查詢快于LinkedList么?

　　然后我們測(cè)試增加

　　???簡(jiǎn)直顛覆我的認(rèn)知!

　　難道我學(xué)的都是錯(cuò)的嗎?

　　事情的真相只有一個(gè)!

　　首先我們需要了解

　　linkedLIst是雙向鏈表結(jié)構(gòu)

　　元素之間的所有關(guān)系是通過(guò)引用關(guān)聯(lián)的,就好比最近特別火的從袖子里撤出棒棒糖來(lái)的情景，想要撤出下一個(gè)就必須撤出上一個(gè)。它在查詢的時(shí)候,只能一個(gè)一個(gè)的遍歷查詢,所以他的查詢效率很低,如果我們想刪除一節(jié)怎么辦呢?就相當(dāng)于自行車的鏈子,有一節(jié)壞了,我們是不是直接把壞的那節(jié)仍掉,然后讓目標(biāo)節(jié)的上一節(jié)指向目標(biāo)節(jié)的下一節(jié),但是

　　ArrayList是數(shù)組結(jié)構(gòu)鄭州好的婦科醫(yī)院 http://www.zzkedayy.com/

　　就是有相同特性的一組數(shù)據(jù)的箱子,比如說(shuō)我有一個(gè)能容下10個(gè)蘋果的箱子,我現(xiàn)在只放了5個(gè)蘋果,那么放第6個(gè)是不是直接放進(jìn)去就行了?呢我要放11個(gè)呢?這個(gè)箱子是不是放不下了?所以我是不是需要換個(gè)大點(diǎn)的箱子?這就是**數(shù)組的擴(kuò)容!**同樣,我們一般放箱子里面的東西是不是按照順序放的?假如說(shuō)是按abcd的順序放的,我突然想添加一個(gè)e,這個(gè)e要放到c的后面,你是不是需要把d先拿出來(lái),再把e放進(jìn)去,再把d放進(jìn)去?假如說(shuō)c后面有10000個(gè)呢?你是不是要把這10000個(gè)都拿出來(lái),把e放進(jìn)去,再放這10000個(gè)?效率是不是很低了?所以,理論上它的增刪比較慢!但是前面也說(shuō)了,我們箱子里面放東西,都是按照順序放的,所以我知道其中一個(gè)"地址",是不是就知道所有元素的地址?所以它的查詢?cè)诶碚撋媳容^快!

　　注意：只是在在list容量較大情況下，ArrayList查詢數(shù)據(jù)要遠(yuǎn)優(yōu)于LinkedList

　　總結(jié)

　　ArrayList和LinkedList在性能上各有優(yōu)缺點(diǎn)，都有各自所適用的地方，總的說(shuō)來(lái)可以描述如下：

　　對(duì)ArrayList而言，主要是在內(nèi)部數(shù)組中增加一項(xiàng)數(shù)據(jù)，指向所添加的元素，偶爾復(fù)雜度為O(n)可能會(huì)導(dǎo)致對(duì)數(shù)組重新進(jìn)行分配;而對(duì)LinkedList而言，這個(gè)開銷是統(tǒng)一的，復(fù)雜度為O(1)，分配一個(gè)內(nèi)部對(duì)象。

　　在ArrayList的中間插入或刪除一個(gè)元素意味著這個(gè)列表中剩余的元素都會(huì)被移動(dòng);而在LinkedList的中間插入或刪除一個(gè)元素的開銷是固定的。

　　LinkedList不支持高效的隨機(jī)元素訪問(wèn)。

　　只是在在list容量較大情況下，ArrayList查詢數(shù)據(jù)要遠(yuǎn)優(yōu)于LinkedList