一、用鏈表的目的

鏈表主要是便于管理長度或數(shù)量不確定的數(shù)據(jù)，相對于數(shù)組，鏈表處理這種數(shù)據(jù)時(shí)比較節(jié)省內(nèi)存。動(dòng)態(tài)語言通常不大需要鏈表，因?yàn)閯?dòng)態(tài)語言的解釋器幫你管理內(nèi)存，但當(dāng)你對空間效率或插入動(dòng)作的效率有特殊要求時(shí)也可在動(dòng)態(tài)語言中使用鏈表。

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

具有這樣的特點(diǎn)的數(shù)據(jù)可以用鏈表來保存：

1、數(shù)據(jù)是逐漸增加的

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

3、不需要按照序號對數(shù)據(jù)進(jìn)行隨機(jī)訪問。

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

4、希望每次添加數(shù)據(jù)、刪除數(shù)據(jù)的動(dòng)作的時(shí)間復(fù)雜度都是O（1）的（常量時(shí)間）。

延伸閱讀：

二、鏈表與數(shù)組的區(qū)別

數(shù)組：使用一塊連續(xù)的內(nèi)存空間地址去存放數(shù)據(jù)，例如：

int? a[5]={1,2,3,4,5}。突然我想繼續(xù)加兩個(gè)數(shù)據(jù)進(jìn)去，但是已經(jīng)定義好的數(shù)組不能往后加，只能通過定義新的數(shù)組

int b[7]={1,2,3,4,5,6,7}; 這樣就相當(dāng)不方便比較浪費(fèi)內(nèi)存資源,對數(shù)據(jù)的增刪不好操作。

鏈表：使用多個(gè)不連續(xù)的內(nèi)存空間去存儲數(shù)據(jù)，可以節(jié)省內(nèi)存資源（只有需要存儲數(shù)據(jù)時(shí)，才去劃分新的空間），對數(shù)據(jù)的增刪比較方便。