線性數據結構：單向鏈表

放棄眼高手低，你真正投入學習，會因為找到一個新方法產生成就感，學習不僅是片面的記單詞、學高數......只要是提升自己的過程，探索到了未知，就是學習。

? ? ? ? ? ? ? ? ??一.鏈表的理解

? ? ? ? ?二.鏈表的分類（重點理解）

三.無頭單向非循環鏈表

? ? ? ? ? ? ? ? ? ??三.1 節點結構以及理解?

? ? ? ? ? ?三.2遍歷鏈表

??三.3尾插

??三.4增加節點

? 三.5尾刪

? 三.6頭刪

??三.7頭插

? 三.8查找數據

??三.8插在目標節點前面

??三.9插在目標節點后面

??三.10刪除目標節點

在上篇我們學習了順序表，它是在計算機內存中以數組形式保存的線性表，特點是通過一組地址連續的存儲的單元依次存儲線性表中的各個元素，既然地址是連續的，它存在以下幾個問題：

1：在中間/頭部插入刪除，需要對整個空間地址、內容進行移動，比較麻煩

2：如果空間不夠用，那么就需要擴容，這個過程需要拷貝原空間數據，釋放舊空間，消耗較大

3：空間浪費問題，當你已經擴容好了一片空間，但是很多用不完或者又不夠用，需要重新對空間問題進行解決

綜合起來，我們需要更加高效的線性存儲結構：鏈表

一.鏈表的理解

定義：鏈表是一種線性結構，由一系列節點組成，鏈表存在頭（頭節點）和尾（尾節點），節點之間通過指針關聯，每一個數據元素都是獨立存儲的（地址不連續）。鏈表通過指針鏈接次序實現數據元素的邏輯順序，每個節點包含兩個組成部分：數據域與指針。數據域用來存儲數據，指針負責指向下一個節點。鏈表的起點為頭節點，尾節點則是空指針（NULL），用來表示鏈表的結束。

抽象圖示：

特點：?1：動態性。靈活刪除或者插入節點

? ? ? ? ? ? 2：內存利用率高。充分利用空間，實現動態內存管理

? ? ? ? ? ? 3：插入與刪除操作效率高。順序表的刪除插入時間復雜度為O（N），那么鏈表的對應時? ? ? ? ? ? ? ? ? ?間復雜度則達到了O（1），可以在很短的時間內完成插入刪除操作

? ? ? ? ? ? 4：查詢效率低。我們知道鏈表從頭到尾，需要遍歷整個鏈表才能找到目標節點，它的查? ? ? ? ? ? ? ? ? ? ? 找時間復雜度則為O（N）

二.鏈表的分類（重點理解）

鏈表主要可以分為以下3大類：

單向鏈表：單向鏈表中的每一個節點只包含一個指針，指向下一個節點，數據元素的邏輯順序通過鏈表中的指針鏈接次序實現

雙向鏈表：雙向鏈表中的每個節點包含2個指針，分別指向前一個節點與后一個節點

循環鏈表：循環鏈表的第一個節點和最后一個節點通過指針相連，形成一個環狀結構，循環鏈表可以是單向也可以是雙向的

在這3大類中我們還需要了解幾個概念：頭指針與頭節點與帶頭節點與不帶頭節點

頭指針：本質是一個結構體類型的指針，存儲第一個節點的地址

頭節點：本質是一個節點，有數據域與指針。在單鏈表的第一個節點之前再附加一個節點，稱為? ? ? ? ? ? ? ? ? 頭節點，頭節點的數據域可以不放任何信息，也可以記錄鏈表長度。若鏈表是帶有頭節? ? ? ? ? ? ? ? ? 點的，則頭指針指向頭節點的存儲位置

帶頭節點：與其它節點一樣，有數據域跟指針，可以理解為一個結構體變量，只是頭指針指向頭節點存儲位置，圖示：

不帶頭節點：我們知道帶頭節點是指針指向頭節點，那么反之，不帶頭節點是頭指針指向第一個節點的存儲位置

那么我們簡單總結：無論是否有頭節點，都存在一個頭指針，頭指針都指向鏈表的一個節點，只是區分頭指針是指向第一個節點還是頭節點，圖示理解：

鏈表會根據：單頭或者不帶頭、單向或者雙向、循環或者非循環進行組合，一共可以組合出8種

其中只要掌握2種，就可以觸類旁通了，我們先重點來學習以下第一種：

無頭單向非循環鏈表? ? ? ? ?帶頭雙向循環鏈表

三.無頭單向非循環鏈表

上面我們已經了解了無頭跟有頭的區別，那這里我們輕而易舉的可以畫個圖：

?三.1 節點結構以及理解?

我們創建了一個指針next跟數據域，這個數據域的類型就是你要存儲的類型，可自行設置，指針指向下一個節點的地址。

這里解釋一下next指針：?鏈表中的next是指向下一個節點的指針（通常稱為next）。所有節點通過next指針連接起來，使得數據元素可以按照一定的順序排列。在雙向鏈表中還有一個指向前一個節點的指針：prev，這使得雙向鏈表可以從頭到尾或從尾到前遍歷，這里僅僅簡單科普一下！

下面我們看幾個常見寫法，來進行錯誤糾正：

我們先用typedef對結構體類型進行重命名，?命名之前結構體類型是struct Student，命名之后可以簡寫為Student，這樣減少了代碼量，方便閱讀。上圖第一種寫法跟第二種寫法都存在一個問題：在進行重命名的結構體里面，類型必須寫全，這是因為現在是屬于聲明階段，出了這個結構體以后才可以用簡寫的方式。舉個例子：一個方案的發布必須是已經制作好的。這里也一樣，typedef目前在這個結構體只是類似方案制作階段，出了這個結構體之后才可以簡化使用。

三.2遍歷鏈表

在遍歷鏈表時，我們需要讓指針靈活的動起來，而不能直接讓節點里面的指針動起來，不然就出問題了，因此我們需要創建一個指針指向節點中的第一個指針，改變這個指針的指向是不是就達到了動態節點的效果！比如我新創建了一個指針 cur?（在下文我們方便講解，還會用到這個指針），每次通過改變cur的指向來改變當前訪問的節點。這里需要注意cur指針是不會真正動的，只是它的指向地址發生改變。圖示理解如下：

在進行鏈表的增刪查找功能前，我們需要掌握遍歷，代碼參考如下：

我們仔細解釋一下圖中比較重要的地方：

1：為什么不需要判斷指針head的有效性？因為head是頭指針，指向第一個節點，指針是空指針只能說明指向的地址不存在，而指向的地址的空間內容是否存在不相干，就好比通訊錄空間，我只是沒有存儲聯系人進去，但是有這個空間，這個大家可以理解嗎？我再舉個例子：現在有一個水杯（head），我需要去拿水杯喝水（head指向地址的內容），杯子里面有沒有水跟這個水杯存不存在不相關！

2：指針head跟指針cur的關系：head是頭指針，是不可以移動的，而將head指針指向的地址交給cur，通過cur的指向移動，實現對節點內容的管理

??3：對while循環的條件的討論：我們看下面2個圖

我們知道頭指針head將第一個節點的地址傳給cur，cur是指向下一個節點的地址的，當cur到達最后一個節點時，此時cur的指向還是最后一個節點的地址，而cur->next已經是指向空指針了，就少進入了循環一次。cur是通過cur->next來改變cur的指向的，而cur->next已經指向下一個節點了。這個我們結合2張圖理解（物理圖示與邏輯圖示）：

?三.3尾插

我們從字面上理解，就是在當前最后一個節點后面再插入新節點！再把新節點與尾節點連接起來，那么我們需要用3個操作：找尾節點? 開辟新節點? 連接節點（最后會對3個步驟匯總代碼講思路）

先解釋一下為什么要用二級指針？因為涉及空鏈表跟鏈表存在的討論，需要更改地址的問題。

下面我們進行第一個操作，找尾節點。我們已經知道如何遍歷鏈表了！既然指針指向下一個節點的地址，那么當這個指針是空指針的時候，是不是就表示找到尾了！這里需要理解的是，這個指針的指向是NULL，因為我們是需要開辟新節點的，自然要在最后一個節點后面開辟，所以需要讓它指向NULL，如圖理解（tail跟cur等價）：

//找尾節點
void Traversal(Pointdef** head)
{//判斷鏈表是不是空鏈表if(*head==NULL){//空鏈表的話新節點作為第一個節點*head=newspointer;}else{//托付head的指向給cur指針Pointdef* cur = *head;//找尾while (cur){//改變 cur 指針的指向cur = cur->next;}//此時cur指向NULL，也就是尾節點的后面}
}

下面我們進行第二個操作：開辟新節點。新節點的創建不能直接使用原節點的類型去創建，因為這樣創建的新節點只是臨時變量，為什么呢？因為我們是在函數里面創建的，當函數調用完，里面的變量就全部銷毀了。因此我們需要用到動態內存開辟，同時初始化指針，至于為什么要初始化，后面會細說，因此用malloc給新節點開辟一塊空間，才能延長新節點生命周期。代碼如下：

Pointdef* Greate()
{Pointdef* news = malloc(sizeof(Pointdef));if (news == NULL){perror("malloc");return NULL;}//理解：news指針指向新節點地址，news->next表示對新節點的指針初始化了news->next = NULL;return news;
}

首先我們看這個函數，它的類型是結構體指針類型，為哈？因為我們用這個函數來開辟新節點，那么開辟的空間類型是節點的結構體類型，我們知道鏈表是用指針連接起來的，那么我們只需要返回一個指針就行了，指針類型肯定是結構體類型，然后用malloc開辟新節點，節點大小是結構體的大小。下面緊接著判斷，判斷新節點是否開辟成功，news->next=NULL，這句話就是告訴我們這是新節點的尾端，因為new->next是指向下一個節點，也就是NULL。大家肯定想知道為哈不初始化這個新節點的數據域呢？單鏈表節點的數據域是否初始化，可以自行設定，未初始化的數據域可能出現一些隨機值。

下面進行第三個操作：連接這2個節點。在連接前需要判斷這個鏈表的頭指針是否存在，否則需要將新節點作為第一個節點，不然會出現嚴重問題。這里涉及空鏈表跟鏈表不存在的區別，如下：

鏈表不存在：如：head==NULL，鏈表都不存在，那么一切操作都無用，因此在使用鏈表時需要檢查鏈表是否存在

空鏈表：鏈表存在，頭指針為空，如：cur==NULL，它的存在與否需要分情況，比如我需要刪除某個節點，那么空鏈表肯定是不行的，而打印、插入節點這些沒什么影響，具體需要根據操作來判斷

//增加新節點
void NewPointer(Pointdef** head)
{assert(head);Pointdef* newpointer = Greate();//如果這個頭指針的指向是空指針，那么鏈表是空的，將這個新節點作為新的節點if (*head == NULL){*head = newpointer;}else{//頭指針指向交給cur，用cur找尾Pointdef* cur = *head;//找尾while (cur->next ！= NULL){cur = cur->next;}//連接cur->next = newpointer;}
}

總結：上面代碼我們是進行拆分了的，如果看不懂，我們可以用筆一步步記錄，理清思路。尾插的總思路就是：先判斷鏈表是否存在，再用函數新增節點，然后判斷空鏈表，最后找尾進行連接。參考完整代碼：

//增加新節點
Pointdef* Greate()
{Pointdef* news = malloc(sizeof(Pointdef));if (news == NULL){perror("malloc");return NULL;}//理解：news指針指向新節點地址，new->next標識它是將要接入的最后一個節點，相當于初始化了news->next = NULL;return news;
}//找尾+連接
void NewPointer(Pointdef** head)
{//判斷鏈表是否存在assert(head);Pointdef* newpointer = Greate();//如果這個頭指針的指向是空指針，那么鏈表是空的，將這個新節點作為新的節點if (*head == NULL){*head = newpointer;}else{Pointdef* cur = *head;//找尾while (cur->next == NULL){cur = cur->next;}//連接cur->next = newpointer;}
}

三.4增加節點

新增我們在上面的尾插已經使用過了，我們就不再重復說了，每次操作接收函數返回的指針，就可以控制新增節點的地方，新增節點的函數都是通用的，代碼如下：

//增加新節點
Pointdef* Greate()
{Pointdef* news = malloc(sizeof(Pointdef));if (news == NULL){perror("malloc");return NULL;}//理解：news指針指向新節點地址，news->next理解為標識自己是將要接入的最后一個節點，相當于初始化了news->next = NULL;return news;
}

三.5尾刪

顧名思義，就是刪除最后一個節點，那么我們猜測步驟也就只有2步：先找? 再刪

我們需要先遍歷鏈表，然后找到最后一個節點，進行刪除釋放，再把倒數第二個節點的cur->next改為NULL。尾刪需要注意幾種情況，空鏈表跟唯一節點的鏈表，2種情況，跟尾插一樣，可能需要更改頭指針地址，因此需要使用二級指針。找尾節點跟倒數第二個節點一個指針肯定不夠，因此我們需要兩個指針，一個來找尾節點，一個來找倒數第二個節點。我們來看思維圖，理清雙指針的關系：

代碼如下：

//尾刪
void Taildeletion(Pointdef** head)
{//判斷鏈表是否存在assert(head);//判斷是否是空鏈表assert(*head);//判斷一個節點的情況if (((*head)->next) == NULL){//直接釋放free(*head);*head = NULL;}else{//找尾Pointdef* cur = *head;while (cur->next){cur = cur->next;}//找倒數第二個節點Pointdef* tail = *head;while (cur->next){tail = cur;cur = cur->next;}//釋放尾節點free(cur);cur = NULL;//改變倒數第二個的指向tail->next = NULL;}}

三.6頭刪

有了尾刪的基礎，頭刪也一樣需要考慮空鏈表跟鏈表不存在的情況，先改變頭指針指向，然后直接刪就行了，也不需要找頭，是不是很簡單！代碼如下：

//頭刪
void Headdeletion(Pointdef** head)
{//判斷鏈表是否存在assert(head);//判斷是否是空鏈表assert(*head);//創建指針指向頭Pointdef* cur = *head;//改變頭指針指向*head = (*head)->next;//釋放free(cur);cur = NULL;
}

三.7頭插

頭插管他是不是空鏈表！直接搞個節點當頭就行了！那么我們需要先開一個新節點，再改變頭指針指向，代碼如下：

//頭插
void HeadPointer(Pointdef** head)
{//判斷鏈表是否存在assert(head);//新開節點Pointdef* cur = Greate();//改頭指針跟指向cur->next = *head;*head = cur;
}

三.8查找數據

我們只要給某個節點的數據域初始化，那么就可以通過遍歷鏈表來找這個節點的地址，例如我初始化了某個節點的整型數據域為x，那么就直接遍歷就行了！

//查找數據
Pointdef* Find(Pointdef* head , int x)
{Pointdef* cur = head;//查找while (cur){if (cur->data==x){return cur;}else{cur = cur->next;}}//否則沒有找到return NULL;
}

三.8插在目標節點前面

之前，我們學習了尾插與頭插，那么如果在中間插入新節點呢？我們先遍歷鏈表，找到那個節點，然后在它的前面插入新節點即可（自行選擇插入的節點前后，我這里例舉插在目標節點前面）。這里需要注意的是如果目標節點是第一個節點，那么就是頭插，這里需要改變指針指向，不能是形參，因此需要二級指針。根據對應節點的指針找目標節點，這里我假設cur是目標節點代碼如下：

void Middle(Pointdef** head ,Pointdef* cur,int x)
{//注意：cur是目標節點//判斷空鏈表,否則是頭插if (*head==NULL){HeadPointer(head);}else{//先開新節點Pointdef* news = Greate();//找要增加的節點位置Pointdef* pc = *head;while (pc->next!=cur){pc = pc->next;}//此時pc指向cur的前一個節點//連接節點pc->next = news;news->next = cur;}
}

三.9插在目標節點后面

這個跟前面插在節點前面的類似，但是更簡單。借助指針找到目標節點，在連接就行。代碼如下：

//插在節點后面
void Outdle( Pointdef* cur)
{//注意：cur是目標節點assert(cur);//開辟新節點Pointdef* news = Greate();Pointdef* pc = cur->next;//連接cur->next = news;news->next = pc;
}

三.10刪除目標節點

考慮空鏈表跟鏈表不存在兩種情況，然后循環找到目標節點，連接左右節點再刪除即可！

//刪除目標節點
void Omit(Pointdef** head, Pointdef* cur)
{//cur是要刪除的節點指針//判斷鏈表是否存在assert(head);//判斷空鏈表assert(*head);//循環找目標節點Pointdef* pc = *head;while (pc->next = cur){pc = pc->next;}//連接目標節點的左右節點pc->next = cur->next;//先連接再釋放free(cur);cur = NULL;
}

好了，本篇到此結束，大家記得一鍵三連哦！幾天后我會繼續出帶頭雙向循環鏈表的博文！感謝支持！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！