一、用鏈表的目的

鏈表主要是便于管理長度或數量不確定的數據，相對于數組，鏈表處理這種數據時比較節省內存。動態語言通常不大需要鏈表，因為動態語言的解釋器幫你管理內存，但當你對空間效率或插入動作的效率有特殊要求時也可在動態語言中使用鏈表。

鏈表常用于在程序中臨時存儲一組不定長的線性數據。

具有這樣的特點的數據可以用鏈表來保存：

1、數據是逐漸增加的

2、數據是不定長的，在存儲名列前茅個數據之前難以確定一個將來一共需要存儲多少數據的上限，或者雖然可以確定上限，但這個上限又比通常大部分情況下數據可能達到的長度要大得多，因而一次性按照上限把空間分配好是不劃算的。而鏈表則可以在每次需要增加新數據時才為之申請內存，不會造成浪費，也不會因一次申請不足而使數據的數量受到限制。

3、不需要按照序號對數據進行隨機訪問。

C++ STL 中提供了list容器，就是鏈表。同時STL還提供了vector容器，也可以用于處理具有上述特點的數據，而且vector還支持隨機訪問（即可以不考慮上述第3點要求）。但vector在增加數據時，如果原先分配的連續內存已經用完則需要重新分配內存并把原有數據復制過去，這時它的插入數據的動作時間復雜度就不是O（1）了（不是常量時間了）。因而，鏈表適于處理的數據除了具有上述特點外，如果還有如下第4點特征，則以鏈表為優異選擇了：

4、希望每次添加數據、刪除數據的動作的時間復雜度都是O（1）的（常量時間）。

延伸閱讀：

二、鏈表與數組的區別

數組：使用一塊連續的內存空間地址去存放數據，例如：

int? a[5]={1,2,3,4,5}。突然我想繼續加兩個數據進去，但是已經定義好的數組不能往后加，只能通過定義新的數組

int b[7]={1,2,3,4,5,6,7}; 這樣就相當不方便比較浪費內存資源,對數據的增刪不好操作。

鏈表：使用多個不連續的內存空間去存儲數據，可以節省內存資源（只有需要存儲數據時，才去劃分新的空間），對數據的增刪比較方便。

上一篇

什么是堆，什么是棧，他們之間有什么區別和聯系?

下一篇

數據結構是什么?