一、链表的概念

       链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。

      上述是书本的定义，链表也是属于线性表，所以在逻辑结构上是线性的，而由于链表的数据与数据之间是通过地址（指针）连接的，所以地址不一定连续，具体要看操作系统分配的地址是否连续。

      下图是链表的形象表示：火车是通过一节一节车厢连接在一起，删除和增加某节车厢不影响其他车厢，即每个车厢都是独立存在，每节车厢是通过钩子连接起来这与链表中每个节点相互独立，却又通过该节点指向下一个节点的指针连接起来有异曲同工之处。

       链表是由一个一个节点组成，节点由要存储的数据+下一个节点地址的指针，如图在第一个节点中保存的数据是1，还有下一个节点的地址：0x0012FFB0,也就是第二个节点的地址。依次往后看，直到第四个节点保存的数据是4，由于它的后面没有节点了，所以它保存的下一个节点的地址是NULL。

二、链表的分类

链表的结构非常多，以下情况组合起来共有8种（2x2x2）链表结构：

1.单向或者双向

在双向链表中，存放了两个指针：next指向下一个节点（后继节点），prev指向前一个节点（前驱节点）

2.带头或者不带头

注意：在上课或者参考书上为了方便理解单链表会把链表的首节点称为头结点，但是这样的称呼是错误的，因为链表中存在一类链表叫做带头链表（不是指链表里的第一个有效的节点），这里的头结点即哨兵位（不保存任何有效数据，仅用来占位置，作用是不需要判断链表的头是否为空），如带头链表中只有头结点，那么我们就称该节点为空链表

3.循环或者不循环

在循环链表中尾节点的指向不为空，它指向了链表中第一个有效的节点

因此在前面我们实现的单链表的全称为：不带头单向不循环链表。链表有上面8种结构，但我们实际中用的最多的是单链表和双向带头循环链表！

三、手动实现单链表

1.链表的初始化

    节点里存储两个变量，这里数据存储使用typedef将全部int改名成SLTDataType，方便以后修改，由于保存的下一个节点的地址也是节点类型，所以使用SListNode*类型，最后也把struct SListNode改名成SLTNode，方便书写。

//定义节点的结构
typedef int SLTDataType;
typedef struct SListNode
{SLTDataType data;struct SListNode* next;}SLTNode;

2.链表的打印

    在实现链表的打印功能前需要手动构造一个链表，如下

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;

以下是链表的打印，具体实现如下：
    1.定义链表结构体指针指向phead
    2.定义pcur等于phead即等于node1
    3.若pcur不为NULL，则打印当前节点的data(存储的数据) ，并让pcur继续往下走
    4.pcur走到为空，跳出while循环，打印NULL
    5.最后打印结果为：1->2->3->4->NULL

注意：在这里直接使用phead来遍历也是一样的，重新创建pcur指针是为了避免由于指针指向的改变，导致无法重新找到链表的首节点

void SLTPrint(SLTNode* phead)
{//pcur存放的是当前节点的地址SLTNode* pcur = phead;while (pcur){printf("%d->", pcur->data);pcur = pcur->next;}printf("NULL\n");
}

3.申请新的节点大小空间

注意：这里要判断申请空间是否成功，如果失败退出，申请成功对data和next进行初始化

SLTNode* SLTBuyNode(SLTDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc fail!\n");exit(1);}newnode->data = x;newnode->next = NULL;return newnode;
}

4.链表的尾插

    向操作系统动态申请一个节点大小的空间 然后断言若传来的是NULL，那么不能解引用，所以需要断言pphead不能为空，但是*pphead可以为空，因为它代表的是空链表，所以可以存在。这里尾插分两种情况

    链表为空：即pphead为空，则让pphead等于newnode(为首节点)即1   

    链表不为空：即pphead不为空，具体步骤如下

     1.定义一个尾节点ptail，初始时等于首节点pphead
    2.遍历链表，结束条件为不能等于尾节点，注意这里结束条件是ptail->next
    3.若为尾节点，则让尾节点4的next指针指向新节点99

链表为空如下：

链表非空如下：

    这里我们发现形参phead的改变没有影响到实参plist的改变（在传值的时候，形参的改变不影响实参 传地址：形参的改变影响实参 ），所以plist应该传地址而不是值，应为&plist，而plist是指针，所以phead要传二级指针来接受一级指针的地址，所以为**pphead。在if语句中药对pphead解引用（*pphead=plist）为一级指针，后面也是同样的意思。

  这里解释下一级指针和二级指针的概念
第一个节点 （解引用） *plist<---------->**phead(解引用两次)，左边例如plist是实参，右边是形参
指向第一个节点的指针 plist<--------->*phead（解引用一次后变成一级指针）
指向第一个节点的指针的地址 （取地址） &plist<----------->pphead（二级指针）

//尾差
void SLTPushBack(SLTNode**pphead, SLTDataType x)
{//如果传来的是NULL，那么不能解引用，所以需要断言pphead不能为空，但是*pphead可以为空，因为它代表的是空链表，所以可以存在assert(pphead);//*pphead就是指向第一个节点的指针//空链表和非空链表两种情况SLTNode* newnode = SLTBuyNode(x);if (*pphead == NULL){*pphead = newnode;}else{SLTNode* ptail = *pphead;//如果ptail为空，那么在循环里面不可以对空指针解引用，所以会报错while (ptail->next){ptail = ptail->next;}//ptail指向的就是尾节点ptail->next = newnode;}
}

5.链表的头插

    1.调用创建新节点的方法
    2.让新节点9的next指针指向原来的头结点1（*pphead）
    3.让新节点(newnode)为新的头结点

//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{//空链表和非空链表都可以运行assert(pphead);SLTNode* newnode = SLTBuyNode(x);newnode->next = *pphead;*pphead = newnode;
}

6.链表的尾删

    代码思路如下：

    1.断言

    2.判断链表中有一个节点还是多个节点

    3.若只有一个节点（pphead->next==NULL），则直接释放，并把*pphead置为NULL

    4.若有多个节点则定义prev和ptail指针指向头结点，然后遍历链表直至到尾节点，然后跳出循环，释放尾节点ptail并置为空，为了不让尾节点前一个节点的next指针为野指针，所以让prev为前一个节点并让其next指向空

注意这里断言时：pphead（一级指针的地址）不能为空，否则不能对二级指针解引用，其次不能让链表为空，总不能删空吧，这不可能的，所以和头插尾插不同的是添加了个（pphead）不能为空

链表中只有一个节点：

链表中多个节点：

//尾删
void SLTPopBack(SLTNode** pphead )
{//这里和头插尾差不一样，因为尾删的话，链表不能为空，总不能删空吧，这不可能的，所以和头插尾插不同的是添加了个*pphead不能为空assert(pphead && *pphead);//链表只有一个节点if ((*pphead)->next == NULL)//这里给*pphead加了个括号，因为有符号的优先级，->的优先级高于*号{free(*pphead);*pphead = NULL;}else{	//链表有多个节点SLTNode* prev = *pphead;SLTNode* ptail = *pphead;while (ptail->next){prev = ptail;ptail = ptail->next;}free(ptail);ptail = NULL;prev->next = NULL;}}

7.链表的头删

1.定义next变量指向头结点的下一个节点
2.释放头结点
2.让next节点变为新的头结点
注意:这里不能直接删除pphead，若删除找不到后面的节点2，所以需要定义next保存下一个节点2

//头删
void SLTPopFront(SLTNode** pphead)
{//这里和尾删是一样的，解释在上面assert(pphead && *pphead);//在这里不能直接删除第一个节点，这样就不能根据原本第一个节点的next指针找到原本第二个节点//在头删方法中，只有一个节点和多个节点如下方法都可以实现SLTNode* next = (*pphead)->next;//这里也是->的优先级大于*号free(*pphead);*pphead = next;}

8.链表的查找

代码思路如下：

1.定义一个变量pcur指向头结点

2.循环遍历，若（if里的语句）pcur存储的data等于要查找的x，则返回该节点

3.否则继续往后遍历链表

4.若循环遍历结束，没有数据等于x，则该数据在链表中不存在

//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{SLTNode* pcur = phead;while (pcur){if (pcur->data == x){return pcur;}else{pcur = pcur->next;}}return NULL;
}

9.在指定位置之前插入数据

代码思路如下：
1.前置条件的断言，如pphead和pos不能为空

2.若指定位置pos为头结点，那么就等于是头插，直接调用头插函数即可（特殊位置）

3.若pos不是头结点，定义prev指向头结点，遍历循环，循环条件为prev的next不等于pos

4.prev->next为pos跳出循环，将新节点的next指向pos，prev的next指向新节点

//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead && pos);//当pos为首节点的时候，会出现对空指针解引用的操作导致下面代码报错//若pos直接等于*pphead的时候则为头插，那么直接调用头插函数if (pos == *pphead){SLTPushFront(pphead, x);}else{SLTNode* newnode = SLTBuyNode(x);SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}newnode->next = pos;prev->next = newnode;}}

10.在指定位置之后插入数据

      注意：1. 这里(newnode->next = pos->next; pos->next = newnode)顺序不能反过来，否则自己指向自己了

                 2.这里只需pos和插入数据两个变量，与在指定位置之前插入数据不一样，不需要遍历找下一个节点，因为pos的next指针存储的就是下一个节点，而在指定位置之前插入数据，pos没有保存前一个节点，需要用pphead遍历链表来寻找

//在指定位置之后插⼊数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode = SLTBuyNode(x);//pos newnode -> (pos->next)newnode->next = pos->next;pos->next = newnode;
}

11.删除指定节点

代码思路：
1.断言pphead不为空且pos不为空，否则怎么删除pos节点
2.这里要判断特殊条件，若pos是头结点则直接调用已写好的头删方法
3.否则循环遍历链表，若prev的next指向pos，则退出循环
4.让prev的next指向pos的下一个节点后再释放pos，并把pos置为空

//删除pos结点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead && pos);//要删除的节点就是头结点if (pos == *pphead){SLTPopFront(pphead);}else {SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}//prev pos pos->nextprev->next = pos->next;free(pos);pos = NULL;}
}

12.删除指定节点之后的数据

在下图我们要删除2节点（pos->next）

1.需要将1节点（pos）的next(pos->next)指向3（pos->next->next）

2.释放2节点（pos->next）
在上面操作中我们发现最后的pos->next指向3节点，也就是说最后释放的不是2而是3节点，所以我们需要定义del变量来存放pos->next

1.del赋值为pos->next,也就是2节点

2.让1节点(pos)的下一个节点为3(del->next)

3.释放节点2（del）并置为空

注意：这里断言不能让pos指向空，也不能为尾节点，因为尾节点之后没有数据，无法删除

//删除pos之后的结点
void SLTEraseAfter(SLTNode* pos)
{assert(pos && pos->next);SLTNode* del = pos->next;//pos del del->nextpos->next = del->next;free(del);del = NULL;
}

13.销毁链表

 不能直接释放链表，应该一个一个释放链表里面的节点，这里不能直接释放节点，应该定义pcur保存该节点，并且还要保存下一个节点的地址，否则要销毁下一个节点的时候找不到该节点地址，变成野指针

代码思路如下：
1.定义pcur指向头结点
2.循环遍历链表，定义next并让他保存要销毁节点的下一个节点
2.释放要销毁的节点，并让链表继续往后遍历（ pcur = next）
3.链表中所有节点都删除跳出循环，还需让*pphead置为空，否则它为野指针

//销毁链表
void SListDestroy(SLTNode** pphead)
{SLTNode* pcur = *pphead;while (pcur){SLTNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}

四、单链表的思考

在上一篇博客里面讲解了顺序表的一些问题，链表相对于顺序表而言有以下几个优势：

1.链表头部插入删除时间复杂度为0(1)
2.链表无需增容
3.链表不存在空间浪费

五.经典链表OJ题

1. 移除链表元素

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/typedef struct ListNode  ListNode;struct ListNode* removeElements(struct ListNode* head, int val) {//创建一个空链表ListNode *newhead,*newtail;newhead=newtail=NULL;//遍历原链表ListNode*pcur=head;while(pcur){//找值不为val的结点尾插到新链表中if(pcur->val!=val){if(newhead==NULL){//链表为空newhead=newtail=pcur;}else{//链表不为空newtail->next=pcur;newtail=newtail->next;}}//遍历原链表pcur=pcur->next; }if(newtail){newtail->next=NULL;}return newhead;
}

2. 反转链表

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head) {if(head==NULL){return head;}ListNode*n1,*n2,*n3;n1=NULL,n2=head,n3=n2->next;while(n2){n2->next=n1;n1=n2;n2=n3;if(n3){n3=n3->next;}}return n1;
}

3. 链表的中间节点

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) {ListNode*slow=head;ListNode*fast=head;while(fast&&fast->next){//fast和fast->next位置不能换，如果先fast-> next,fast都已经为空了，不能对空解引用//代码会报错，只要第一个为假，就不会判断fast->next为真为假slow=slow->next;fast=fast->next->next;}return slow;
}

4. 合并两个有序链表

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/typedef  struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {ListNode*l1=list1;ListNode*l2=list2;if(list1==NULL){return list2;}if(list2==NULL){return list1;}//新链表ListNode*newhead,*newtail;newhead=newtail=NULL;while(l1&&l2){if(l1->val<l2->val){//l1插入到新链表中if(newhead==NULL){//链表为空newhead=newtail=l1;}else{newtail->next=l1;newtail=newtail->next;}l1=l1->next;}else{//l2插入到新链表中if(newhead==NULL){newhead=newtail=l2;}else{newtail->next=l2;newtail=newtail->next;}l2=l2->next;}}//跳出循环，只有两种情况，l1走到空，l2走到空//有没有可能l1l2同时为空？不可能if(l1){newtail->next=l1;}if(l2){newtail->next=l2;}return newhead;
}

5. 相交链表

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {//求出两个链表的长度ListNode*pa=headA,*pb=headB;int sizeA=0,sizeB=0;while(pa){++sizeA;pa=pa->next;}while(pb){++sizeB;pb=pb->next;}int gap=abs(sizeA-sizeB);//abs:求绝对值的函数//让长链表先走gap步ListNode*shortlist=headA;ListNode*longlist=headB;if(sizeA>sizeB){longlist=headA;shortlist=headB;}while(gap--){longlist=longlist->next;}//shortlist  longlist在同一起跑线while(shortlist){if(shortlist==longlist){return shortlist;}shortlist=shortlist->next;longlist=longlist->next;}return NULL;
}

6. 环形链表

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/typedef struct ListNode ListNode;
bool hasCycle(struct ListNode *head) {ListNode*slow=head,*fast=head;while(fast&&fast->next){slow=slow->next;fast =fast->next->next;if(slow==fast){//相遇return true;}}return false;
}

7. 环形链表II

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
typedef struct ListNode ListNode;
struct ListNode *detectCycle(struct ListNode *head) {ListNode*slow=head,*fast=head;while(fast&&fast->next){slow=slow->next;fast=fast->next->next;if(fast==slow){//相遇点ListNode*pcur=head;while(slow!=pcur ){slow=slow->next;pcur=pcur->next;}return pcur;}}return NULL;
}

8. 随机链表的复制

/*** Definition for a Node.* struct Node {*     int val;*     struct Node *next;*     struct Node *random;* };*/
typedef struct Node Node;
//创建新节点
Node*buyNode(int x)
{Node*node=(Node*)malloc(sizeof(Node));node->val=x;node->next=node->random=NULL;return node;
}
void  AddNode(Node*head)
{Node*pcur=head;while(pcur){Node*next=pcur->next;//创建新节点，插入到pcur结点之后Node*newnode=buyNode(pcur->val);newnode->next=pcur->next;pcur->next=newnode;pcur=next;}
}void setRandom(Node*head)
{Node*pcur=head;while(pcur){Node*copy=pcur->next;if(pcur->random){copy->random=pcur->random->next;}pcur=copy->next;}
}
struct Node* copyRandomList(struct Node* head) {if(head==NULL){return head;}//1.  拷贝结点 AddNode(head); //2.   置random指针setRandom(head);//3  断开链表Node*pcur=head;Node*newHead,*newTail;newHead=newTail=pcur->next;while(newTail->next){pcur=newTail->next;newTail->next=pcur->next;newTail=newTail->next;}return newHead;
}

data = pd.read_csv('https://labfile.oss.aliyuncs.com/courses/1283/adult.data.csv')
print(data.head())

六、单链表与双链表最全源码

单链表源码

SList.h源码

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>//定义节点的结构
typedef int SLTDataType;
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);//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead,SLTNode*pos ,SLTDataType x);//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos);//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos);//顺序表的销毁
void SListDestroy(SLTNode**pphead);

SList.c源码

#include"SList.h"void SLTPrint(SLTNode* phead)
{//pcur存放的是当前节点的地址SLTNode* pcur = phead;while (pcur){printf("%d->", pcur->data);pcur = pcur->next;}printf("NULL\n");
}SLTNode* SLTBuyNode(SLTDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc fail!\n");exit(1);}newnode->data = x;newnode->next = NULL;return newnode;
}//尾差
void SLTPushBack(SLTNode**pphead, SLTDataType x)
{//如果传来的是NULL，那么不能解引用，所以需要断言pphead不能为空，但是*pphead可以为空，因为它代表的是空链表，所以可以存在assert(pphead);//*pphead就是指向第一个节点的指针//空链表和非空链表两种情况SLTNode* newnode = SLTBuyNode(x);if (*pphead == NULL){*pphead = newnode;}else{SLTNode* ptail = *pphead;//如果ptail为空，那么在循环里面不可以对空指针解引用，所以会报错while (ptail->next){ptail = ptail->next;}//ptail指向的就是尾节点ptail->next = newnode;}
}//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{//空链表和非空链表都可以运行assert(pphead);SLTNode* newnode = SLTBuyNode(x);newnode->next = *pphead;*pphead = newnode;}//尾删
void SLTPopBack(SLTNode** pphead )
{//这里和头插尾差不一样，因为尾删的话，链表不能为空，总不能删空吧，这不可能的，所以和头插尾插不同的是添加了个*pphead不能为空assert(pphead && *pphead);//链表只有一个节点if ((*pphead)->next == NULL)//这里给*pphead加了个括号，因为有符号的优先级，->的优先级高于*号{free(*pphead);*pphead = NULL;}else{	//链表有多个节点SLTNode* prev = *pphead;SLTNode* ptail = *pphead;while (ptail->next){prev = ptail;ptail = ptail->next;}free(ptail);ptail = NULL;prev->next = NULL;}}//头删
void SLTPopFront(SLTNode** pphead)
{//这里和尾删是一样的，解释在上面assert(pphead && *pphead);//在这里不能直接删除第一个节点，这样就不能根据原本第一个节点的next指针找到原本第二个节点//在头删方法中，只有一个节点和多个节点如下方法都可以实现SLTNode* next = (*pphead)->next;//这里也是->的优先级大于*号free(*pphead);*pphead = next;}//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{SLTNode* pcur = phead;while (pcur){if (pcur->data == x){return pcur;}else{pcur = pcur->next;}}return NULL;
}//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead && pos);//当pos为首节点的时候，会出现对空指针解引用的操作导致下面代码报错//若pos直接等于*pphead的时候则为头插，那么直接调用头插函数if (pos == *pphead){SLTPushFront(pphead, x);}else{assert(pphead && *pphead);assert(pos);SLTNode* newnode = SLTBuyNode(x);SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}newnode->next = pos;prev->next = newnode;}}//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)//为啥没有头结点？？？
{assert(pos);SLTNode* newnode = SLTBuyNode(x);newnode->next = pos->next;pos->next = newnode;}//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead && *pphead);assert(pos);//pos是头结点,那么可以直接调用头删代码if (pos == *pphead){SLTPopFront(pphead);//测试过只能是pphead不能是*pphead}else{SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;}}//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos)
{assert(pos&&pos->next);//这里注意pos的next也不能为空，不然怎么删除SLTNode* del = pos->next;pos->next = del->next;free(del);del = NULL;//注意不能这样写：pos->next=pos->next->next//free(pos)//pos->next=NULL;因为这样写就是把pos后的节点的下一个节点也释放掉了}//顺序表的销毁
void SListDestroy(SLTNode**pphead)
{assert(pphead && *pphead);SLTNode* pcur = *pphead;while (pcur){SLTNode* next = pcur->next;free(pcur);pcur = next;}//pcur为空*pphead = NULL;}

test.c

#include"SList.h"void test()
{//手动构造一个链表SLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode));SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode));SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode));SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode));node1->data = 1;node2->data = 2;node3->data = 3;node4->data = 4;node1->next = node2;node2->next = node3;node3->next = node4;node4->next = NULL;SLTNode* plist = node1;SLTPrint(plist);
}void test01()
{SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPrint(plist);//SLTPushFront(&plist, 1);//SLTPushFront(&plist, 2);//SLTPushFront(&plist, 3);//SLTPushFront(&plist, 4);//SLTPrint(plist);//SLTPopBack(&plist);//SLTPrint(plist);//SLTPopBack(&plist);//SLTPrint(plist);//SLTPopBack(&plist);//SLTPrint(plist);//SLTPopBack(&plist);//SLTPrint(plist);////SLTPopFront(&plist);//SLTPrint(plist);//SLTPopFront(&plist);//SLTPrint(plist);//SLTPopFront(&plist);//SLTPrint(plist);//SLTPopFront(&plist);//SLTPrint(plist);//SLTPopFront(&plist);//SLTPrint(plist);SLTNode* find = SLTFind(plist, 4);//if (find == NULL)//{//	printf("未找到！\n");//}//else//{//	printf("找到了！\n");//}//SLTInsert(&plist, find, 88);//1 88 2 3 4//SLTInsertAfter(find, 88);//1 2 88 3 4//SLTErase(&plist, find);//SLTEraseAfter(find);//1 3 4SListDestroy(&plist);SLTPrint(plist);
}struct ListNode {int val;//datastruct ListNode* next;
};
typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val) {ListNode* newHead, * newTail;newHead = newTail = NULL;ListNode* pcur = head;while (pcur){//找值不为val的结点尾插到新链表中if (pcur->val != val){//尾插if (newHead == NULL){//链表为空newHead = newTail = pcur;}else {//链表不为空newTail->next = pcur;newTail = newTail->next;}}pcur = pcur->next;}return newHead;
}void test02()
{ListNode* node1 = (ListNode*)malloc(sizeof(ListNode));ListNode* node2 = (ListNode*)malloc(sizeof(ListNode));ListNode* node3 = (ListNode*)malloc(sizeof(ListNode));ListNode* node4 = (ListNode*)malloc(sizeof(ListNode));ListNode* node5 = (ListNode*)malloc(sizeof(ListNode));ListNode* node6 = (ListNode*)malloc(sizeof(ListNode));ListNode* node7 = (ListNode*)malloc(sizeof(ListNode));node1->val = 1;node2->val = 2;node3->val = 6;node4->val = 3;node5->val = 4;node6->val = 5;node7->val = 6;node1->next = node2;node2->next = node3;node3->next = node4;node4->next = node5;node5->next = node6;node6->next = node7;node7->next = NULL;ListNode* plist = node1;removeElements(plist, 6);
}int main()
{//test();//test01();test02();return 0;
}

双链表源码

List.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef int LTDatatype;
//定义双向链表（结点）结构
typedef struct ListNode {LTDatatype data;struct ListNode* next;struct ListNode* prev;
}LTNode;//初始化
LTNode* LTInit();
//void LTDesTroy(LTNode** pphead);
//接口一致性,传一级，在函数调用结束后需要手动将实参置为NULL
void LTDesTroy(LTNode* phead);
//void LTInit(LTNode** pphead);void LTPrint(LTNode* phead);
bool LTEmpty(LTNode* phead);//尾插
//phead节点不会发生改变，参数就为一级
//phead节点发生改变，参数就为二级
void LTPushBack(LTNode* phead, LTDatatype x);
void LTPushFront(LTNode* phead, LTDatatype x);//尾删
void LTPopBack(LTNode* phead);
void LTPopFront(LTNode* phead);//在pos位置之后插⼊数据----pos位置之前插入代码基本是一样的（双向的）--课下可以实现以下在pos之前插入
void LTInsert(LTNode* pos, LTDatatype x);
void LTErase(LTNode* pos);LTNode* LTFind(LTNode* phead, LTDatatype x);

List.c

#include"List.h"LTNode* buyNode(LTDatatype x)
{LTNode* node = (LTNode*)malloc(sizeof(LTNode));node->data = x;node->next = node->prev = node;return node;
}LTNode* LTInit()
{//创建头结点//LTNode* phead = (LTNode*)malloc(sizeof(LTNode));//phead->data = -1;//phead->next = phead->prev = phead;LTNode* phead = buyNode(-1);return phead;
}
//void LTInit(LTNode** pphead)
//{
//	assert(pphead);
//	*pphead = (LTNode*)malloc(sizeof(LTNode));
//	(*pphead)->data = -1;
//	(*pphead)->next = (*pphead)->prev = *pphead;
//}//void LTDesTroy(LTNode** pphead)
//{
//	LTNode* pcur = (*pphead)->next;
//	while (pcur != *pphead)
//	{
//		LTNode* next = pcur->next;
//		free(pcur);
//		pcur = next;
//	}
//	free(*pphead);
//	*pphead = NULL;
//}
void LTDesTroy(LTNode* phead)
{LTNode* pcur = phead->next;while (pcur != phead){LTNode* next = pcur->next;free(pcur);pcur = next;}free(phead);phead = NULL;
}void LTPushBack(LTNode* phead, LTDatatype x)
{assert(phead);LTNode* newnode = buyNode(x);//phead phead->prev newnodenewnode->prev = phead->prev;newnode->next = phead;phead->prev->next = newnode;phead->prev = newnode;
}
void LTPushFront(LTNode* phead, LTDatatype x)
{assert(phead);LTNode* newnode = buyNode(x);//phead newnode phead->nextnewnode->next = phead->next;newnode->prev = phead;phead->next->prev = newnode;phead->next = newnode;
}void LTPrint(LTNode* phead)
{LTNode* pcur = phead->next;while (pcur != phead){printf("%d -> ", pcur->data);pcur = pcur->next;}printf("\n");
}bool LTEmpty(LTNode* phead)
{assert(phead);return phead->next == phead;
}//尾删
void LTPopBack(LTNode* phead)
{assert(!LTEmpty(phead));LTNode* del = phead->prev;//phead del->prev deldel->prev->next = phead;phead->prev = del->prev;free(del);del = NULL;
}
void LTPopFront(LTNode* phead)
{assert(!LTEmpty(phead));LTNode* del = phead->next;//phead del del->nextdel->next->prev = phead;phead->next = del->next;free(del);del = NULL;
}LTNode* LTFind(LTNode* phead, LTDatatype x)
{LTNode* pcur = phead->next;while (pcur != phead){if (pcur->data == x){return pcur;}pcur = pcur->next;}return NULL;
}
//在pos位置之后插⼊数据
void LTInsert(LTNode* pos, LTDatatype x)
{assert(pos);LTNode* newnode = buyNode(x);//pos newnode pos->nextnewnode->next = pos->next;newnode->prev = pos;pos->next->prev = newnode;pos->next = newnode;
}
void LTErase(LTNode* pos)
{assert(pos);//pos->prev pos pos->nextpos->prev->next = pos->next;pos->next->prev = pos->prev;free(pos);pos = NULL;
}

test.c

#include"List.h"void test()
{//LTNode* plist = NULL;//LTInit(&plist);LTNode* plist = LTInit();LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);//LTPushFront(plist, 1);//LTPushFront(plist, 2);//LTPushFront(plist, 3);//LTPushFront(plist, 4);LTPrint(plist);//4 3 2 1////LTPopBack(plist);//LTPrint(plist);//LTPopBack(plist);//LTPrint(plist);//LTPopBack(plist);//LTPrint(plist);//LTPopBack(plist);//LTPrint(plist);////LTPopFront(plist);//LTPrint(plist);//LTPopFront(plist);//LTPrint(plist);//LTPopFront(plist);//LTPrint(plist);//LTPopFront(plist);//LTPrint(plist);//LTPopFront(plist);//LTPrint(plist);//LTNode* find = LTFind(plist, 3);//if (find == NULL)//{//	printf("ûҵ\n");//}//else {//	printf("ҵˣ\n");//}//LTInsert(find, 99);//LTErase(find);//LTPrint(plist);LTDesTroy(plist);plist = NULL;
}int main()
{test();return 0;
}

总结

链表作为数据结构中的重要线性结构，其灵活的存储方式和高效的插入删除操作使其在众多场景中不可或缺。本文从链表的基本概念入手，详细解析了链表的分类方式，通过手动实现单链表的各项核心操作，深入剖析了指针操作的细节与边界条件的处理，尤其对二级指针的使用场景和原理进行了重点说明。

在此基础上，通过对比顺序表，凸显了链表在头部操作、空间利用等方面的优势，并结合 8 道经典 OJ 题，展示了链表在实际问题中的应用技巧，如快慢指针、新链表构建、环形链表特性利用等。最后提供的单链表和双链表完整源码，为实践练习提供了直接参考。

掌握链表不仅是理解更复杂数据结构（如哈希表、树、图）的基础，其指针操作逻辑也能显著提升对内存管理和程序设计的理解。希望本文能帮助读者扎实掌握链表知识，为后续数据结构学习和算法提升奠定坚实基础。