想必大多數(shù)人和我一樣，剛開始學數(shù)據(jù)結構中的單鏈表還是蠻吃力的，特別是后面的雙鏈表操作更是如此。還有就是在實踐代碼操作時，你又會感到無從下手，沒有思路。造成這樣的緣由，還是沒有完全把鏈表吃透，今天剛好看書又看到了這里，總結一下，分享給大家，希望對大家有幫助。

一、鏈表引入的緣由：

在一開始，不知大家用了這么久的數(shù)組，你有沒有發(fā)現(xiàn)數(shù)組存在兩個明顯的缺陷？1）一個是數(shù)組中所有元素的類型必須一致；2）第二個是數(shù)組的元素個數(shù)必須事先制定并且一旦指定之后不能更改。于是乎為了解決數(shù)組的缺陷，先輩們發(fā)明的一些特殊方法來解決：a、數(shù)組的第一個缺陷靠結構體去解決。結構體允許其中的元素的類型不相同，因此解決了數(shù)組的第一個缺陷。所以說結構體是因為數(shù)組不能解決某些問題所以才發(fā)明的；b、我們希望數(shù)組的大小能夠實時擴展。譬如我剛開始定了一個元素個數(shù)是10，后來程序運行時覺得不夠因此動態(tài)擴展為20．普通的數(shù)組顯然不行，我們可以對數(shù)組進行封裝以達到這種目的；我們還可以使用一個新的數(shù)據(jù)結構來解決，這個新的數(shù)據(jù)結構就是鏈表（幾乎可以這樣理解：鏈表就是一個元素個數(shù)可以實時變大／變小的數(shù)組）。

二、什么是鏈表？

顧名思義，鏈表就是用鎖鏈連接起來的表。這里的表指的是一個一個的節(jié)點（一個節(jié)點可以比喻成大樓里面的空房子一樣用來存放東西的），節(jié)點中有一些內存可以用來存儲數(shù)據(jù)（所以叫表，表就是數(shù)據(jù)表）；這里的鎖鏈指的是鏈接各個表的方法，C語言中用來連接2個表（其實就是2塊內存）的方法就是指針。它的特點是：它是由若干個節(jié)點組成的（鏈表的各個節(jié)點結構是完全類似的），節(jié)點是由有效數(shù)據(jù)和指針組成的。有效數(shù)據(jù)區(qū)域用來存儲信息完成任務的，指針區(qū)域用于指向鏈表的下一個節(jié)點從而構成鏈表。

三、單鏈表中的一些細節(jié)：

1、單鏈表的構成：

a、鏈表是由節(jié)點組成的，節(jié)點中包含：有效數(shù)據(jù)和指針。

b、定義的struct node只是一個結構體，本身并沒有變量生成，也不占用內存。結構體定義相當于為鏈表節(jié)點定義了一個模板，但是還沒有一個節(jié)點，將來在實際創(chuàng)建鏈表時需要一個節(jié)點時用這個模板來復制一個即可。例如：

1 struct node｛2 int data；／／有效數(shù)據(jù)34struct node ＊pNext；／／指向下一個節(jié)點的指針56 ｝；／／構建一個鏈表的節(jié)點。

2、堆內存的申請和使用：

a、先了解一下什么是堆：堆（heap）是種內存管理方式，它的特點是：就是自由管理（隨時申請，靈活，大小塊隨意）。堆內存是操作系統(tǒng)規(guī)劃給堆管理器（操作系統(tǒng)中的的一段代碼，屬于操作系統(tǒng)的內存管理單元），來管理的，然后向使用者（用戶進程）提供api（malloc和free）來使用堆內存。

b、為什么要使用堆呢？

需要內存容量比較大的時候，需要反復使用及釋放時，需要反復使用及釋放很多數(shù)據(jù)結構（譬如鏈表）的實現(xiàn)都要使用堆內存；它的特點：容量不限（常規(guī)使用的需求容量都能滿足），申請及釋放都需要手工進行，手工進行的含義就是需要程序員寫代碼明確進行申請malloc及釋放free。如果程序員申請內存并使用沒有釋放，這段內存就丟失了（在堆管理器的記錄中，這段內存仍然屬于你這個進程，但是進程自己又以為這段內存已經(jīng)不用了，再用的時候又會申請新的內存塊，這就叫吃內存），稱為內存泄漏。

c、基本概念：

作用域：起作用的區(qū)域，也就是可以工作的范圍。

代碼塊：所謂代碼塊，就是用｛｝括起來的一段代碼。

數(shù)據(jù)段：數(shù)據(jù)段存的是數(shù)，像全局變量就是存在數(shù)據(jù)段的。

代碼段：存的是程序代碼，一般是只讀的。

棧（stack）：先進后出。C語言中局部變量就分配在棧中。

這里隨便也講一下什么是棧：

棧是一種數(shù)據(jù)結構，c語言中使用棧來保存局部變量。棧是被發(fā)明出來管理內存的；它的特點：是先進后出；而先進先出，它是隊列的特點；棧的特點是入口即出口，另外一個口是堵死的。所以先進去的必須后出來隊列的特點是入口和出口都有，必須從入口進去，從出口出來，所以先進去的必須先出來，否則就堵住后面的。在c 語言中的局部變量是用棧來實現(xiàn)的。我們在c中定義一個局部變量時（int a ），編譯器會在棧中分配一段空間（4字節(jié)）給這個局部變量用（分配時棧頂指針會移動給出空間，給局部變量a用的意思就是，將這4字節(jié)的棧內存地址和我們定義的局部變量名a 給關聯(lián)起來），對應棧的操作時入棧。

注意：這里棧指針的移動和內存分配是自動的（棧自己完成，不用我們寫代碼去操作）；然后等我們函數(shù)退出的時候，局部變量要滅亡。對應棧的操作時出棧。出棧時也是棧頂指針移動將棧空間中與a關聯(lián)的那4個字節(jié)空間釋放。這個動作也是自動的，也不用人去寫代碼去控制。棧的優(yōu)點：棧管理內存，好處是方便，分配和最后回收都不用程序員操心，c語言自動完成。分析一個細節(jié)：c語言中，定義局部變量時如果未初始化，則值時隨機的為什么？定義局部變量，其實就是在棧中通過移動棧指針來給程序提供一個內存空間和這個局部變量名綁定，因為這段內存空間在棧上，而棧內存是反復使用的（臟的，上次用完沒有清零的），所以說使用棧來實現(xiàn)的局部變量定義時如果不顯示初始化，值就是臟的。如果你顯示初始化會怎樣？

c語言是通過一個小手段來實現(xiàn)局部變量的初始化的。比如 int a＝10；相當于 int a ；

a＝10；

棧的缺點：首先，棧是有大小的。所以棧內存大小不好設置，如果太小怕溢出，太大跑浪費內存；所以棧的溢出危害很大，一定避免。所以我們在c語言中定義局部變量時不能定義太多或者太大（譬如不能定義局部變量時int a［10000］）

使用遞歸來解決問題時一定要注意遞歸收斂．

d、注意：鏈表的內存要求比較靈活，不能用棧，也不能用data數(shù)據(jù)段。只能用堆內存。

使用堆內存來創(chuàng)建一個鏈表節(jié)點的步驟：1、申請堆內存，大小為一個節(jié)點的大?。z查申請結果是否正確）；2、清理申請到的堆內存；3、把申請到的堆內存當作一個新節(jié)點；4、填充你哦個新節(jié)點的有效數(shù)據(jù)和指針區(qū)域。

實例：

1 ＃include ＜stdio．h＞ 2 ＃include ＜strings．h＞ 3 ＃include ＜stdlib．h＞ 4 int main（void） 5｛ 6 ／／創(chuàng)建一個鏈表節(jié)點 7 struct node ＊p＝（struct node＊）malloc（sizeof（struct node））； 8 if（NULL＝＝p） 9 ｛10 printf（＂malloc error．n＂）；11 ｝12 ／／清理申請到的堆內存13 bzero（p，sizeof（struct node））；14 ／／填充節(jié)點15 p－＞data＝1；16 p－＞pNext ＝NULL；／／將來要指向下一個節(jié)點的首地址；實際操作時將下 一 個節(jié)點malloc返回的指針賦值給這個17｝

四、實例演示：

1、單鏈表的實現(xiàn)：

1 ＃include ＜stdio．h＞ 2 ＃include ＜strings．h＞ 3 ＃include ＜stdlib．h＞ 4 ／／ 構建一個鏈表的節(jié)點 5 struct node 6 ｛ 7 int data； ／／ 有效數(shù)據(jù) 8struct node ＊pNext； ／／ 指向下一個節(jié)點的指針 9 ｝；10 int main（void）11 ｛12／／ 定義頭指針13struct node ＊pHeader ＝ NULL；14／／15／／ 每創(chuàng)建一個新的節(jié)點，把這個新的節(jié)點和它前一個節(jié)點關聯(lián)起來16／／ 創(chuàng)建一個鏈表節(jié)點17struct node ＊p ＝ （struct node ＊）malloc（sizeof（struct node））；18if （NULL ＝＝ p）19｛20 printf（＂malloc error．n＂）；21 return －1；22｝23／／ 清理申請到的堆內存24bzero（p， sizeof（struct node））；25／／ 填充節(jié)點26p－＞data ＝ 1；27p－＞pNext ＝ NULL； ／／ 將來要指向下一個節(jié)點的首地址28 ／／ 實際操作時將下一個節(jié)點malloc返回的指針賦值給這個2930pHeader ＝ p； ／／ 將本節(jié)點和它前面的頭指針關聯(lián)起來 31／／33／／ 每創(chuàng)建一個新的節(jié)點，把這個新的節(jié)點和它前一個節(jié)點關聯(lián)起來34／／ 創(chuàng)建一個鏈表節(jié)點35struct node ＊p1 ＝ （struct node ＊）malloc（sizeof（struct node））；36if （NULL ＝＝ p1）37｛38 printf（＂malloc error．n＂）；39 return －1；40｝41／／ 清理申請到的堆內存42bzero（p1， sizeof（struct node））；43／／ 填充節(jié)點44p1－＞data ＝ 2；45p1－＞pNext ＝ NULL； ／／ 將來要指向下一個節(jié)點的首地址46 ／／ 實際操作時將下一個節(jié)點malloc返回的指針賦值給這個474849p－＞pNext ＝ p1； ／／ 將本節(jié)點和它前面的頭指針關聯(lián)起來 505152／／5354／／5556／／ 每創(chuàng)建一個新的節(jié)點，把這個新的節(jié)點和它前一個節(jié)點關聯(lián)起來5758／／ 創(chuàng)建一個鏈表節(jié)點5960struct node ＊p2 ＝ （struct node ＊）malloc（sizeof（struct node））；61if （NULL ＝＝ p2）62｛63 printf（＂malloc error．n＂）；64 return －1；65｝66／／ 清理申請到的堆內存67bzero（p2， sizeof（struct node））；68／／ 填充節(jié)點69p2－＞data ＝ 3；70p1－＞pNext ＝ p2； ／／ 將來要指向下一個節(jié)點的首地址71 ／／ 實際操作時將下一個節(jié)點malloc返回的指針賦值給這個 72／／73／／ 至此創(chuàng)建了一個有1個頭指針＋3個完整節(jié)點的鏈表。7475／／ 下面是4．9．3節(jié)的代碼76／／ 訪問鏈表中的各個節(jié)點的有效數(shù)據(jù)，這個訪問必須注意不能使用p、p1、p2，而只能77／／ 使用pHeader。7879／／ 訪問鏈表第1個節(jié)點的有效數(shù)據(jù)80printf（＂node1 data： ％d．n＂， pHeader－＞data）； 81printf（＂p－＞data： ％d．n＂， p－＞data）； ／／ pHeader－＞data等同于p－＞data8283／／ 訪問鏈表第2個節(jié)點的有效數(shù)據(jù)84printf（＂node2 data： ％d．n＂， pHeader－＞pNext－＞data）； 85printf（＂p1－＞data： ％d．n＂， p1－＞data）； 86／／ pHeader－＞pNext－＞data等同于p1－＞data8788／／ 訪問鏈表第3個節(jié)點的有效數(shù)據(jù)89printf（＂node3 data： ％d．n＂， pHeader－＞pNext－＞pNext－＞data）； 90printf（＂p2－＞data： ％d．n＂， p2－＞data）； 91／／ pHeader－＞pNext－＞pNext－＞data等同于p2－＞data9293return 0；94｝

編譯結果如下：

1 root＠ubuntu－virtual－machine：／mnt／hgfs／day＃ gcc file2．c2 root＠ubuntu－virtual－machine：／mnt／hgfs／day＃ ．／a．out3 node1 data： 1．4 p－＞data： 1．5 node2 data： 2．6 p1－＞data： 2．7 node3 data： 3．8 p2－＞data： 3．

2、在鏈表末尾添加元素：

思路：由頭指針向后遍歷，直到走到原來的最后一個節(jié)點。原來最后一個節(jié)點里面的pNext是NULL，現(xiàn)在我們只要將它改成new就可以了。添加了之后新節(jié)點就變成了最后一個。代碼實例；

1 ＃include ＜stdio．h＞ 2 ＃include ＜strings．h＞ 3 ＃include ＜stdlib．h＞ 4 ／／ 構建一個鏈表的節(jié)點 5 struct node 6｛ 7int data； ／／ 有效數(shù)據(jù) 8struct node ＊pNext； ／／ 指向下一個節(jié)點的指針 9 ｝；10／／ 作用：創(chuàng)建一個鏈表節(jié)點11／／ 返回值：指針，指針指向我們本函數(shù)新創(chuàng)建的一個節(jié)點的首地址12struct node ＊ create＿node（int data）13｛14struct node ＊p ＝ （struct node ＊）malloc（sizeof（struct node））；15if （NULL ＝＝ p）16｛17 printf（＂malloc error．n＂）；18 return NULL；19｝20／／ 清理申請到的堆內存21bzero（p， sizeof（struct node））；22／／ 填充節(jié)點23p－＞data ＝ data；24p－＞pNext ＝ NULL； 25return p；26 ｝27 void insert＿tail（struct node ＊pH， struct node ＊new）28 ｛29／／ 分兩步來完成插入30／／ 第一步，先找到鏈表中最后一個節(jié)點31struct node ＊p ＝ pH；32while （NULL ?。?p－＞pNext）33｛34 p ＝ p－＞pNext； 35／／ 往后走一個節(jié)點36｝37／／ 第二步，將新節(jié)點插入到最后一個節(jié)點尾部38p－＞pNext ＝ new；39 ｝40 int main（void）41 ｛42／／ 定義頭指針43／／struct node ＊pHeader ＝ NULL； 44／／ 這樣直接insert＿tail會段錯誤。45struct node ＊pHeader ＝ create＿node（1）；46insert＿tail（pHeader， create＿node（2））；47insert＿tail（pHeader， create＿node（3））；48insert＿tail（pHeader， create＿node（4））；49 ／＊50pHeader ＝ create＿node（1）；51 ／／ 將本節(jié)點和它前面的頭指針關聯(lián)起來 52pHeader－＞pNext ＝ create＿node（432）； 53／／ 將本節(jié)點和它前面的頭指針關聯(lián)起來 5455pHeader－＞pNext－＞pNext ＝ create＿node（123）； 56／／ 將來要指向下一個節(jié)點的首地址5758／／ 至此創(chuàng)建了一個有1個頭指針＋3個完整節(jié)點的鏈表。59 ＊／60 ／／ 訪問鏈表中的各個節(jié)點的有效數(shù)據(jù)，這個訪問必須注意不能使用p、p1、p2，而只能61 ／／ 使用pHeader。62／／ 訪問鏈表第1個節(jié)點的有效數(shù)據(jù)63printf（＂node1 data： ％d．n＂， pHeader－＞data）； 64／／printf（＂p－＞data： ％d．n＂， p－＞data）； 65 ／／ pHeader－＞data等同于p－＞data66／／ 訪問鏈表第2個節(jié)點的有效數(shù)據(jù)67printf（＂node2 data： ％d．n＂， pHeader－＞pNext－＞data）； 68／／printf（＂p1－＞data： ％d．n＂， p1－＞data）； 69／／ pHeader－＞pNext－＞data等同于p1－＞data70／／ 訪問鏈表第3個節(jié)點的有效數(shù)據(jù)71printf（＂node3 data： ％d．n＂， pHeader－＞pNext－＞pNext－＞data）； 72／／printf（＂p2－＞data： ％d．n＂， p2－＞data）； 73／／ pHeader－＞pNext－＞pNext－＞data等同于p2－＞data74return 0；75｝

編譯結果：

1root＠ubuntu－virtual－machine：／mnt／hgfs／day＃ gcc file3．c2root＠ubuntu－virtual－machine：／mnt／hgfs／day＃ ．／a．out3node1 data： 1．4node2 data： 2．5node3 data： 3．

3、在第一個節(jié)點插入元素：

在代碼演示之前，先名兩個概念：頭指針和頭節(jié)點

a、什么是頭指針？

頭指針并不是節(jié)點，而是一個普通指針，只占4字節(jié)。頭指針的類型是struct node ＊類型的，所以它才能指向鏈表的節(jié)點。一個典型的鏈表的實現(xiàn)就是：頭指針指向鏈表的第1個節(jié)點，然后第1個節(jié)點中的指針指向下一個節(jié)點，然后依次類推一直到最后一個節(jié)點。這樣就構成了一個鏈。

b、什么是頭節(jié)點？

其實它和一般的節(jié)點差不多，只不過要注意的是：第一，它緊跟在頭指針后面。第二，頭節(jié)點的數(shù)據(jù)部分是空的（有時候不是空的，而是存儲整個鏈表的節(jié)點數(shù)），指針部分指向下一個節(jié)點，也就是第一個節(jié)點。

1 ＃include ＜stdio．h＞ 2 ＃include ＜strings．h＞ 3 ＃include ＜stdlib．h＞ 4 ／／ 構建一個鏈表的節(jié)點 5 struct node 6 ｛ 7int data； ／／ 有效數(shù)據(jù) 8struct node ＊pNext； ／／ 指向下一個節(jié)點的指針 9 ｝；10 ／／ 作用：創(chuàng)建一個鏈表節(jié)點11 ／／ 返回值：指針，指針指向我們本函數(shù)新創(chuàng)建的一個節(jié)點的首地址12 struct node ＊ create＿node（int data）13 ｛14struct node ＊p ＝ （struct node ＊）malloc（sizeof（struct node））；15if （NULL ＝＝ p）16｛17 printf（＂malloc error．n＂）；18 return NULL；19 ｝20／／ 清理申請到的堆內存21bzero（p， sizeof（struct node））；22／／ 填充節(jié)點23p－＞data ＝ data；24p－＞pNext ＝ NULL； 25return p；26 ｝27 ／／ 思路：由頭指針向后遍歷，直到走到原來的最后一個節(jié)點。原來最后一個節(jié)點里面的pNext是NULL，現(xiàn)在我們只要將它改成new就可以了。添加了之后新節(jié)點就變成了最后一個。2829 ／／ 計算添加了新的節(jié)點后總共有多少個節(jié)點，然后把這個數(shù)寫進頭節(jié)點中。3031void insert＿tail（struct node ＊pH， struct node ＊new）32 ｛33int cnt ＝ 0；34／／ 分兩步來完成插入35／／ 第一步，先找到鏈表中最后一個節(jié)點36struct node ＊p ＝ pH；37while （NULL ?。?p－＞pNext）38｛39 p ＝ p－＞pNext； 40 ／／ 往后走一個節(jié)點41 cnt＋＋；42｝43／／ 第二步，將新節(jié)點插入到最后一個節(jié)點尾部44p－＞pNext ＝ new；45pH－＞data ＝ cnt ＋ 1；46 ｝47void insert＿head（struct node ＊pH， struct node ＊new）48｛49／／ 第1步： 新節(jié)點的next指向原來的第一個節(jié)點50new－＞pNext ＝ pH－＞pNext；51／／ 第2步： 頭節(jié)點的next指向新節(jié)點的地址52pH－＞pNext ＝ new；53／／ 第3步： 頭節(jié)點中的計數(shù)要加154pH－＞data ＋＝ 1；55 ｝56int main（void）57｛58／／ 定義頭指針59／／struct node ＊pHeader ＝ NULL； 60 ／／ 這樣直接insert＿tail會段錯誤。61struct node ＊pHeader ＝ create＿node（0）；62insert＿head（pHeader， create＿node（1））；63insert＿tail（pHeader， create＿node（2））；64insert＿head（pHeader， create＿node（3））；65 ／＊66pHeader ＝ create＿node（1）；6768／／ 將本節(jié)點和它前面的頭指針關聯(lián)起來 69pHeader－＞pNext ＝ create＿node（432）； 70／／ 將本節(jié)點和它前面的頭指針關聯(lián)起來 71pHeader－＞pNext－＞pNext ＝ create＿node（123）； 72／／ 將來要指向下一個節(jié)點的首地址73／／ 至此創(chuàng)建了一個有1個頭指針＋3個完整節(jié)點的鏈表。74 ＊／75／／ 訪問鏈表中的各個節(jié)點的有效數(shù)據(jù)，這個訪問必須注意不能使用 p、p1、p2，而只能76／／ 使用pHeader。77／／ 訪問鏈表頭節(jié)點的有效數(shù)據(jù)78printf（＂beader node data： ％d．n＂， pHeader－＞data）； 79／／ 訪問鏈表第1個節(jié)點的有效數(shù)據(jù)80printf（＂node1 data： ％d．n＂， pHeader－＞pNext－＞data）； 81／／ 訪問鏈表第2個節(jié)點的有效數(shù)據(jù)82printf（＂node2 data： ％d．n＂， pHeader－＞pNext－＞pNext－＞data）； 83／／ 訪問鏈表第3個節(jié)點的有效數(shù)據(jù)84printf（＂node3 data： ％d．n＂， pHeader－＞pNext－＞pNext－＞pNext－＞data）； 85return 0；86｝

編譯結果；

1 root＠ubuntu－virtual－machine：／mnt／hgfs／day＃ gcc file4．c2 root＠ubuntu－virtual－machine：／mnt／hgfs／day＃ ．／a．out3 beader node data： 3．4 node1 data： 3．5 node2 data： 1．6 node3 data： 2．

五、總結：

通過本次鏈表的學習，讓自己對鏈表的理解更加深了，接下來雙鏈表的使用會在后面更新，歡迎大家來關注！！