一、鏈表(linkedlist)這一數(shù)據(jù)結(jié)構(gòu)具體有哪些實(shí)際應(yīng)用
鏈表(linkedlist)這一數(shù)據(jù)結(jié)構(gòu)具體實(shí)際應(yīng)用,最顯著的應(yīng)用就是文件系統(tǒng)。你格式化硬盤時(shí)會(huì)讓你選擇fat32、ntfs格式,其實(shí)就是讓你選擇存儲(chǔ)鏈表空間規(guī)模及格式。為提高系統(tǒng)效率,你時(shí)需要做文件碎片整理。
這說明一個(gè)文件的數(shù)據(jù)不一定是連續(xù)存放的,那么操作系統(tǒng)是如何知道把不連續(xù)的數(shù)據(jù)合成一個(gè)文件提供給你的呢?其實(shí)就是通過訪問一個(gè)指向文件數(shù)據(jù)區(qū)的鏈表得到的。操作系統(tǒng)通常會(huì)把一個(gè)硬盤的文件區(qū)域劃分為3個(gè)部分:簇鏈表空間(FAT)/根目錄區(qū)(Root)、數(shù)據(jù)區(qū),而數(shù)據(jù)區(qū)是按指定空間大小分為一簇簇,并編號(hào),假入一個(gè)文件數(shù)據(jù)分布在1/3/5簇,那么目錄區(qū)該文件目錄后面會(huì)跟隨一個(gè)指針指向1,接著在FAT編號(hào)為1的指針指向3,3指向5,5沒有指向,通常鏈表是以NULL結(jié)束,但文件系統(tǒng)是以-1結(jié)束。所以文件系統(tǒng)通過訪問目錄(頭指針head)、FAT區(qū)(鏈表區(qū)相當(dāng)去申請(qǐng)到的堆空間)得到一個(gè)完整的鏈表1-3-5,再通過計(jì)算獲取文件數(shù)據(jù)所在的簇,最后得到數(shù)據(jù)。
由于鏈表屬于環(huán)環(huán)相扣的串行數(shù)據(jù),任何一環(huán)斷開,這個(gè)鏈條就壞了,所以文件系統(tǒng)通常會(huì)有一個(gè)備份FAT,確保一個(gè)損壞可以恢復(fù)。
延伸閱讀:
二、鏈表 vs 數(shù)組
內(nèi)存空間存儲(chǔ)結(jié)構(gòu):
數(shù)組:存儲(chǔ)在一組連續(xù)的內(nèi)存空間中鏈表:節(jié)點(diǎn)分散在各自不同的內(nèi)存空間中調(diào)整大小
數(shù)組:增加或減少元素個(gè)數(shù),大多需要重新分配一整塊連續(xù)的內(nèi)存空間,然后復(fù)制原有數(shù)據(jù)鏈表:節(jié)點(diǎn)不需要連續(xù)地存儲(chǔ)在一塊地方,增加和刪除節(jié)點(diǎn),非常方便隨機(jī)訪問
數(shù)組:可以通過下標(biāo)地址隨機(jī)訪問數(shù)組鏈表:只能通過一個(gè)節(jié)點(diǎn)一個(gè)節(jié)點(diǎn)輪詢,效率低