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

一、鏈表引入的緣由：

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

二、什么是鏈表？

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

三、單鏈表中的一些細節：

1、單鏈表的構成：

a、鏈表是由節點組成的，節點中包含：有效數據和指針。

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

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

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

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

b、為什么要使用堆呢？

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

c、基本概念：

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

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

數據段：數據段存的是數，像全局變量就是存在數據段的。

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

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

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

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

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

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

a＝10；

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

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

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

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

實例：

1 ＃include ＜stdio．h＞ 2 ＃include ＜strings．h＞ 3 ＃include ＜stdlib．h＞ 4 int main（void） 5｛ 6 ／／創建一個鏈表節點 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 ／／填充節點15 p－＞data＝1；16 p－＞pNext ＝NULL；／／將來要指向下一個節點的首地址；實際操作時將下 一 個節點malloc返回的指針賦值給這個17｝

四、實例演示：

1、單鏈表的實現：

1 ＃include ＜stdio．h＞ 2 ＃include ＜strings．h＞ 3 ＃include ＜stdlib．h＞ 4 ／／ 構建一個鏈表的節點 5 struct node 6 ｛ 7 int data； ／／ 有效數據 8struct node ＊pNext； ／／ 指向下一個節點的指針 9 ｝；10 int main（void）11 ｛12／／ 定義頭指針13struct node ＊pHeader ＝ NULL；14／／15／／ 每創建一個新的節點，把這個新的節點和它前一個節點關聯起來16／／ 創建一個鏈表節點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／／ 填充節點26p－＞data ＝ 1；27p－＞pNext ＝ NULL； ／／ 將來要指向下一個節點的首地址28 ／／ 實際操作時將下一個節點malloc返回的指針賦值給這個2930pHeader ＝ p； ／／ 將本節點和它前面的頭指針關聯起來 31／／33／／ 每創建一個新的節點，把這個新的節點和它前一個節點關聯起來34／／ 創建一個鏈表節點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／／ 填充節點44p1－＞data ＝ 2；45p1－＞pNext ＝ NULL； ／／ 將來要指向下一個節點的首地址46 ／／ 實際操作時將下一個節點malloc返回的指針賦值給這個474849p－＞pNext ＝ p1； ／／ 將本節點和它前面的頭指針關聯起來 505152／／5354／／5556／／ 每創建一個新的節點，把這個新的節點和它前一個節點關聯起來5758／／ 創建一個鏈表節點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／／ 填充節點69p2－＞data ＝ 3；70p1－＞pNext ＝ p2； ／／ 將來要指向下一個節點的首地址71 ／／ 實際操作時將下一個節點malloc返回的指針賦值給這個 72／／73／／ 至此創建了一個有1個頭指針＋3個完整節點的鏈表。7475／／ 下面是4．9．3節的代碼76／／ 訪問鏈表中的各個節點的有效數據，這個訪問必須注意不能使用p、p1、p2，而只能77／／ 使用pHeader。7879／／ 訪問鏈表第1個節點的有效數據80printf（＂node1 data： ％d．n＂， pHeader－＞data）； 81printf（＂p－＞data： ％d．n＂， p－＞data）； ／／ pHeader－＞data等同于p－＞data8283／／ 訪問鏈表第2個節點的有效數據84printf（＂node2 data： ％d．n＂， pHeader－＞pNext－＞data）； 85printf（＂p1－＞data： ％d．n＂， p1－＞data）； 86／／ pHeader－＞pNext－＞data等同于p1－＞data8788／／ 訪問鏈表第3個節點的有效數據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、在鏈表末尾添加元素：

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

1 ＃include ＜stdio．h＞ 2 ＃include ＜strings．h＞ 3 ＃include ＜stdlib．h＞ 4 ／／ 構建一個鏈表的節點 5 struct node 6｛ 7int data； ／／ 有效數據 8struct node ＊pNext； ／／ 指向下一個節點的指針 9 ｝；10／／ 作用：創建一個鏈表節點11／／ 返回值：指針，指針指向我們本函數新創建的一個節點的首地址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／／ 填充節點23p－＞data ＝ data；24p－＞pNext ＝ NULL； 25return p；26 ｝27 void insert＿tail（struct node ＊pH， struct node ＊new）28 ｛29／／ 分兩步來完成插入30／／ 第一步，先找到鏈表中最后一個節點31struct node ＊p ＝ pH；32while （NULL ?。?p－＞pNext）33｛34 p ＝ p－＞pNext； 35／／ 往后走一個節點36｝37／／ 第二步，將新節點插入到最后一個節點尾部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 ／／ 將本節點和它前面的頭指針關聯起來 52pHeader－＞pNext ＝ create＿node（432）； 53／／ 將本節點和它前面的頭指針關聯起來 5455pHeader－＞pNext－＞pNext ＝ create＿node（123）； 56／／ 將來要指向下一個節點的首地址5758／／ 至此創建了一個有1個頭指針＋3個完整節點的鏈表。59 ＊／60 ／／ 訪問鏈表中的各個節點的有效數據，這個訪問必須注意不能使用p、p1、p2，而只能61 ／／ 使用pHeader。62／／ 訪問鏈表第1個節點的有效數據63printf（＂node1 data： ％d．n＂， pHeader－＞data）； 64／／printf（＂p－＞data： ％d．n＂， p－＞data）； 65 ／／ pHeader－＞data等同于p－＞data66／／ 訪問鏈表第2個節點的有效數據67printf（＂node2 data： ％d．n＂， pHeader－＞pNext－＞data）； 68／／printf（＂p1－＞data： ％d．n＂， p1－＞data）； 69／／ pHeader－＞pNext－＞data等同于p1－＞data70／／ 訪問鏈表第3個節點的有效數據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、在第一個節點插入元素：

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

a、什么是頭指針？

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

b、什么是頭節點？

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

1 ＃include ＜stdio．h＞ 2 ＃include ＜strings．h＞ 3 ＃include ＜stdlib．h＞ 4 ／／ 構建一個鏈表的節點 5 struct node 6 ｛ 7int data； ／／ 有效數據 8struct node ＊pNext； ／／ 指向下一個節點的指針 9 ｝；10 ／／ 作用：創建一個鏈表節點11 ／／ 返回值：指針，指針指向我們本函數新創建的一個節點的首地址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／／ 填充節點23p－＞data ＝ data；24p－＞pNext ＝ NULL； 25return p；26 ｝27 ／／ 思路：由頭指針向后遍歷，直到走到原來的最后一個節點。原來最后一個節點里面的pNext是NULL，現在我們只要將它改成new就可以了。添加了之后新節點就變成了最后一個。2829 ／／ 計算添加了新的節點后總共有多少個節點，然后把這個數寫進頭節點中。3031void insert＿tail（struct node ＊pH， struct node ＊new）32 ｛33int cnt ＝ 0；34／／ 分兩步來完成插入35／／ 第一步，先找到鏈表中最后一個節點36struct node ＊p ＝ pH；37while （NULL ?。?p－＞pNext）38｛39 p ＝ p－＞pNext； 40 ／／ 往后走一個節點41 cnt＋＋；42｝43／／ 第二步，將新節點插入到最后一個節點尾部44p－＞pNext ＝ new；45pH－＞data ＝ cnt ＋ 1；46 ｝47void insert＿head（struct node ＊pH， struct node ＊new）48｛49／／ 第1步： 新節點的next指向原來的第一個節點50new－＞pNext ＝ pH－＞pNext；51／／ 第2步： 頭節點的next指向新節點的地址52pH－＞pNext ＝ new；53／／ 第3步： 頭節點中的計數要加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／／ 將本節點和它前面的頭指針關聯起來 69pHeader－＞pNext ＝ create＿node（432）； 70／／ 將本節點和它前面的頭指針關聯起來 71pHeader－＞pNext－＞pNext ＝ create＿node（123）； 72／／ 將來要指向下一個節點的首地址73／／ 至此創建了一個有1個頭指針＋3個完整節點的鏈表。74 ＊／75／／ 訪問鏈表中的各個節點的有效數據，這個訪問必須注意不能使用 p、p1、p2，而只能76／／ 使用pHeader。77／／ 訪問鏈表頭節點的有效數據78printf（＂beader node data： ％d．n＂， pHeader－＞data）； 79／／ 訪問鏈表第1個節點的有效數據80printf（＂node1 data： ％d．n＂， pHeader－＞pNext－＞data）； 81／／ 訪問鏈表第2個節點的有效數據82printf（＂node2 data： ％d．n＂， pHeader－＞pNext－＞pNext－＞data）； 83／／ 訪問鏈表第3個節點的有效數據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．

五、總結：

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