1. 鏈表的概念及結(jié)構(gòu)

在順序表中存在一定的問題：

1. 順序表的中間/頭部插入、刪除需要挪動(dòng)數(shù)據(jù)
2. 擴(kuò)容存在性能的消耗
3. 會(huì)有空間的浪費(fèi)

而鏈表是獨(dú)立的節(jié)點(diǎn)組成

鏈表概念：鏈表是一種物理存儲(chǔ)結(jié)構(gòu)上非連續(xù)、非連續(xù)的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的。

鏈表、順序表都是線性表

邏輯結(jié)構(gòu)一定是線性的
物理結(jié)構(gòu)不一定是線性的

圖中指針變量plist保存的是第一個(gè)節(jié)點(diǎn)的地址，我們稱plist此時(shí)“指向”第一個(gè)節(jié)點(diǎn)，如果我們希望plist“指向第二個(gè)節(jié)點(diǎn)時(shí)，只需要修改plist保存的內(nèi)容為0x0012FFA0

為什么還需要指針變量來保存下一個(gè)節(jié)點(diǎn)的位置？

鏈表中每個(gè)節(jié)點(diǎn)都是獨(dú)立申請(qǐng)的（即需要插入數(shù)據(jù)時(shí)才去申請(qǐng)一塊節(jié)點(diǎn)的空間），我們需要通過指針變量來保存下一個(gè)節(jié)點(diǎn)位置才能從當(dāng)前節(jié)點(diǎn)找到下一個(gè)節(jié)點(diǎn)。

鏈表是由一個(gè)一個(gè)的節(jié)點(diǎn)組成的
一個(gè)節(jié)點(diǎn)由兩部分組成：要存儲(chǔ)的數(shù)據(jù)+指針

int a = 1;
int* pa = &a;

節(jié)點(diǎn)結(jié)構(gòu)的定義

struct SListNode{
int data;
struct SListNode* next;
}

鏈表結(jié)構(gòu)體的打印方式：

補(bǔ)充說明：

1. 鏈?zhǔn)綑C(jī)構(gòu)在邏輯上是連續(xù)的，在物理結(jié)構(gòu)上不一定連續(xù)
2. 節(jié)點(diǎn)一般是從堆上申請(qǐng)的
3. 從堆上申請(qǐng)來的空間，是按照一定策略分配出來的，每次申請(qǐng)的空間可能連續(xù)，可能不連續(xù)

2. 實(shí)現(xiàn)單鏈表

初始化

typedef int SLTDataType;
//鏈表是由節(jié)點(diǎn)組成的
typedef struct SListNode
{SLTDataType data;//節(jié)點(diǎn)數(shù)據(jù)struct SListNode* next;//指針變量保存下一個(gè)節(jié)點(diǎn)的地址
}SLTNode;

尾插

//公共部分，開辟一個(gè)新的節(jié)點(diǎn)
SLTNode* SLBuyNode(SLTDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc");exit(1);}newnode->data = x;newnode->next = NULL;return newnode;
}//鏈表的尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = SLBuyNode(x);//鏈表為空，新節(jié)點(diǎn)作為pheadif (*pphead == NULL){*pphead = newnode;return;}//鏈表不為空，找尾結(jié)點(diǎn)SLTNode* ptail = *pphead;while (ptail->next){ptail = ptail->next;}//ptril就是尾結(jié)點(diǎn),將尾結(jié)點(diǎn)指向newnodeptail->next = newnode;
}

頭插

void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = SLBuyNode(x);//newnode  *ppheadnewnode->next = *pphead;*pphead = newnode;
}

尾刪

void SLTPopBack(SLTNode** pphead)
{assert(pphead);//鏈表不能為空assert(*pphead);//指向第一個(gè)節(jié)點(diǎn)的地址//鏈表不為空//鏈表只有一個(gè)節(jié)點(diǎn)/多個(gè)節(jié)點(diǎn)if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;return;}SLTNode* ptail = *pphead;SLTNode* prev = NULL;while (ptail->next){prev = ptail;ptail = ptail->next;}prev->next = NULL;//銷毀尾結(jié)點(diǎn)free(ptail);ptail = NULL;
}

頭刪

void SLTPopFront(SLTNode** pphead)
{assert(pphead);//鏈表不能為空assert(*pphead);//讓第二個(gè)節(jié)點(diǎn)稱為新的頭SLTNode* next = (*pphead)->next;//->優(yōu)先級(jí)高于*//把舊的頭節(jié)點(diǎn)釋放掉free(*pphead);*pphead = next;
}

查找

SLTNode* SLTFind(SLTNode** pphead, SLTDataType x)
{assert(*pphead);//遍歷鏈表SLTNode* pcur = *pphead;while (pcur){if (pcur->data == x){return pcur;}pcur = pcur->next;}//沒有找到當(dāng)前數(shù)據(jù)return NULL;
}

在指定位置之前插入數(shù)據(jù)

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);assert(pos);//鏈表不能為空assert(*pphead);//pos剛好是頭結(jié)點(diǎn)if (pos == *pphead){//頭插SLTPushFront(pphead, x);return;}//pos不是頭結(jié)點(diǎn)的情況SLTNode* newnode = SLBuyNode(x);SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}//找到了prev->next = newnode;newnode->next = pos;
}

在指定位置之后插入數(shù)據(jù)

void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode = SLBuyNode(x);newnode->next = pos->next;pos->next = newnode;
}

刪除指定位之前的節(jié)點(diǎn)

void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(*pphead);assert(pos);//pos剛好是頭結(jié)點(diǎn)，沒有前驅(qū)節(jié)點(diǎn)，執(zhí)行頭刪if (*pphead == pos){//頭刪SLTPopFront(pphead);return;}SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;}

刪除指定位置之后pos節(jié)點(diǎn)

//刪除指定位置之后pos節(jié)點(diǎn)
void SLTEraseAfter(SLTNode** pphead, SLTNode* pos)
{assert(pos);assert(pos->next);//pos  pos->next  pos->next->nextSLTNode* del = pos->next;pos->next = pos->next->next;free(del);del = NULL;
}}

銷毀鏈表

//銷毀鏈表
void SListDesTory(SLTNode** pphead)
{assert(pphead);assert(*pphead);SLTNode* pcur = *pphead;while (pcur){SLTNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}

3. 完整代碼

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "SList.h"
#include <stdio.h>//void SlistTest1()
//{
//	//一般不會(huì)這樣去創(chuàng)建鏈表，這里只是為了給大家展示鏈表的打印
//	SLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode));
//	node1->data = 1;
//	SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode));
//	node2->data = 2;
//	SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode));
//	node3->data = 3;
//	SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode));
//	node4->data = 4;
//
//	node1->next = node2;
//	node2->next = node3;
//	node3->next = node4;
//	node4->next = NULL;
//
//	SLTNode* plist = node1;//定一個(gè)指針指向第一個(gè)節(jié)點(diǎn)
//	SLTPrint(plist);
//}void SlistTest2()
{SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 0);SLTPrint(plist);//SLTPushFront(&plist, 2);//SLTPushFront(&plist, 3);//SLTPrint(plist);SLTPopBack(&plist);SLTPrint(plist);
}void SlistTest3()
{SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 0);SLTPrint(plist);//頭刪SLTPopFront(&plist);SLTPrint(plist);//查找SLTNode* FindRet = SLTFind(&plist, 0);if (FindRet){printf("找到了\n");}else {printf("未找到\n");}SLTInsert(&plist, FindRet, 100);SLTPrint(plist);SLTInsertAfter(FindRet, 200);SLTPrint(plist);//刪除指定位置的節(jié)點(diǎn)SLTErase(&plist, FindRet);SLTPrint(plist);//銷毀節(jié)點(diǎn)SListDesTory(&plist);
}int main()
{SlistTest3();//SlistTest2();//SlistTest1();return 0;
}

SList.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "SList.h"
#include <assert.h>//鏈表的打印
void SLTPrint(SLTNode* phead)
{SLTNode* pcur = phead;while (pcur){printf("%d->", pcur->data);pcur = pcur->next;}printf("NULL\n");
}SLTNode* SLBuyNode(SLTDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc");exit(1);}newnode->data = x;newnode->next = NULL;return newnode;
}//鏈表的尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = SLBuyNode(x);//鏈表為空，新節(jié)點(diǎn)作為pheadif (*pphead == NULL){*pphead = newnode;return;}//鏈表不為空，找尾結(jié)點(diǎn)SLTNode* ptail = *pphead;while (ptail->next){ptail = ptail->next;}//ptril就是尾結(jié)點(diǎn),將尾結(jié)點(diǎn)指向newnodeptail->next = newnode;
}//頭插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = SLBuyNode(x);//newnode  *ppheadnewnode->next = *pphead;*pphead = newnode;
}//尾刪
void SLTPopBack(SLTNode** pphead)
{assert(pphead);//鏈表不能為空assert(*pphead);//指向第一個(gè)節(jié)點(diǎn)的地址//鏈表不為空//鏈表只有一個(gè)節(jié)點(diǎn)/多個(gè)節(jié)點(diǎn)if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;return;}SLTNode* ptail = *pphead;SLTNode* prev = NULL;while (ptail->next){prev = ptail;ptail = ptail->next;}prev->next = NULL;//銷毀尾結(jié)點(diǎn)free(ptail);ptail = NULL;
}//頭刪
void SLTPopFront(SLTNode** pphead)
{assert(pphead);//鏈表不能為空assert(*pphead);//讓第二個(gè)節(jié)點(diǎn)稱為新的頭SLTNode* next = (*pphead)->next;//->優(yōu)先級(jí)高于*//把舊的頭節(jié)點(diǎn)釋放掉free(*pphead);*pphead = next;
}//查找
SLTNode* SLTFind(SLTNode** pphead, SLTDataType x)
{assert(*pphead);//遍歷鏈表SLTNode* pcur = *pphead;while (pcur){if (pcur->data == x){return pcur;}pcur = pcur->next;}//沒有找到當(dāng)前數(shù)據(jù)return NULL;
}//在指定位置之前插入數(shù)據(jù)
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);assert(pos);//鏈表不能為空assert(*pphead);//pos剛好是頭結(jié)點(diǎn)if (pos == *pphead){//頭插SLTPushFront(pphead, x);return;}//pos不是頭結(jié)點(diǎn)的情況SLTNode* newnode = SLBuyNode(x);SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}//找到了prev->next = newnode;newnode->next = pos;
}//在指定位置之后插入數(shù)據(jù)
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode = SLBuyNode(x);newnode->next = pos->next;pos->next = newnode;
}//刪除指定位之前的節(jié)點(diǎn)
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(*pphead);assert(pos);//pos剛好是頭結(jié)點(diǎn)，沒有前驅(qū)節(jié)點(diǎn)，執(zhí)行頭刪if (*pphead == pos){//頭刪SLTPopFront(pphead);return;}SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;}//刪除指定位置之后pos節(jié)點(diǎn)
void SLTEraseAfter(SLTNode** pphead, SLTNode* pos)
{assert(pos);assert(pos->next);//pos  pos->next  pos->next->nextSLTNode* del = pos->next;pos->next = pos->next->next;free(del);del = NULL;
}//銷毀鏈表
void SListDesTory(SLTNode** pphead)
{assert(pphead);assert(*pphead);SLTNode* pcur = *pphead;while (pcur){SLTNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}

SList.h

#define _CRT_SECURE_NO_WARNINGS 1#include <stdio.h>
#include <stdlib.h>typedef int SLTDataType;
//鏈表是由節(jié)點(diǎn)組成的
typedef struct SListNode
{SLTDataType data;struct SListNode* next;
}SLTNode;//鏈表的打印
void SLTPrint(SLTNode* phead);//鏈表的頭插和尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);
void SLTPushFront(SLTNode** pphead, SLTDataType x);//鏈表的頭刪和尾刪
void SLTPopBack(SLTNode** pphead);
void SLTPopFront(SLTNode** pphead);//查找
SLTNode* SLTFind(SLTNode** pphead, SLTDataType x);//在指定位置之前插入數(shù)據(jù)
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//在指定位置之后插入數(shù)據(jù)
void SLTInsertAfter(SLTNode* pos, SLTDataType x);//刪除指定位置之前pos節(jié)點(diǎn)
void SLTErase(SLTNode** pphead, SLTNode* pos);
//刪除指定位置之后pos節(jié)點(diǎn)
void SLTEraseAfter(SLTNode** pphead, SLTNode* pos);//銷毀鏈表
void SListDesTory(SLTNode** pphead);

4. 鏈表的分類

鏈表的結(jié)構(gòu)非常多樣，一下情況組合組合起來就有8種鏈表結(jié)構(gòu)：

鏈表說明：

在單鏈表中，“頭結(jié)點(diǎn)”的“頭”和“帶頭”鏈表是兩個(gè)概念
單鏈表中提到的“頭結(jié)點(diǎn)”指的是第一個(gè)有效的節(jié)點(diǎn)
“帶頭”鏈表里的“頭”指的是無效的節(jié)點(diǎn)

雖然鏈表的種類非常之多，但是使用比較多的只有兩種：單鏈表（不帶頭單向不循環(huán)鏈表）和雙向鏈表（帶頭雙向循環(huán)鏈表）