一、用鏈表的目的
鏈表主要是便于管理長度或數(shù)量不確定的數(shù)據,相對于數(shù)組,鏈表處理這種數(shù)據時比較節(jié)省內存。動態(tài)語言通常不大需要鏈表,因為動態(tài)語言的解釋器幫你管理內存,但當你對空間效率或插入動作的效率有特殊要求時也可在動態(tài)語言中使用鏈表。
鏈表常用于在程序中臨時存儲一組不定長的線性數(shù)據。
具有這樣的特點的數(shù)據可以用鏈表來保存:
1、數(shù)據是逐漸增加的
2、數(shù)據是不定長的,在存儲名列前茅個數(shù)據之前難以確定一個將來一共需要存儲多少數(shù)據的上限,或者雖然可以確定上限,但這個上限又比通常大部分情況下數(shù)據可能達到的長度要大得多,因而一次性按照上限把空間分配好是不劃算的。而鏈表則可以在每次需要增加新數(shù)據時才為之申請內存,不會造成浪費,也不會因一次申請不足而使數(shù)據的數(shù)量受到限制。
3、不需要按照序號對數(shù)據進行隨機訪問。
C++ STL 中提供了list容器,就是鏈表。同時STL還提供了vector容器,也可以用于處理具有上述特點的數(shù)據,而且vector還支持隨機訪問(即可以不考慮上述第3點要求)。但vector在增加數(shù)據時,如果原先分配的連續(xù)內存已經用完則需要重新分配內存并把原有數(shù)據復制過去,這時它的插入數(shù)據的動作時間復雜度就不是O(1)了(不是常量時間了)。因而,鏈表適于處理的數(shù)據除了具有上述特點外,如果還有如下第4點特征,則以鏈表為優(yōu)異選擇了:
4、希望每次添加數(shù)據、刪除數(shù)據的動作的時間復雜度都是O(1)的(常量時間)。
延伸閱讀:
二、鏈表與數(shù)組的區(qū)別
數(shù)組:使用一塊連續(xù)的內存空間地址去存放數(shù)據,例如:
int? a[5]={1,2,3,4,5}。突然我想繼續(xù)加兩個數(shù)據進去,但是已經定義好的數(shù)組不能往后加,只能通過定義新的數(shù)組
int b[7]={1,2,3,4,5,6,7}; 這樣就相當不方便比較浪費內存資源,對數(shù)據的增刪不好操作。
鏈表:使用多個不連續(xù)的內存空間去存儲數(shù)據,可以節(jié)省內存資源(只有需要存儲數(shù)據時,才去劃分新的空間),對數(shù)據的增刪比較方便。