目錄
一.為什么要使用鏈表存儲數據？
二.鏈表的分類
單向或者雙向鏈表：
帶頭或者不帶頭：
循環或者非循環：
三.鏈表的實現
3.1無頭單向非循環鏈表的實現：
3.1.1單向無頭非循環鏈表的聲明
3.1.2動態申請一個節點
?3.1.3單鏈表打印
??3.1.4單鏈表尾插
???3.1.5單鏈表的頭插
???3.1.6單鏈表的尾刪
???3.1.7單鏈表頭刪
???3.1.8單鏈表查找
??3.1.9單鏈表在pos位置之前插入x
?3.1.10單鏈表在pos位置之后插入x
??3.1.11單鏈表刪除pos之后的值
?3.1.12單鏈表刪除pos位置的值
3.1.13銷毀單鏈表
?頭文件：
?測試文件：
3.2帶頭雙向循環鏈表的實現
3.2.1帶頭雙向循環鏈表的聲明
3.2.2動態申請一個節點
?3.2.3哨兵位初始化(創建鏈表的頭結點)
?3.2.4帶頭雙向循環鏈表打印
?3.2.5雙向鏈表尾插
??3.2.6雙向鏈表頭插
3.2.7雙線鏈表尾刪
3.2.8雙線鏈表頭刪
3.2.9雙向鏈表查找
?3.2.10雙向鏈表在pos的前面進行插入
3.2.11雙向鏈表刪除pos位置的結點
?3.2.12雙向鏈表銷毀
頭文件：
測試文件：
四.鏈表總結
一.為什么要使用鏈表存儲數據？
內存空間是所有程序的公共資源，在一個復雜的系統運行環境下，空閑的內存空間可能散落在內存各處。我們知道，存儲數組的內存空間必須是連續的，而當數組非常大時，內存可能無法提供如此大的連續空間。此時鏈表的靈活性優勢就體現出來了。
讓我們來看看鏈表的結構：
- ?可以得出：鏈表是一種物理存儲結構上非連續、非順序的存儲結構，數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的 。
- 上述圖中的鏈表知識鏈表中的其中一種
二.鏈表的分類
單向或者雙向鏈表：
帶頭或者不帶頭：
循環或者非循環：
雖然鏈表的種類很多，但我們主要使用的還是無頭單向非循環鏈表（OJ題中最常見的鏈表）和帶頭循環雙向鏈表（實踐應用）。
三.鏈表的實現
3.1無頭單向非循環鏈表的實現：
對于項目我們需要區分測試文件和接口文件，這樣做有利于培養良好的代碼能力。
3.1.1單向無頭非循環鏈表的聲明
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int SLNDataType;// 聲明一個 Single Link List Node （單向無頭鏈表）typedef struct SLLN
{//節點值SLNDataType val;//指向下一個節點的指針struct SLLN* next;}SLNode;3.1.2動態申請一個節點
// 動態申請一個節點
SLNode* CreateNode(SLNDataType x)
{SLNode* newnode = (SLNode*)calloc(1, sizeof(SLNode));if (newnode == NULL){perror("calloc");//直接終止程序exit(-1);}newnode->val = x;newnode->next = NULL;return newnode;
}?3.1.3單鏈表打印
// 單鏈表打印
void SLNodePrint(SLNode* plist)
{SLNode* cur = plist;if (cur != NULL){while (cur){printf("%d->", cur->val);cur = cur->next;}printf("NULL");printf("\n");}else{printf("鏈表為空無需打印\n");}
}??3.1.4單鏈表尾插
// 單鏈表尾插
void SLNodePushBack(SLNode** pplist, SLNDataType x)
{//先創造一個新節點SLNode* newnode = CreateNode(x);SLNode* tail = *pplist;//將plist賦值給tail//找尾if (*pplist == NULL){*pplist = newnode;}else{while (tail->next != NULL){tail = tail->next;}tail->next = newnode;}
}???3.1.5單鏈表的頭插
// 單鏈表的頭插
void SLNodePushFront(SLNode** pplist, SLNDataType x)
{//先創建一個新節點SLNode* newnode = CreateNode(x);newnode->next = *pplist;*pplist = newnode;
}???3.1.6單鏈表的尾刪
// 單鏈表的尾刪
void SLNodePopBack(SLNode** pplist)
{//如果鏈表為空則不能刪除，報錯assert(*pplist);//找尾SLNode* tail = *pplist;//tail移動時我們還需要有一個前驅指針 prev 跟在tail后面SLNode* prev = NULL;//單鏈表只有一個節點情況下尾刪if (tail->next == NULL){free(*pplist);*pplist = NULL;}//單鏈表有多個節點情況下尾刪else{while (tail->next != NULL){prev = tail;tail = tail->next;}free(tail);tail = NULL;prev->next = NULL;}}???3.1.7單鏈表頭刪
// 單鏈表頭刪
void SLNodePopFront(SLNode** pplist)
{//當鏈表為空時不能刪除，報錯assert(*pplist);SLNode* cur = *pplist;SLNode* newplist = (*pplist)->next;free(cur);cur = NULL;*pplist = newplist;}???3.1.8單鏈表查找
// 單鏈表查找(配合在pos位置插入或者刪除使用)
SLNode* SLNodeFind(SLNode* plist, SLNDataType x)
{while (plist != NULL){if (plist->val == x){return plist;}else{plist = plist->next;}}return NULL;
}??3.1.9單鏈表在pos位置之前插入x
//單鏈表在pos位置之前插入x
void SLNodeInsertBefore(SLNode** pplist, SLNode* pos, SLNDataType x)//此處傳入二級指針pplist是為了在頭插時改變plist的值，傳址調用
{//此處需要對哪個指針進行斷言檢查呢？assert(pos && *pplist);//防止人為亂傳空SLNode* cur = *pplist;SLNode* prev = NULL;//前驅指針prev保存cur前一個節點的地址if (pos == *pplist){//在頭節點位置前插入x實質上就是頭插，我們調用之前寫的頭插函數即可SLNodePushFront(pplist, x);}else{SLNode* newnode = CreateNode(x);while (cur != pos){prev = cur;cur = cur->next;}prev->next = newnode;newnode->next = cur;}
}?3.1.10單鏈表在pos位置之后插入x
// 單鏈表在pos位置之后插入x
void SLNodeInsertAfter(SLNode* pos, SLNDataType x)
{//鏈表為空無法在pos位置之后插入xassert(pos);SLNode* newnode = CreateNode(x);if (newnode == NULL){perror(calloc);return;}SLNode* next = pos->next;pos->next = newnode;newnode->next = next;}??3.1.11單鏈表刪除pos之后的值
//單鏈表刪除pos之后的值
void SLNodeEraseAfter(SLNode* pos)
{//鏈表為空無法刪除assert(pos);//當鏈表只剩下一個節點或者pos后面無節點時也無法刪除assert(pos->next);SLNode* del = pos->next;pos->next = pos->next->next;free(del);del == NULL;
}?3.1.12單鏈表刪除pos位置的值
//單鏈表刪除pos位置的值
void SLNodeErasepos(SLNode** pplist, SLNode* pos)
{//鏈表為空不能刪除assert(*pplist);SLNode* cur = *pplist;SLNode* prev = NULL;//前驅指針prev保存cur前一個節點的地址if (pos != *pplist){while (cur != pos){prev = cur;cur = cur->next;}SLNode* next = cur->next;free(cur);cur = NULL;//鏈接兩個節點prev->next = next;}else{SLNode* next = cur->next;free(cur);cur = NULL;//更新頭節點*pplist = next;}
}3.1.13銷毀單鏈表
//銷毀鏈表
void SLNodeDestory(SLNode** pplist)
{assert(pplist);assert(*pplist);SLNode* cur = *pplist;while (cur){SLNode* next = cur->next;free(cur);cur = next;}*pplist = NULL;
}以上代碼為單鏈表所實現的所有功能（接口）
?頭文件：
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int SLNDataType;// 聲明一個 Single Link List Node （單向無頭鏈表）typedef struct SLLN
{//節點值SLNDataType val;//指向下一個節點的指針struct SLLN* next;}SLNode;// 動態申請一個節點
SLNode* CreateNode(SLNDataType x);// 單鏈表打印
void SLNodePrint(SLNode* plist);// 單鏈表尾插
void SLNodePushBack(SLNode** pplist, SLNDataType x);// 單鏈表的頭插
void SLNodePushFront(SLNode** pplist, SLNDataType x);// 單鏈表的尾刪
void SLNodePopBack(SLNode** pplist);// 單鏈表頭刪
void SLNodePopFront(SLNode** pplist);// 單鏈表查找
SLNode* SLNodeFind(SLNode* plist, SLNDataType x);//單鏈表在pos位置之前插入x
void SLNodeInsertBefore(SLNode** pplist, SLNode* pos, SLNDataType x);//單鏈表在pos位置之后插入x
void SLNodeInsertAfter(SLNode* pos, SLNDataType x);//單鏈表刪除pos位置之后的值
void SLNodeEraseAfter(SLNode* pos);//單鏈表刪除pos位置的值
void SLNodeErasepos(SLNode** pplist, SLNode* pos);//銷毀單鏈表
void SLNodeDestory(SLNode** pplist);
?測試文件：
#define _CRT_SECURE_NO_WARNINGS 1
#include"Single_linked_lists.h"//單鏈表尾插測試
void text1()
{SLNode* plist = NULL;SLNodePushBack(&plist, 1);SLNodePushBack(&plist, 2);SLNodePushBack(&plist, 3);SLNodePushBack(&plist, 4);SLNodePrint(plist);
}
//單向鏈表頭插測試
void text2()
{SLNode* plist = NULL;SLNodePushFront(&plist, 1);SLNodePushFront(&plist, 2);SLNodePushFront(&plist, 3);SLNodePushFront(&plist, 4);SLNodePrint(plist);}
//單向鏈表尾刪測試
void text3()
{//SLNode* plist = NULL;//SLNodePushBack(&plist, 1);//SLNodePushBack(&plist, 2);//SLNodePushBack(&plist, 3);//SLNodePushBack(&plist, 4);多節點尾刪測試//SLNodePopBack(&plist);SLNode* plist = NULL;SLNodePushBack(&plist, 1);//單節點尾刪測試SLNodePopBack(&plist);SLNodePrint(plist);
}
//單向鏈表頭刪測試
void text4()
{SLNode* plist = NULL;SLNodePushBack(&plist, 1);SLNodePushBack(&plist, 2);SLNodePushBack(&plist, 3);SLNodePushBack(&plist, 4);//頭刪測試SLNodePopFront(&plist);SLNodePrint(plist);
}//單向鏈表查找 val 測試
void text5()
{SLNode* plist = NULL;SLNodePushBack(&plist, 1);SLNodePushBack(&plist, 2);SLNodePushBack(&plist, 3);SLNodePushBack(&plist, 4);//查找val測試SLNode* pos = SLNodeFind(plist, 4);printf("%p\n", pos);
}// 單鏈表在pos位置之后插入 x 測試
void text6()
{SLNode* plist = NULL;SLNodePushBack(&plist, 1);SLNodePushBack(&plist, 2);SLNodePushBack(&plist, 3);SLNodePushBack(&plist, 4);//pos之后插入xSLNode* pos = SLNodeFind(plist, 3);SLNodeInsertAfter(pos, 0);SLNodePrint(plist);
}//單鏈表刪除pos之后的值測試
void text7()
{SLNode* plist = NULL;SLNodePushBack(&plist, 1);SLNodePushBack(&plist, 2);SLNodePushBack(&plist, 3);SLNodePushBack(&plist, 4);//單鏈表刪除pos之后的值測試SLNode* pos = SLNodeFind(plist, 3);SLNodeEraseAfter(pos);SLNodePrint(plist);}
//單鏈表在pos前一個位置插入 x 測試
void text8()
{SLNode* plist = NULL;SLNodePushBack(&plist, 1);SLNodePushBack(&plist, 2);SLNodePushBack(&plist, 3);SLNodePushBack(&plist, 4);SLNodePrint(plist);SLNode* posbefore = SLNodeFind(plist, 3);//單鏈表在pos前一個位置插入 x 測試SLNodeInsertBefore(&plist, posbefore, 0);SLNodePrint(plist);}
//單鏈表刪除pos位置的值
void text9()
{SLNode* plist = NULL;SLNodePushBack(&plist, 1);SLNodePushBack(&plist, 2);SLNodePushBack(&plist, 3);SLNodePushBack(&plist, 4);SLNodePrint(plist);//單鏈表刪除pos位置的值SLNode* pos1 = SLNodeFind(plist, 1);SLNode* pos2 = SLNodeFind(plist, 3);SLNodeErasepos(&plist, pos1);SLNodeErasepos(&plist, pos2);SLNodePrint(plist);}
int main()
{//text1();//單鏈表尾插測試//text2();//單向鏈表頭插測試//text3();//單向鏈表尾刪測試//text4();//單向鏈表頭刪測試//text5();//單向鏈表查找 val 測試//text6();// 單鏈表在pos位置之后插入 x 測試//text7();//單鏈表刪除pos之后的值測試//text8();//單鏈表在pos前一個位置插入 x 測試//text9();//單鏈表刪除pos位置的值測試return 0;
}
3.2帶頭雙向循環鏈表的實現
3.2.1帶頭雙向循環鏈表的聲明
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int DataType;typedef struct ListNode
{DataType val;struct LTNode* next;struct LTNode* prev;
}LTNode;3.2.2動態申請一個節點
//Create one newnode
LTNode* Createnode(DataType x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){perror("malloc");exit(-1);}newnode->val = x;newnode->next = NULL;newnode->prev = NULL;return newnode;
}?3.2.3哨兵位初始化(創建鏈表的頭結點)
//哨兵位初始化(創建鏈表的頭結點)
LTNode* LTInit()
{LTNode* plist = Createnode(-1);plist->next = plist;plist->prev = plist;return plist;
}?3.2.4帶頭雙向循環鏈表打印
//帶頭雙向循環鏈表打印
void LTPrint(LTNode* plist)
{assert(plist);LTNode* cur = plist->next;printf("哨兵位<=>");while (cur != plist){printf("%d<=>", cur->val);cur = cur->next;}printf("\n");
}?3.2.5雙向鏈表尾插
// 雙向鏈表尾插
void LTNodePushBack(LTNode* plist, DataType x)
{LTNode* newnode = Createnode(x);LTNode* tail = plist->prev;tail->next = newnode;newnode->prev = tail;plist->prev = newnode;newnode->next = plist;}??3.2.6雙向鏈表頭插
// 雙向鏈表頭插
void LTNodePushFront(LTNode* plist, DataType x)
{assert(plist);LTNode* first = plist->next;LTNode* newnode = Createnode(x);newnode->next = first;first->prev = newnode;plist->next = newnode;newnode->prev = plist;}3.2.7雙線鏈表尾刪
// 雙向鏈表尾刪
void LTNodePopBack(LTNode* plist)
{//防止鏈表不存在assert(plist);//防止鏈表為空assert(plist->next);LTNode* tail = plist->prev;plist->prev = tail->prev;LTNode* tailprev = tail->prev;tailprev->next = plist;
}3.2.8雙線鏈表頭刪
// 雙向鏈表頭刪
void LTNodePopFront(LTNode* plist)
{//防止鏈表不存在assert(plist);//防止鏈表為空assert(plist->next);LTNode* first = plist->next;LTNode* second = first->next;plist->next = second;second->prev = plist;free(first);first = NULL;}3.2.9雙向鏈表查找
// 雙向鏈表查找
LTNode* LTNodeFind(LTNode* plist, DataType x)
{//防止鏈表不存在assert(plist);//防止鏈表為空assert(plist->next);LTNode* cur = plist->next;while (cur != plist){if (cur->val == x){return cur;}cur = cur->next;}return NULL;
}?3.2.10雙向鏈表在pos的前面進行插入
// 雙向鏈表在pos的前面進行插入
void LTNodeInsert(LTNode* pos, DataType x)
{assert(pos);LTNode* newnode = Createnode(x);LTNode* posprev = pos->prev;posprev->next = newnode;newnode->next = pos;pos->prev = newnode;newnode->prev = posprev;
}
3.2.11雙向鏈表刪除pos位置的結點
// 雙向鏈表刪除pos位置的結點
void LTNodeErase(LTNode* pos)
{//防止傳空assert(pos);LTNode* posnext = pos->next;LTNode* posprev = pos->prev;posprev->next = posnext;posnext->prev = posprev;free(pos);
}?3.2.12雙向鏈表銷毀
// 雙向鏈表銷毀
void LTNodeDestory(LTNode* plist)
{//防止鏈表不存在assert(plist);LTNode* cur = plist->next;while (cur != plist){LTNode* next = cur->next;free(cur);cur = next;}free(plist);plist = NULL;
}以上代碼為單鏈表所實現的所有功能（接口）
頭文件：
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int DataType;typedef struct ListNode
{DataType val;struct LTNode* next;struct LTNode* prev;
}LTNode;//生成新節點
LTNode* Createnode(DataType x);//哨兵位初始化
LTNode* LTInit();//帶頭雙向循環鏈表打印
void LTPrint(LTNode* plist);// 雙向鏈表銷毀
void LTNodeDestory(LTNode* plist);// 雙向鏈表尾插
void LTNodePushBack(LTNode* plist, DataType x);// 雙向鏈表尾刪
void LTNodePopBack(LTNode* plist);// 雙向鏈表頭插
void LTNodePushFront(LTNode* plist, DataType x);// 雙向鏈表頭刪
void LTNodePopFront(LTNode* plist);// 雙向鏈表查找
LTNode* LTNodeFind(LTNode* plist, DataType x);// 雙向鏈表在pos的前面進行插入
void LTNodeInsert(LTNode* pos, DataType x);// 雙向鏈表刪除pos位置的結點
void LTNodeErase(LTNode* pos);測試文件：
#define _CRT_SECURE_NO_WARNINGS 1
#include"list.h"
// 初步測試
void test1()
{// 創建一個哨兵位頭節點LTNode* plist = LTInit();LTPrint(plist);
}// 尾插尾刪測試
void test2()
{LTNode* plist = LTInit();LTNodePushBack(plist, 1);LTNodePushBack(plist, 2);LTNodePushBack(plist, 3);LTNodePushBack(plist, 4);LTNodePushBack(plist, 5);LTPrint(plist);LTNodePopBack(plist);LTPrint(plist);
}
// 頭插頭刪測試
void test3()
{LTNode* plist = LTInit();LTNodePushFront(plist, 1);LTNodePushFront(plist, 2);LTNodePushFront(plist, 3);LTNodePushFront(plist, 4);LTNodePushFront(plist, 5);LTPrint(plist);LTNodePopFront(plist);LTPrint(plist);
}
// 鏈表查找測試
void test4()
{LTNode* plist = LTInit();LTNodePushBack(plist, 1);LTNodePushBack(plist, 2);LTNodePushBack(plist, 3);LTNodePushBack(plist, 4);LTNodePushBack(plist, 5);LTPrint(plist);LTNode* pos = LTNodeFind(plist, 3);printf("%d\n", pos->val);}
// 雙向鏈表在pos的前面進行插入測試
void test5()
{LTNode* plist = LTInit();LTNodePushBack(plist, 1);LTNodePushBack(plist, 2);LTNodePushBack(plist, 3);LTNodePushBack(plist, 4);LTNodePushBack(plist, 5);LTPrint(plist);LTNode* pos = LTNodeFind(plist, 3);LTNodeInsert(pos, 100);LTNodeInsert(pos, 200);LTPrint(plist);}
// 雙向鏈表刪除pos位置的結點測試
void test6()
{LTNode* plist = LTInit();LTNodePushBack(plist, 1);LTNodePushBack(plist, 2);LTNodePushBack(plist, 3);LTNodePushBack(plist, 4);LTNodePushBack(plist, 5);LTPrint(plist);LTNode* pos = LTNodeFind(plist, 3);LTNodeErase(pos);LTPrint(plist);
}
// 鏈表銷毀測試
void test7()
{LTNode* plist = LTInit();LTNodePushBack(plist, 1);LTNodePushBack(plist, 2);LTNodePushBack(plist, 3);LTNodePushBack(plist, 4);LTNodePushBack(plist, 5);LTNodeDestory(plist);plist = NULL;LTPrint(plist);
}
int main()
{// 初步測試test1();// 尾插尾刪測試test2();// 頭插頭刪測試test3();// 鏈表查找測試test4();// 雙向鏈表在pos的前面進行插入測試test5();// 雙向鏈表刪除pos位置的結點測試test6();// 鏈表銷毀測試//test7();return 0;
}四.鏈表總結
這是一個我個人做的思維導圖,對于學習鏈表的一些總結，希望對你有所幫助：
)
