引言

單鏈表在數據結構中是很重要的一種線性結構，它是單向的，有著非常廣泛的應用領域；雖然現在很多語言中都有封裝好的鏈表類型可以直接使用，但是自己能寫一個鏈表并實現基本操作是至關重要的；

接下來我將用代碼展示單鏈表的創建和一些基本操作；
注：以下代碼僅供參考，并不一定是最優代碼，只是想讓各位了解單鏈表如何進行的一些基本操作；

單鏈表的結構

單鏈表就是由一個一個節點組成，這個節點由一個數據域和指針域組成；
如圖：

所以，我們需要先創建節點結構，然后才能依次組成單鏈表；
注：以下鏈表的數據域的數據類型都是int類型，實際情況可以修改為任意數據類型；

這里使用結構體來創建，代碼如下：

// 單鏈表節點結構 typedef struct Node {int data; // 數據域struct Node* next; // 指針域 }NODE;

可以看到，指針域指向的其實就是該節點本身的數據類型，所以這一點一定要注意！

單鏈表的初始化和創建

有了基本組成單元，那么就要創建鏈表了，這里我分為兩個函數來實現：

• void initList(NODE*& head); // 初始化鏈表
• void creatList(NODE*& head); // 創建一個鏈表

初始化鏈表很簡單，直接看代碼：

// 初始化鏈表 void initList(NODE*& head) {try {head = new NODE;}catch (bad_alloc& e) {cout << "內存分配失敗！！" << endl;cout << e.what() << endl; // 輸出異常信息} // 捕獲異常head->data = 0;head->next = NULL;return; }

這里還有一點值得一提：
當鏈表內存分配失敗時，我是用的是try…catch捕獲的異常，這個使用于現在的大部分新版的編譯器，因為新版編譯器在內存分配失敗的情況下將不再會返回NULL；老版的編譯器入VC++6.0等就會返回NULL，所以一定要注意對內存分配失敗的處理；

接下來就是創建一個單鏈表了，這里使用的是尾插法；
為什么使用尾插法呢？因為頭插法輸出的鏈表和輸入的順序是相反的，所以最好使用尾插法來創建鏈表；

這里創建的鏈表也需要注意：
該鏈表創建時會有一個沒有什么實際意義的頭節點，它的數據域存放的是鏈表的長度，當然創建頭節點的目的也是為了方便對鏈表的操作；

代碼如下：

void creatList(NODE*& head) {// 1，確定創建鏈表長度int len;cout << "請輸入創建鏈表長度：" << endl;cin >> len;// 鏈表長度不應該為0和負數if (len <= 0) {cout << "創建鏈表長度不能是0或負數" << endl;return;}head->data = len; // 頭節點數據域存放鏈表長度// 2，創建一個尾節點NODE* tail = head; // 定義一個節點為尾節點，指向頭節點，它將代替頭節點移動tail->next = NULL;// 3，循環創建新的節點for (int i = 0; i < len; ++i) {cout << "請輸入第" << i + 1 << "個數據" << endl;int val;cin >> val;NODE* newNode = NULL;// 創建一個新節點作為臨時節點try {newNode = new NODE; }catch (bad_alloc& e) {cout << "內存分配失敗！！" << endl;cout << e.what() << endl;} // 捕獲異常newNode->data = val; // 新節點數據域賦值tail->next = newNode; // 將新節點掛在尾節點后面newNode->next = NULL; // 新節點指針域為空tail = newNode; // 尾節點為新的節點}return; }

這一步的操作一定要學會，因為只有創建出來鏈表后你才能對鏈表進行其他操作；

遍歷輸出鏈表和鏈表長度

下面的操作是遍歷鏈表并輸出和返回鏈表的長度；

為什么把這兩個函數放一起？因為它們的操作可以說是一模一樣，只是有很小的改動；

當然對鏈表遍歷也是非常簡單，所以不需要有太大的心理負擔；


遍歷輸出鏈表代碼如下：

void traverseList(NODE* head) {NODE* p = head->next; // 臨時節點p指向頭節點的下一個節點while (p) {cout << p->data << " ";p = p->next; // p移向下一個節點}cout << endl;return; }

雖然簡單，但是還是需要注意一點：
臨時節點不要忘記，因為頭節點是沒有什么實際意義的節點，所以輸出頭節點并沒有什么意義；

獲取鏈表長度代碼如下：

int listLength(NODE* head) {NODE* p = head->next; // 臨時節點p指向頭節點的下一個節點int len = 0; // 鏈表長度while (p) {++len; // 長度加一p = p->next; // p移向下一個節點}return len; }

是不是很簡單，只是只需要修改關鍵的一句代碼即可求得鏈表長度；

排序操作

有時我們可能會遇到一些情況需要對鏈表進行排序，鏈表是線性存儲結構，那么該如何排序呢？
其實也很簡單，只需要將數據域的內容進行交換排序即可，也就是只對數據域進行操作，并不改變鏈表結構；

這里是順序排序；
代碼如下：

void sortList(NODE*& head) {int t;NODE* p;NODE* q;for (p = head->next; p != NULL; p = p->next) {for (q = p->next; q != NULL; q = q->next) {// 交換數據域的內容if (p->data > q->data) {t = p->data;p->data = q->data;q->data = t;}}} }

這個排序算法并不是最優的，但是非常好理解，所以先學會一種方法再去突破吧！

插入操作和刪除操作

單鏈表和數組都是線性存儲結構，數組的優點是：可以實現快速查詢；鏈表的的優點是：可以快速的實現插入和刪除操作；
所以，插入和刪除操作在單鏈表中是非常非常非常重要的！！

對于鏈表的插入和刪除操作，只需要記住一點：插入/刪除哪個位置，一定要找到該位置的前一個位置；

還是畫個圖吧：

我來描述一下這張圖：

• 想要在data3的位置插入新節點節點s，首先需要找到data3的前一個位置：data2的位置，也就是p指針指向的位置；
• 接下來就是插入操作了
• 第一步1：先把新節點s掛到data3上；（即讓s節點指向data3節點）
• 第二步2：斷開p節點和data3節點的聯系；
• 第三步3：讓p節點指向s節點；（即p節點指針域存放s節點地址）

下面就來看一下代碼：

void insertListByPostion(NODE*& head, int data, int pos) {int i = 1;NODE* p = head;while (p && i < pos) {++i;p = p->next;}if (!p || i > pos) {cout << "插入位置不存在！！" << endl;return;}NODE* newNode = NULL;try {newNode = new NODE;}catch (bad_alloc& e) {cout << "內存分配失敗！！" << endl;cout << e.what() << endl;} // 捕獲異常newNode->data = data;newNode->next = p->next;p->next = newNode;head->data++;cout << "插入成功！！" << endl; }

需要注意：插入節點位置必須存在，即首部尾部和中間，所以前面需要先判斷插入位置是否存在；


刪除操作更簡單，如圖：

同樣描述一下該圖：

• 想要刪除q節點，所以先找到q節點前一個位置：p節點；
• 接下來是刪除操作：
• 第一步：讓p節點指向r節點
• 第二步：釋放q節點內存空間

是不是很簡單；

來看一下代碼如何實現：

void deleteListByPostion(NODE*& head, int pos) {int i = 1;NODE* p = head;while (p->next && i < pos) {p = p->next;++i;}if (!p->next || i > pos) {cout << "刪除位置不存在！！" << endl;return;}NODE* q = p->next;p->next = q->next;cout << "刪除成功！！刪除元素為：" << q->data << endl;delete q;head->data--; }

同樣需要注意：刪除節點位置必須存在，所以需要先判斷插入位置是否存在，因為刪除只能刪除節點只能刪除存在的節點，所以判斷條件和插入節點有些不同，不理解可以畫個圖細細品味；

按順序合并兩個有序鏈表

這個操作其實已經不算是單鏈表的基本操作了，它是將兩個順序的鏈表合并為一個順序的鏈表，并且使用O(1)的空間復雜度，既不能使用額外空間，但是考研時經常會出現，所以就來實現一下；
其實力扣上有原題，可以看看我的這篇文章：21. 合并兩個有序鏈表(C語言)，這里就不再寫解析了；

代碼如下：

void mergeTwoLists(NODE*& l1, NODE*& l2, NODE*& list) {list->data = l1->data + l2->data; // 頭節點數據域為兩個鏈表個數之和NODE* p = list;NODE* list1 = l1->next; // list1為l1頭節點下一個節點NODE* list2 = l2->next; // list2為l2頭節點下一個節點// 要對沒有頭節點的鏈表進行操作，一定不能帶上頭節點進行比較while (list1 && list2) {if (list1->data < list2->data) {p->next = list1;list1 = list1->next;}else {p->next = list2;list2 = list2->next;}p = p->next;}p->next = list1 ? list1 : list2;return; }

其實這里還是需要注意一點：
力扣上的測試鏈表是沒有頭指針的，所以我們的鏈表不能直接去使用力扣上的代碼，需要進行一些小改動，但是基本的算法思想還是一樣的；

逆序鏈表

這個操作是將鏈表逆置，且同樣不能使用額外內存空間；這個力扣上也有原題，解析可以看看我的這篇文章：劍指 Offer 24. 反轉鏈表(C語言)

這個操作其實非常簡單，就是一個雙指針操作；

代碼如下：

void reverseList(NODE*& head, NODE*& list) {// 雙指針list = head; // 先把頭節點連接到新的鏈表上NODE* fast = head->next;NODE* slow = NULL;while (fast) {NODE* node = fast->next;fast->next = slow;slow = fast;fast = node;}list->next = slow; }

同樣需要注意：
力扣上的測試鏈表是沒有頭指針的，所以我們的鏈表不能直接去使用力扣上的代碼，需要進行一些小改動，但是基本的算法思想還是一樣的；

總結

鏈表的操作其實是非常多的，這里只是為你開一個頭，不管你是剛學習數據結構的小白，還是有經驗的老手，都希望這篇文章可以給你帶來一些啟發；
數據結構的學習并不一定會讓你瞬間感覺到編程能力的提升，這也是很多人學完數據結構感覺沒什么用的原因；但是正是數據結構描述了我們生活抽象的事物，讓它們變成了代碼展示出來，數據結構在你的編程路上是要一直學習和理解的，只有對底層有更深入的了解，你的編程之路才能走的更順更遠！！！
希望我們一起進步！！

歡迎大家的點評！

總結

以上是生活随笔為你收集整理的数据结构解析——小白也能看懂的单链表的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。