一、鏈表(linkedlist)這一數(shù)據(jù)結構具體有哪些實際應用

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

這說明一個文件的數(shù)據(jù)不一定是連續(xù)存放的，那么操作系統(tǒng)是如何知道把不連續(xù)的數(shù)據(jù)合成一個文件提供給你的呢？其實就是通過訪問一個指向文件數(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結束，但文件系統(tǒng)是以-1結束。所以文件系統(tǒng)通過訪問目錄（頭指針head）、FAT區(qū)（鏈表區(qū)相當去申請到的堆空間）得到一個完整的鏈表1-3-5，再通過計算獲取文件數(shù)據(jù)所在的簇，最后得到數(shù)據(jù)。

由于鏈表屬于環(huán)環(huán)相扣的串行數(shù)據(jù)，任何一環(huán)斷開，這個鏈條就壞了，所以文件系統(tǒng)通常會有一個備份FAT，確保一個損壞可以恢復。

延伸閱讀：

二、鏈表 vs 數(shù)組

內(nèi)存空間存儲結構：

調(diào)整大小

隨機訪問