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