久re在线,久久夜福利

在上一節(jié)，我們知道了動(dòng)態(tài)數(shù)組實(shí)現(xiàn)的大概原理，不過(guò)，動(dòng)態(tài)數(shù)組卻有一個(gè)明顯的缺點(diǎn)，即可能會(huì)造成內(nèi)存空間的大量浪費(fèi)。因?yàn)楫?dāng)動(dòng)態(tài)數(shù)組空間使用完以后，會(huì)申請(qǐng)一個(gè)更大的空間，用來(lái)保存數(shù)據(jù)，但是更大空間的數(shù)組，卻不一定能全部使用，因此可能造成空間浪費(fèi)。

??能否做到用到多少就申請(qǐng)多少內(nèi)存呢？

有！鏈表就可以做到這一點(diǎn)。

鏈表

鏈表是一種鏈?zhǔn)酱鎯?chǔ)的線性表，所有元素的內(nèi)存地址不一定是連續(xù)的；

例如我們添加一個(gè)元素，會(huì)首先為則個(gè)元素分配存儲(chǔ)空間，并且在鏈表中存儲(chǔ)數(shù)據(jù)，會(huì)首先創(chuàng)建出一個(gè)node節(jié)點(diǎn)對(duì)象，其中內(nèi)部會(huì)有一塊存儲(chǔ)空間，用來(lái)保存要存儲(chǔ)的數(shù)據(jù)，例如下圖是一個(gè)首節(jié)點(diǎn)

1566305122630.png

假設(shè)有兩個(gè)節(jié)點(diǎn)對(duì)象，則如下圖所示進(jìn)行關(guān)聯(lián)

1566305226539.png

以此類推，當(dāng)有多個(gè)節(jié)點(diǎn)時(shí)，會(huì)像下圖一樣相互關(guān)聯(lián)

1566305313016.png

所以，由于每次添加一個(gè)元素，都是新分配的內(nèi)存空間，說(shuō)一每個(gè)節(jié)點(diǎn)之間的內(nèi)存地址并不一定是連續(xù)的。

當(dāng)某個(gè)節(jié)點(diǎn)是尾節(jié)點(diǎn)時(shí)，尾節(jié)點(diǎn)的下一個(gè)Node地址將指向null，用圖形表示如下

1566305570732.png

鏈表的設(shè)計(jì)

鏈表中應(yīng)該包含的元素

size - 保持鏈表的大小
first - 指向鏈表的頭節(jié)點(diǎn)

1566305881624.png

一個(gè)完整的鏈表，用圖形表示如下

1566306009091.png

了解了鏈表的設(shè)計(jì)以后，我們就可以來(lái)了解一下鏈表的接口設(shè)計(jì)了。

鏈表的接口設(shè)計(jì)

小提示：在閱讀該小節(jié)時(shí)，建議結(jié)合demo源碼進(jìn)行同步閱讀效果更佳，demo源碼地址

由于鏈表和動(dòng)態(tài)數(shù)組都是線性表，因此鏈表的大部分接口和動(dòng)態(tài)數(shù)組是一致的，但實(shí)現(xiàn)方式不一樣。因此我們可以將鏈表和動(dòng)態(tài)數(shù)組的接口統(tǒng)一申明到接口文件中，關(guān)系如下

1566310283422.png

由于在動(dòng)態(tài)數(shù)組與鏈表之間，存在一些接口的實(shí)現(xiàn)和一些相同的方法，因此可以抽取一個(gè)抽象類與一個(gè)接口，來(lái)管理接口與方法的實(shí)現(xiàn)，因此有了如下的設(shè)計(jì)

1566310539362.png

至此，鏈表的接口設(shè)計(jì)就完成了，接下來(lái)再來(lái)了解一下接口的實(shí)現(xiàn)

清空鏈表 - clear()

首先，我們假設(shè)現(xiàn)在有一個(gè)結(jié)構(gòu)如下的鏈表對(duì)象

1566310888924.png

我們需要做的事情就是

將size設(shè)置為0
將LinkedList對(duì)象中的first字段設(shè)置為null，當(dāng)我們將first設(shè)置為null時(shí)，相當(dāng)于頭節(jié)點(diǎn)沒(méi)有引用指向它，頭節(jié)點(diǎn)的內(nèi)存就會(huì)被系統(tǒng)回收，然后后節(jié)點(diǎn)依次被系統(tǒng)銷毀

1566311205757.png