链表的相关概念链表在逻辑顺序上是连续的而在物理存储空间上不一定连续是一种线性的数据结构由一系列节点组成每一个节点包含两部分一个是数据域存储实际的数据另一个是指针域存储下一个节点的地址。常见类型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 newnodevoid 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)-nextNULL) { 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因为这是通过内存地址直接进行操作会对原链表造成影响如果是直接freepcur在打印最后一个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; }
链表的实现（单链表、双链表、环形表）【上】超详细！！
链表的相关概念链表在逻辑顺序上是连续的而在物理存储空间上不一定连续是一种线性的数据结构由一系列节点组成每一个节点包含两部分一个是数据域存储实际的数据另一个是指针域存储下一个节点的地址。常见类型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 newnodevoid 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)-nextNULL) { 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因为这是通过内存地址直接进行操作会对原链表造成影响如果是直接freepcur在打印最后一个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; }
