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