一、鏈表(linkedlist)這一數(shù)據(jù)結(jié)構(gòu)具體有哪些實(shí)際應(yīng)用

鏈表(linkedlist)這一數(shù)據(jù)結(jié)構(gòu)具體實(shí)際應(yīng)用，最顯著的應(yīng)用就是文件系統(tǒng)。你格式化硬盤(pán)時(shí)會(huì)讓你選擇fat32、ntfs格式，其實(shí)就是讓你選擇存儲(chǔ)鏈表空間規(guī)模及格式。為提高系統(tǒng)效率，你時(shí)需要做文件碎片整理。

這說(shuō)明一個(gè)文件的數(shù)據(jù)不一定是連續(xù)存放的，那么操作系統(tǒng)是如何知道把不連續(xù)的數(shù)據(jù)合成一個(gè)文件提供給你的呢？其實(shí)就是通過(guò)訪(fǎng)問(wèn)一個(gè)指向文件數(shù)據(jù)區(qū)的鏈表得到的。操作系統(tǒng)通常會(huì)把一個(gè)硬盤(pán)的文件區(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ò)訪(fǎng)問(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)：

調(diào)整大小

隨機(jī)訪(fǎng)問(wèn)