一、鏈表(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í)需要做文件碎片整理。
這說(shuō)明一個(gè)文件的數(shù)據(jù)不一定是連續(xù)存放的，那么操作系統(tǒng)是如何知道把不連續(xù)的數(shù)據(jù)合成一個(gè)文件提供給你的呢？其實(shí)就是通過(guò)訪問(wèn)一個(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沒(méi)有指向，通常鏈表是以NULL結(jié)束，但文件系統(tǒng)是以-1結(jié)束。所以文件系統(tǒng)通過(guò)訪問(wèn)目錄（頭指針head）、FAT區(qū)（鏈表區(qū)相當(dāng)去申請(qǐng)到的堆空間）得到一個(gè)完整的鏈表1-3-5，再通過(guò)計(jì)算獲取文件數(shù)據(jù)所在的簇，最后得到數(shù)據(jù)。
由于鏈表屬于環(huán)環(huán)相扣的串行數(shù)據(jù)，任何一環(huán)斷開(kāi)，這個(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ī)訪問(wèn)
數(shù)組：可以通過(guò)下標(biāo)地址隨機(jī)訪問(wèn)數(shù)組鏈表：只能通過(guò)一個(gè)節(jié)點(diǎn)一個(gè)節(jié)點(diǎn)輪詢，效率低
京公網(wǎng)安備 11010802030320號(hào)