柚子快報(bào)邀請(qǐng)碼778899分享：【數(shù)據(jù)結(jié)構(gòu)】順序表與鏈表的差異

http://yzkb.51969.com/

順序表和鏈表都是線性表，它們有著相似的部分，但是同時(shí)也有著很大的差異。

?存儲(chǔ)空間上的差異：

對(duì)于插入上的不同點(diǎn)，順序表在空間不夠時(shí)需要擴(kuò)容，而如果在使用realloc函數(shù)去擴(kuò)容，會(huì)有原地?cái)U(kuò)容和異地?cái)U(kuò)容兩種情況，若申請(qǐng)的空間沒(méi)有被使用，則會(huì)用原地?cái)U(kuò)容，消耗不會(huì)大。但是若申請(qǐng)被使用的話，則會(huì)用異地?cái)U(kuò)容，則會(huì)在堆區(qū)上申請(qǐng)一塊空間，并把原來(lái)的數(shù)據(jù)拷貝過(guò)來(lái)，就會(huì)造成消耗會(huì)比較大的問(wèn)題。而帶頭雙向循環(huán)鏈表則不需要考慮到這些問(wèn)題，只需要按需申請(qǐng)釋放就可以了。同時(shí)，順序表的擴(kuò)容還可能存在空間浪費(fèi)的問(wèn)題。

關(guān)于原地?cái)U(kuò)容和異地?cái)U(kuò)容的代碼：

int main()

{

int* p1 = (int*)malloc(8);

printf("%p\n", p1);

int p2 = (int*)realloc(p1, 800);

printf("%p\n", p2);

return 0;

}

原地?cái)U(kuò)容：

異地?cái)U(kuò)容

?

關(guān)于緩存利用率兩種線性表也有很大的不同。

在此之前，我們首先要知道緩存(高速緩沖存儲(chǔ)器)是什么？

在多體并行存儲(chǔ)系統(tǒng)中，由于I/O設(shè)備向主存請(qǐng)求的級(jí)別高于CPU訪存，這就出現(xiàn)了CPU?等待I/0設(shè)備訪存的現(xiàn)象，致使CPU空等一段時(shí)間，甚至可能等待幾個(gè)主存周期，從而降低了CPU的工作效率。為了避免CPU與I/O設(shè)備爭(zhēng)搶訪存，可在CPU與主存之間加一級(jí)緩存(參見(jiàn)圖4.3),這樣，主存可將CPU要取的信息提前送至緩存，一旦主存在與I/O設(shè)備交換時(shí)，CPU?可直接從緩存中讀取所需信息，不必空等而影響效率。?

從另一角度來(lái)看，主存速度的提高始終跟不上CPU的發(fā)展。據(jù)統(tǒng)計(jì)，CPU的速度平均每年改進(jìn)60%,而組成主存的動(dòng)態(tài)RAM速度平均每年只改進(jìn)7%,結(jié)果是CPU和動(dòng)態(tài)RAM之間的速度間隙平均每年增大50%。例如，100MHz的Pentium處理器平均每10ns就執(zhí)行一條指令，而動(dòng)態(tài)RAM的典型訪問(wèn)時(shí)間為60~120ns。這也希望由高速緩存Cache?來(lái)解決主存與CPU速度的不匹配問(wèn)題。

緩存的命中：

在說(shuō)明這兩個(gè)問(wèn)題之前。我們需要要解一個(gè)術(shù)語(yǔ) Cache Line。緩存基本上來(lái)說(shuō)就是把后面的數(shù)據(jù)加載到離自己近的地方，對(duì)于CPU來(lái)說(shuō)，它是不會(huì)一個(gè)字節(jié)一個(gè)字節(jié)的加載的，因?yàn)檫@非常沒(méi)有效率，一般來(lái)說(shuō)都是要一塊一塊的加載的，對(duì)于這樣的一塊一塊的數(shù)據(jù)單位，術(shù)語(yǔ)叫“Cache Line”，

比如：Cache Line是最小單位（64Bytes），所以先把Cache分布多個(gè)Cache Line，比如：L1有32KB，那么，32KB/64B = 512 個(gè) Cache Line。

在計(jì)算機(jī)讀取數(shù)據(jù)的時(shí)候，計(jì)算機(jī)會(huì)根據(jù)地址去訪問(wèn)，如果數(shù)據(jù)在緩存上，則稱(chēng)為命中成功，直接就可以訪問(wèn)數(shù)據(jù)了。如果數(shù)據(jù)在主存上，則稱(chēng)為命中失敗，就需要將主存上的數(shù)據(jù)移到緩存上，這時(shí)就需要使用Cache來(lái)進(jìn)行運(yùn)輸。

我們?cè)倥c線性表聯(lián)系起來(lái)。

順序表的物理結(jié)構(gòu)和邏輯結(jié)構(gòu)的方面上都是連續(xù)的，在數(shù)據(jù)在主存上的情況下，數(shù)據(jù)被移到cache上面。同時(shí)，因?yàn)閷?duì)于CPU來(lái)說(shuō)，它一般來(lái)說(shuō)都是要一塊一塊的加載的，也就代表著加載的時(shí)候會(huì)將順序表連帶著后面的數(shù)據(jù)一并加載到cache上面，也就節(jié)省了時(shí)間，節(jié)約了空間，提高了程序的運(yùn)行效率。

鏈表（雙向帶頭循環(huán)鏈表）的邏輯結(jié)構(gòu)是不連續(xù)的，但是它的物理結(jié)構(gòu)卻是不連續(xù)的。所以，在CPU一塊一塊加載數(shù)據(jù)的時(shí)候，在加載第一個(gè)數(shù)據(jù)的時(shí)候并不會(huì)連帶著后面的數(shù)據(jù)去加載（參考下圖），也就降低了程序運(yùn)行的效率。同時(shí)，因?yàn)橛写罅康臒o(wú)用的數(shù)據(jù)加載到緩存，會(huì)造成數(shù)據(jù)的污染，影響程序的性能。

想對(duì)緩存的命中有更深的了解的話，可以參考陳皓大佬的文章《程序員相關(guān)的CPU緩存知識(shí)?》進(jìn)一步了解。

與程序員相關(guān)的CPU緩存知識(shí) | 酷 殼 - CoolShell

柚子快報(bào)邀請(qǐng)碼778899分享：【數(shù)據(jù)結(jié)構(gòu)】順序表與鏈表的差異

http://yzkb.51969.com/

參考文章