數(shù)組是有下標(biāo)索引和data兩部分組成

　　鏈表是有data和指向下一個(gè)數(shù)據(jù)的指針地址兩部分組成

　　綜述：數(shù)組是線性結(jié)構(gòu)，可以直接索引，即要去第i個(gè)元素，a[i]即可。鏈表也是線性結(jié)構(gòu)，要取第i個(gè)元素，只需用指針往后遍歷i次就可。貌似鏈表比數(shù)組還要麻煩些，而且效率低些。

　　想到這些相同處中的一些細(xì)微的不同處，于是他們的真正不同處漸漸顯現(xiàn)了：鏈表的效率為何比數(shù)組低些?先從兩者的初始化開(kāi)始。數(shù)組無(wú)需初始化，因?yàn)閿?shù)組的元素在內(nèi)存的棧區(qū)，系統(tǒng)自動(dòng)申請(qǐng)空間。而鏈表的結(jié)點(diǎn)元素在內(nèi)存的堆區(qū)，每個(gè)元素須手動(dòng)申請(qǐng)空間，如malloc。也就是說(shuō)數(shù)組是靜態(tài)分配內(nèi)存，而鏈表是動(dòng)態(tài)分配內(nèi)存。鏈表如此麻煩為何還要用鏈表呢?數(shù)組不能完全代替鏈表嗎?為何那時(shí)候要用鏈表?因?yàn)楣芾硐到y(tǒng)中的插入，刪除等操作都很靈活，而數(shù)組則大小固定，也無(wú)法靈活高效的插入，刪除。因?yàn)槎巡僮黛`活性更強(qiáng)。數(shù)組每次插入一個(gè)元素就需要移動(dòng)已有元素，而鏈表元素在堆上，無(wú)需這么麻煩。

　　說(shuō)了這么多，數(shù)組和鏈表的區(qū)別整理如下：

　　數(shù)組靜態(tài)分配內(nèi)存，鏈表動(dòng)態(tài)分配內(nèi)存;

　　數(shù)組在內(nèi)存中連續(xù)，鏈表不連續(xù);

　　數(shù)組元素在棧區(qū)，鏈表元素在堆區(qū);

　　數(shù)組利用下標(biāo)定位，時(shí)間復(fù)雜度為O(1)，鏈表定位元素時(shí)間復(fù)雜度O(n);

　　數(shù)組插入或刪除元素的時(shí)間復(fù)雜度O(n)，鏈表的時(shí)間復(fù)雜度O(1)。

　　1.數(shù)組的特點(diǎn)：

　　在內(nèi)存中，數(shù)組是一塊連續(xù)的區(qū)域。 例如看電影來(lái)說(shuō)，幾個(gè)去在電影院看電影必須坐在一起。

　　數(shù)組需要預(yù)留空間，在使用前要先申請(qǐng)占內(nèi)存的大小，可能會(huì)浪費(fèi)內(nèi)存空間。 比如看電影時(shí)，為了保證10個(gè)人能坐在一起，必須提前訂好10個(gè)連續(xù)的位置。這樣的好處就是能保證10個(gè)人可以在一起。但是這樣的缺點(diǎn)是，如果來(lái)的人不夠10個(gè)，那么剩下的位置就浪費(fèi)了。如果臨時(shí)有多來(lái)了個(gè)人，那么10個(gè)就不夠用了，這時(shí)可能需要將第11個(gè)位置上的人挪走，或者是他們11個(gè)人重新去找一個(gè)11連坐的位置，效率都很低。如果沒(méi)有找到符合要求的作為，那么就沒(méi)法坐了。

　　插入數(shù)據(jù)和刪除數(shù)據(jù)效率低，插入數(shù)據(jù)時(shí)，這個(gè)位置后面的數(shù)據(jù)在內(nèi)存中都要向后移。刪除數(shù)據(jù)時(shí)，這個(gè)數(shù)據(jù)后面的數(shù)據(jù)都要往前移動(dòng)。 比如原來(lái)去了5個(gè)人，然后后來(lái)又去了一個(gè)人要坐在第三個(gè)位置上，那么第三個(gè)到第五個(gè)都要往后移動(dòng)一個(gè)位子，將第三個(gè)位置留給新來(lái)的人。 當(dāng)這個(gè)人走了的時(shí)候，因?yàn)樗麄円B在一起的，所以他后面幾個(gè)人要往前移動(dòng)一個(gè)位置，把這個(gè)空位補(bǔ)上。

　　隨機(jī)讀取效率很高。因?yàn)閿?shù)組是連續(xù)的，知道每一個(gè)數(shù)據(jù)的內(nèi)存地址，可以直接找到給地址的數(shù)據(jù)。并且不利于擴(kuò)展，數(shù)組定義的空間不夠時(shí)要重新定義數(shù)組。

　　2 .鏈表的特點(diǎn)

　　在內(nèi)存中可以存在任何地方，不要求連續(xù)。 在電影院幾個(gè)人可以隨便坐。

　　每一個(gè)數(shù)據(jù)都保存了下一個(gè)數(shù)據(jù)的內(nèi)存地址，通過(guò)這個(gè)地址找到下一個(gè)數(shù)據(jù)。 第一個(gè)人知道第二個(gè)人的座位號(hào)，第二個(gè)人知道第三個(gè)人的座位號(hào)……

　　增加數(shù)據(jù)和刪除數(shù)據(jù)很容易。 再來(lái)個(gè)人可以隨便坐，比如來(lái)了個(gè)人要做到第三個(gè)位置，那他只需要把自己的位置告訴第二個(gè)人，然后問(wèn)第二個(gè)人拿到原來(lái)第三個(gè)人的位置就行了。其他人都不用動(dòng)。

　　查找數(shù)據(jù)時(shí)效率低，因?yàn)椴痪哂须S機(jī)訪問(wèn)性，所以訪問(wèn)某個(gè)位置的數(shù)據(jù)都要從第一個(gè)數(shù)據(jù)開(kāi)始訪問(wèn)，然后根據(jù)第一個(gè)數(shù)據(jù)保存的下一個(gè)數(shù)據(jù)的地址找到第二個(gè)數(shù)據(jù)，以此類(lèi)推。 要找到第三個(gè)人，必須從第一個(gè)人開(kāi)始問(wèn)起。

　　不指定大小，擴(kuò)展方便。鏈表大小不用定義，數(shù)據(jù)隨意增刪。

　　3.各自的優(yōu)缺點(diǎn)：

　　(1)數(shù)組的優(yōu)點(diǎn)：

　　隨機(jī)訪問(wèn)性強(qiáng)

　　查詢速度快

　　(2)數(shù)組的缺點(diǎn)：

　　增刪速度慢

　　可能浪費(fèi)內(nèi)存

　　內(nèi)存空間要求高，必須有足夠大的連續(xù)內(nèi)存存儲(chǔ)空間。

　　數(shù)組的大小固定，不能動(dòng)態(tài)擴(kuò)展。

　　(3)鏈表的優(yōu)點(diǎn)

　　插入刪除速度快

　　大小不固定，可以動(dòng)態(tài)擴(kuò)展。

　　內(nèi)存利用率高，不會(huì)浪費(fèi)內(nèi)存

　　(4)鏈表的缺點(diǎn)：

　　不能隨機(jī)查找，必須從第一個(gè)開(kāi)始遍歷，查找效率低

       以上就是動(dòng)力節(jié)點(diǎn)Java培訓(xùn)機(jī)構(gòu)小編介紹的“Java中鏈表和數(shù)組如何學(xué)”的內(nèi)容，希望對(duì)大家有幫助，如有疑問(wèn)，請(qǐng)?jiān)诰€咨詢，有專業(yè)老師隨時(shí)為你服務(wù)。

       Java全套自學(xué)資料

       Java自學(xué)視頻教程（免費(fèi)學(xué)習(xí)）：http://www.dabaquan.cn/video.html

　　Java技術(shù)教程：http://www.dabaquan.cn/tutorial/

       相關(guān)文章

　　零基礎(chǔ)怎么自學(xué)Java，完整版Java學(xué)習(xí)路線圖

　　你還在糾結(jié)學(xué)Java，是自學(xué)還是去培訓(xùn)班嗎

　　一個(gè)標(biāo)準(zhǔn)的Java程序員如何進(jìn)階?

　　Java學(xué)習(xí)路線清單，快速進(jìn)階Java

　　Java編程初學(xué)者要如何進(jìn)階