链表的实现（单链表、双链表、环形表）【上】超详细！！

链表的相关概念

链表在逻辑顺序上是连续的，而在物理存储空间上不一定连续，是一种线性的数据结构，由一系列节点组成，每一个节点包含两部分，一个是数据域：存储实际的数据，另一个是指针域：存储下一个节点的地址。

常见类型：

1.单链表：每个节点指向下一个节点。

2.双链表：每个节点同时指向前驱与后继。

3.循环链表：尾节点指回头节点，形成环。

适用场景一般为：1.频繁插入/删除数据；2.不需要随机访问元素（在内存空间不连续，查找元素需要从头开始，逐个遍历，运行效率低）；实现栈、队列、图等更复杂的数据结构。

其与顺序表的区别在于：1.存储结构上顺序表为连续内存，链表分散内存；2.空间分配上顺序表预分配，可能会有空间的浪费，链表内存按需动态申请；3.查找上顺序表内存连续按值查找，支持随机访问，链表内存不连续只能通过指针接力，挨个查找，效率较低。4.在插入删除当中，顺序表需要整体移动多个元素，造成程序性能的消耗，而链表效率高，只需要修改指针；5.在缓存当中，顺序表连续内存，命中率高，缓存友好性号，链表内存分散，缓存不友好。

单链表的实现

1.定义单链表结构：

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

在定义完单链表结构后，我们创建一个函数CreteNode用来创建链表节点以便我们在vs及时观察调试：

void CreateNode() { SListNode* node1 = (SListNode*)malloc(sizeof(SListNode)); node1->data = 1; SListNode* node2 = (SListNode*)malloc(sizeof(SListNode)); node2->data = 2; SListNode* node3 = (SListNode*)malloc(sizeof(SListNode)); node3->data = 3; SListNode* node4 = (SListNode*)malloc(sizeof(SListNode)); node4->data = 4; node1->next = node2; node2->next = node3; node3->next = node4; node4->next = NULL; }

在链表中没有增容的概念，需要插入数据就直接申请一块新的空间，动态申请的空间指针类型为void*，所以需要强制类型转换成相应的指针类型，接着调试监视node1,观察单链表是否创建成功：

由图可知，链表创建成功。创建成功后，试着用一个函数将其打印出来：

void SLprint(phead) { SListNode* pcur = phead; while (pcur) { printf("%d->", pcur->data); pcur = pcur->next; } printf("NULL\n"); }

刚刚做的测试只是为了验证定义链表结构是否正确，因此创建链表调试观察其是否符合预期，一般来说创建链表并不像CreatNode函数这样创建，而是插入到空链表当中。

2.链表的头插以及尾插：

在进行插入操作，增加新的数据都需要开辟新的空间，将这一步单独抽离开来，重新定义一个函数单独来实现SListNode*SLBuyNode(SLDataType x);

SListNode*SLBuyNode(SLDataType x) { SListNode* newnode = (SListNode*)malloc(sizeof(SListNode)); newnode->data = x; newnode->next = NULL; return newnode; }

在写完SLBuyNode函数后进行尾插操作：

void SLPushBack(SListNode** pphead,SLDataType x) { assert(pphead); SListNode* newnode = SLBuyNode(x); SListNode* pcur = *pphead; while (pcur->next) { pcur = pcur->next; } pcur->next = newnode; }

之后在test函数里面进行测试：

函数放回值为0，说明程序正常运行，打印出插入后的链表。但这里有个问题，我们是在已知链表的基础上进行操作，那假如链表为NULL呢，这种情况就应该进行特殊处理：

void SLPushBack(SListNode** pphead,SLDataType x) { assert(pphead); SListNode* newnode = SLBuyNode(x); if (*pphead == NULL) { *pphead = newnode; } else { SListNode* pcur = *pphead; while (pcur->next) { pcur = pcur->next; } pcur->next = newnode; } }

用一个函数调试，测试，运行：

void test01() { SListNode* node = NULL; SLPushBack(&node,1); SLPushBack(&node,2); SLPushBack(&node,3); SLPushBack(&node,4); SLPushBack(&node,5); SLprint(node); } int main() { //SListNode* phead = CreateNode(); test01(); return 0; }

函数返回值为0，程序正常运行。

接下来为头插：对于头插操作，我们依旧需要调用SLBuyNode函数，申请一块新的空间，将新申请节点的next指针指向我原来的节点*pphead，将新申请的空间地址作为我单链表的新节点，即*pphead = newnode；

void SLPushFront(SListNode** pphead, SLDataType x) { assert(pphead); SListNode* newnode = SLBuyNode(x); if (*pphead == NULL) { *pphead = newnode; } else { newnode->next = *pphead; *pphead = newnode; } }

这里需要注意的是1.newnode->next = *pphead 2.*pphead = newnode，这里的顺序是不能进行颠倒的，因为一旦先*pphead = newnode，此时在newnode->next = *pphead，*pphead指向的就不是原来的头节点了，而是申请新节点地址。

3.单链表的头删和尾删：

对于尾删SLPopBack，我们需要注意的是保存最后一个节点的上一个节点位置，free释放掉最后一个节点以及不能对空链表进行尾删操作：

//尾删 void SLPopBack(SListNode** pphead) { assert(pphead && *pphead); SListNode* pcur = *pphead; SListNode* ptail = NULL; while (pcur->next->next) { pcur = pcur->next; ptail = pcur->next; } free(ptail); ptail = NULL; pcur->next = NULL; }

pcur->next->next是指pcur下一个节点的下一个节点，当pcur->next->next指针为NULL时，也就意味这pcur走到了最后一个节点的上一个位置，除此之外，我们不能对空链表执行删除操作，所以代码如下：

//尾删 void SLPopBack(SListNode** pphead) { assert(pphead && *pphead); if ((*pphead)->next==NULL) { free(*pphead); *pphead = NULL; } else { SListNode* pcur = *pphead; SListNode* prev = NULL; while (pcur->next) { prev = pcur; pcur = pcur->next; } prev->next = NULL; free(pcur); pcur = NULL; } }

测试、运行：

程序运行成功，尾删执行完成。在尾删操作当中，如果删到最后一个元素时，此时没有前一个节点prev了，如果我们对prev解引用，属于非法访问了，所以我们需要对只有一个节点的情况另行判断，只剩一个节点相当于头删操作，直接释放这个空间，但我们需要用*pphead，因为这是通过内存地址直接进行操作，会对原链表造成影响，如果是直接free（pcur），在打印最后一个NULL时，会出现随机的垃圾值，这是因为pcur只是一个临时变量，出了函数周期，不会对链表造成影响，那为什么else分支里面的prev也是临时变量会对链表造成影响呢？因为prev->next = NULL;操作是通过地址去操作的，并且将节点置为NULL后，逻辑上切断了该节点的连续性，所以else分支里面的操作是可以影响链表。

如果我们尾删完了所有数据此时链表为空，依旧执行删除操作呢？代码会因为assert断言终止程序。

对于头删而言，逻辑代码相对简洁，主要是需提前保存第一个节点的下一个节点，然后再去释放第一个节点空间：

void SLPopFront(SListNode** pphead) { assert(pphead && *pphead); SListNode* next = (*pphead)->next; free(*pphead); *pphead = next; }

4.查找：

SListNode* SLFind(SListNode*phead, SLDataType x) { SListNode* pcur = phead; while (pcur) { if (pcur->data == x) { printf("找到了\n"); return pcur; } pcur = pcur->next; } printf("NULL\n"); }

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

在指定位置之前插入数据需要找到该节点的前一个节点，然后改变节点指向，另外一个需要注意的情况可能链表只有一个数据，此时需要找的pos节点恰好为该节点，即头插，此时调用头插函数即可：

void SLInsert(SListNode** pphead,SListNode* pos,SLDataType x) { assert(pphead&&*pphead); //SListNode* pcur = *pphead; assert(pos); if (*pphead == pos) { SLPushFront(pphead, x); } else { SListNode* prev = *pphead; SListNode* newnode = SLBuyNode(x); while (prev->next != pos) { prev = prev->next; } newnode->next = pos; prev->next = newnode; } }

对于在test.c测试文件中，我们需要调用查找函数，利用函数的返回值，如果查找的数不存在，返回NULL，此时pos为NULL，程序会终止运行：

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

在指定位置之后插入数据传参不需要头节点，因为有pos就可以找得到下一个节点，不过再写代码的时候需要特别注意1.newnode->next = pos->next;2.pos->next = newnode;顺序不能动，因为一旦代码先运行2，那么pos->next指针就变了，不是原来的节点了。

//在指定位置之后插入数据 void SLInsertAfter(SListNode* pos, SLDataType x) { assert(pos); SListNode* newnode = SLBuyNode(x); newnode->next = pos->next; pos->next = newnode; }

调试、运行:

7.删除指定位置节点：

在这一步当中，对于非头尾节点的节点来说，受到影响的为前一个节点以及后一个节点，所以我们需要遍历找到这个要删除的节点，然后让上一个节点prev的下一个节点指向newnode的下一个节点，然后free掉我们要删除的节点newnode，但我们放到test测试文件里面进行测试时，发现尾节点也能正常删除，但头节点却不适用，这是因为头节点没有前置节点prev了，这时候我们需要另外判断这种情况，当需要删除的节点恰好为头节点时，此时为头删，直接调用头删函数即可。

//删除指定位置的节点 void SLErase(SListNode** pphead,SLDataType x) { SListNode* newnode = SLFind(*pphead,x); assert(pphead && newnode); SListNode* prev = *pphead; if (prev == newnode) { SLPopFront(pphead); } else { while (prev->next != newnode) { prev = prev->next; } prev->next = newnode->next; free(newnode); newnode = NULL; } }

测试、运行：

8.删除指定位置之后的节点：

在这里的逻辑实现相对简单，不过需要注意的是删除指定位置的下一个节点不能为NULL；

//删除指定位置之后的节点 void SLEraseAfter(SListNode** pos) { assert(pos && *pos); assert((*pos)->next); SListNode* del = (*pos)->next; (*pos)->next = (*pos)->next->next; free(del); del = NULL; }