鏈表(linked list)這一數據結構具體有哪些實際應用？

12-31

最近在學Java的時候接觸到鏈表，感覺好像沒什麼實際意義啊。。。請問各位鏈表在信息技術領域有什麼實際應用么？

我覺得家裡的承重牆沒實際意義，正忙著拆它呢。有事等我拆完了再說。

拆完了。

鏈表插入刪除效率極高，達到O(1)。對於不需要搜索但變動頻繁且無法預知數量上限的數據，比如內存池、操作系統的進程管理、網路通信協議棧的trunk管理等等等等，缺了它是絕對玩不轉的。

甚至就連很多腳本語言都有內置的鏈表、字典等基礎數據結構支持。哪怕只是稍微像點樣子的小項目，如果缺了鏈表……誰扔的小石子？……啊，缺了鏈表絕對玩不轉。保守估計，缺了鏈表，普通家用PC至少得慢10倍，網路伺服器慢數百到數萬倍都有可……啊，房子要塌!@*@##^#@#$]

最顯著的應用就是文件系統。

你格式化硬碟時會讓你選擇fat32、ntfs格式，其實就是讓你選擇存儲鏈表空間規模及格式。為提高系統效率，你有時需要做文件碎片整理，這說明一個文件的數據不一定是連續存放的，那麼操作系統是如何知道把不連續的數據合成一個文件提供給你的呢？其實就是通過訪問一個指向文件數據區的鏈表得到的。操作系統通常會把一個硬碟的文件區域劃分為3個部分：簇鏈表空間（FAT）/根目錄區（Root）、數據區，而數據區是按指定空間大小分為一簇簇，並編號，假入一個文件數據分布在1/3/5簇，那麼目錄區該文件目錄後面會跟隨一個指針指向1，接著在FAT編號為1的指針指向3,3指向5,5沒有指向，通常鏈表是以NULL結束，但文件系統是以-1結束。所以文件系統通過訪問目錄（頭指針head）、FAT區（鏈表區相當去申請到的堆空間）得到一個完整的鏈表1-3-5，再通過計算獲取文件數據所在的簇，最後得到數據。

由於鏈表屬於環環相扣的串列數據，任何一環斷開，這個鏈條就壞了，所以文件系統通常會有一個備份FAT，確保一個損壞可以恢復。

隨便舉個例子吧，LRU cache的典型實現是用雙向鏈表加上hash table做的。

樓上雖然是開玩笑，但是對待初學者態度還是要好一點嘛。畢竟我也是初學者：）

相對於ArrayList，LinkedList插入是更快的。因為LinkedList不像ArrayList，不需要在數組裝滿的時候要將所有的數據重新裝入一個新的數組，這是ArrayList最壞的一種情況，時間複雜度是O(n)，而LinkedList中插入或刪除的時間複雜度僅為O(1)。ArrayList在插入數據時還需要更新索引（除了插入數組的尾部）。

我覺得在以下場景LinkedList比ArrayList有優勢：

1) 你的應用不會隨機訪問數據。因為如果你需要LinkedList中的第n個元素的時候，你需要從第一個元素順序數到第n個數據，然後讀取數據。

2) 你的應用更多的插入和刪除元素，更少的按索引讀取數據（如果只是遍歷，區別不大）。因為插入和刪除元素不涉及重排數據，所以它要比ArrayList要快。

ps:其實自己點進去看看源碼就知道了。

你問的只是Java里的LinkedList class的話，確實沒什麼卵用。好歹和LinkedList的作者探討過這個問題，對方的意見是「要List用ArrayList, 要Queue用ArrayDeque，反正Java也不會底層到大家天天要用Linked list這個東西，日常用途都包到別的東西里了，我也不知道我當時寫這麼個鬼出來腦子裡進了啥水」

既然題主問的是鏈表的實際應用那就說一下據我所知的一些有用的數據結構中的實際應用，樓上兩位對於對鏈表數據結構的增，查，刪，改的時間複雜度的分析很全面了

上學期剛好學了操作系統的入門課，其中的一個課題就是對於文件系統（file system）的實現，在文件系統中一個比較重要的話題就是對一個文件在硬碟上面的空間分配。

比如你有一個大約512MB的3.5寸軟盤，現在你需要把一個大約佔200MB的文件存儲到這個軟盤上去，但是這個軟盤大概有300MB的空間已經被其他的文件佔用了，而且更糟糕的是，這些大大小小體積各異的文件在軟盤上的分布並不是連續的

紅色表示被佔用空間，綠色表示可用空間：

這個時候，你就需要把你即將寫入磁碟的前100MB 存到第一個綠色方塊裡面，並且在這個文件碎片的末尾寫入第二個綠色方塊的起始地址，這樣當操作系統讀到這個文件碎片的最後一行時，就會跳到第二個綠色方塊的開始並且讀入文件。

註：這只是一個簡單的用鏈表實現的文件模型，在實際實現文件系統與硬碟空間分配的邏輯中，最常用的並不是鏈表結構，據我所知512MB軟盤以及DOS文件系統的空間分配用的是FAT（12，16，32）系統，在硬碟（磁碟）的開頭會有一張FAT表，上面儲存了每一個文件碎片的起始位置。 NTFS系統則採用了B+tree（B++？）樹狀結構來作為磁碟空間分配的邏輯

我之前做的優化搜索演算法就在利用鏈表優化速度（只需要push, back, pop_back, traversal三個操作，長度未知）

別聽那些玩c++的瞎說，你覺得java LinkeList 用處不大是正常的，Java的API把鏈表的精華部分包的一點沒露出來，你根本沒法用。你讓那些說結合hashmap的，拿LinkedList結合結合看看，單個節點都拿不出來，他們寫的出有鬼了，到時候還不是自己實現一個鏈表，和hashmap結合一下。。。

大家保護下新人好嗎？

如果真的指的是鏈表這數據結構，大家當我什麼都沒說，你們說的都對，我路過。路過。。

最後再吐槽一下，我們一直追求的封裝乾淨這事，有時是不是做過了呢，根據我的經驗，很多時候是的。java 8出來的時候發現很多庫函數從原來的private變成public 我覺得也是對封裝操作的反思吧。

不知道知乎的回答和評論區算不算……

你這個問題相當於問魚「水在哪裡」。

讓我舉例子還真是不好舉，隨便一個操作系統、隨便一個有點規模的程序里一般都少不了調用鏈表的代碼。

凡是有線性關係（或者說有全序關係）的數據都會用list的形式保存。如果這個表還需要經常性地插入移除，並且數據量不算很小的情況下，一般都用鏈表表示。

我認為除去效率問題，其實linkedlist最重要的特性是插入刪除的時候迭代器不失效，可以安全的存儲在其他數據結構中。要牢記比起效率，正確性總是第一位的。

所以很多答案提到了內存池，lru等等，其實關鍵問題在於哈希表中存儲了指向鏈表元素的指針。這種程序中一旦分配完句柄，指針就泄露到了容器外部（比如hashmap存儲了pageNode）。如果採用vector那種連續內存空間，一個insert騰挪，指針錯位，程序就錯了。

至於效率問題，LinkedList本身對緩存的友好程度就不如vector。在不要求元素排列順序的情況下，vector可以把元素和rbegin()進行交換再pop_back()，照樣是常數時間，還更緩存友好，大概率比list快。

如果你去看memcache/linux的slab搞法，就會發現它其實介於線性數組和鏈表之間，兼顧了正確性和效率。

哇，C語言用鏈表寫過兩次實踐作業的人，怒答一波。

鏈表可以做很多東西呀，講一個大家都知道的吧，反正大一的我是用鏈表寫了一個簡單的高校信息系統(第二次實踐作業。。

進行學生信息的錄入，從鍵盤從文件讀取，進行學生信息的刪除，添加，按一定的方式排序學生信息，分析學生信息，，寫入信息到文件。。。等一系列用對結點進行的操作。。

記得自己寫了差不多2500行左右，對於一個大一弱菜，感覺還是挺有成就感的。

哈哈哈。。不過，感覺用資料庫應該更好。

反正，還有很多操作，。。

說實話你這問的就讓人很生氣，比如說搞神經生理的說，心理學天天弄的這些玩意有屁用？心理學能把每一種精神現象對應的神經基礎解釋出來嗎？學心理學的大部分都不是專業搞神經的。

就以領接鏈表為例，對於圖G(V, E)，領接鏈表的空間複雜度是O(E)，鄰接矩陣的空間複雜度是O(V*V)，如果要遍歷一張非常巨大的稀疏圖，鄰接矩陣的空間複雜度是無法接受的。

很多解決hash衝突的方式就是鏈表呀，java不知道，我知道的，比如C++里hash map，非關係資料庫redis中的hash也是用鏈表解決衝突的。

操作系統內核里，那就更多了。Linux進程管理，內存管理等等，到處都是鏈表的影子。

還有內存池技術，你看看c中的malloc庫函數的實現源碼就發現，chunk都是通過鏈表管理的，sgi版本的stl源碼中，配接器也自動實現一個內存池，裡面也用到了鏈表。。。

所以，只要你讀源碼，你就會發現 hash、鏈表、紅黑樹真是無處不在。。。所以，好好學習數據結構與演算法吧。。。

樓上有人說了LRU和文件系統，還有一個比較常用的應用是git。

git裡面每次commit都是創建一個node，node包含了刪減後的新文件，然後node指向前一個commit的node。git checkout、delete branch、merge、rebase這些基本上都是以鏈表操作為主。git應該算是對linked list很好的應用。不用linked list應該很難高效地實現git提供的功能。

沒有linkedlist我演算法分析大作業交不上去啊

C語言標準庫中malloc()函數就是基於鏈表，

malloc的工作原理是因為內存塊的分布是離散的，它將各個內存塊以鏈表的形式連接，組成空閑鏈表，在用戶使用malloc函數申請內存時，遍歷鏈表找到一個足夠大的，能夠滿足用戶需求的用戶的大內存快，將它一分為二，其中一個與用戶申請的內存相同，將它的地址返回。

所以頻繁的malloc/free會造成性能的降低

比如……貪吃蛇？

……

修改插入O(1)在一些地方還是用得上的。

鏈表沒意義……你會明白鏈表的用途有多廣泛的……

堆管理就是基於鏈表的

Java 裡面有一個 LinkedList 就是用鏈表做的。

LinkedList 通常在經常需要在 List 中間增刪元素的場景下使用。