AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

【数据结构】链表其实并不难 —— 手把手带你实现单链表2

2023-02-10 101
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 【数据结构】链表其实并不难 —— 手把手带你实现单链表

4.10 在pos位置之后插入节点


我们实现了在pos位置之前插入节点之后，是不是觉得实现的很难受，这么麻烦，还要实现，这明显不合理啊。


在pos位置之后插入更加合适吧？这样我根本不需要遍历链表，我只需要让 新节点newnode 和 pos 位置的下一个节点链接，然后将pos位置的next变为我的新节点即可。

d4f58d5356e25dc004c8ada0db8872c8.png

// 在pos位置之后插入节点
void SListInsertAfter(SLTNode* pos, SLTDateType x)
{
  assert(pos); // 避免pos传参传错
  SLTNode* newnode = BuyListNode(x);
  newnode->next = pos->next;
  pos->next = newnode; 
}


4.11 删除pos位置的节点


删除pos位置的节点，需要考虑此时链表是否为空，但这只是一部分，只需要用断言处理一下就好。


而我们着重处理的为，头删和多个节点删除的情况。


如果是头删，那么删除的就是第一个节点，那么此时就需要将头变为pos->next，并且释放pos位置。头删情况也完美处理了单个节点删除时的情况。


如果是多个节点，那么就需要找到pos的前一个位置，将 pos 前一个位置(prev)的 next 链接为我当前 pos 的 next。然后释放我的pos节点。

85dd2842216702f3b08116fe2370c02a.png

// 删除pos位置的节点
void SListErase(SLTNode** pphead, SLTNode* pos)
{
  assert(pos);
  // 处理头删
  if (*pphead == pos)
  {
    *pphead = pos->next;
    free(pos);
  }
  // 处理其他情况
  else
  {
    SLTNode* prev = *pphead;
    while (prev->next != pos)
    {
      prev = prev->next;
    }
    prev->next = pos->next;
    free(pos);
    pos = NULL;
  }
}



4.12 删除pos位置之后的节点


和在pos位置之前插入一样，我们发现删除pos位置的节点，也很麻烦。因为需要找pos的前一个位置，所以这种设计也比较麻烦。


所以有时我们会删除pos位置之后的节点，这样就很方便了。


既然要删除pos位置之后的节点，那么我就需要将 pos 位置的节点和pos位置的 next 的 next 链接起来。

那么我们首先用 next 拷贝记录一下 pos->next ，然后，再将pos->next赋值为next->next，也就是pos往后的两个节点。最后释放next位置的节点即可。

注意：我pos位置的下一个节点不能是尾结点后面的节点！


9b53cc2ed74c8d93af7cd1942f62d068.png

// 删除指定pos位置后的一个节点
void SListEraseAfter(SLTNode** pphead, SLTNode* pos)
{
  assert(pos);
  assert(pos->next);// 删除的不能是尾结点后面的位置
  SLTNode* next = pos->next;// 拷贝pos的下一个节点
  pos->next = next->next;// 将pos的next变为下一个节点的next
  free(next);// 释放之前pos的下一个节点
  next = NULL;
}



4.13 打印


打印整个链表，只需要遍历链表，控制好循环的停止条件：

// 打印
void SListPrint(SLTNode* phead)
{
  SLTNode* cur = phead;
  while (cur != NULL)
  {
    printf("%d->", cur->data);
    cur = cur->next;
  }
  printf("NULL\n");
}


4.14 销毁


销毁链表，如果仅仅释放我的*pphead，可行吗？这当然不可行。


因为单链表是由不同地址的节点串联起来的。它不像数组，存储连续，只要释放起始位置。


如果我仅仅释放*pphead，那么只释放了我的第一个节点，后面的节点没释放，函数调用结束后，这些节点也找不到了。所以我们需要逐个销毁。


首先，使用 cur 拷贝头部位置。然后使用循环迭代。迭代过程中，需要记住我的 cur->next ，否则 cur 被释放后，无法找到下一个节点，然后逐个释放就可以了。


注意：当销毁后，记得把*pphead 置空，防止销毁链表后对链表误操作而导致的野指针问题。


f78b28f4d722ab35f1199262f94895be.png

// 销毁
void SListDestory(SLTNode** pphead)
{
  SLTNode* cur = *pphead;
  while (cur)
  {
    SLTNode* next = cur->next;
    free(cur);
    cur = next;
  }
  *pphead = NULL; // 置空
}



5. 完整代码

SList.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLTDateType;
typedef struct SListNode
{
  int data;
  struct SListNode* next;
}SLTNode;
// 打印
void SListPrint(SLTNode* phead);
// 尾插
void SListPushBack(SLTNode** pphead, SLTDateType x);
// 头插
void SListPushFront(SLTNode** pphead, SLTDateType x);
// 尾删
void SListPopBack(SLTNode** pphead);
// 头删
void SListPopFront(SLTNode** pphead);
// 查找
SLTNode* SListFind(SLTNode* phead, SLTDateType x);
// 在pos位置之前插入一个节点 
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x);
// 在pos位置之后插入一个节点
void SListInsertAfter(SLTNode* pos, SLTDateType x);
// 在指定位置删除一个节点
void SListErase(SLTNode** pphead, SLTNode* pos);
// 删除指定pos位置后的一个节点
void SListEraseAfter(SLTNode** pphead, SLTNode* pos);
// 销毁
void SListDestory(SLTNode** pphead);



SList.c

#define _CRT_SECURE_NO_WARNINGS 1 
#include "SList.h"
// 创建新节点
SLTNode* BuyListNode(SLTDateType x)
{
  SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
  if (newnode == NULL)
  {
    printf("malloc fail\n");
    exit(-1);// 内存申请失败，说明几乎没有空间了，直接退出程序
  }
  newnode->data = x;
  newnode->next = NULL;
  return newnode;
}
// 打印
void SListPrint(SLTNode* phead)
{
  SLTNode* cur = phead;
  while (cur != NULL)
  {
    printf("%d->", cur->data);
    cur = cur->next;
  }
  printf("NULL\n");
}
// 尾插
void SListPushBack(SLTNode** pphead, SLTDateType x)
{ // 建立新节点
  SLTNode* newnode = BuyListNode(x);
  // 链表没有节点，给新节点
  if (*pphead == NULL)
  {
    *pphead = newnode;
  }
  else
  {
    // 找到尾结点
    SLTNode* tail = *pphead;
    while (tail->next != NULL)
    {
      tail = tail->next;
    }
    // 尾结点链接新节点
    tail->next = newnode;
  } 
}
// 头插
void SListPushFront(SLTNode** pphead, SLTDateType x)
{
  assert(pphead);
  SLTNode* newnode = BuyListNode(x);
  newnode->next = *pphead;// 新节点链接之前plist的地址
  *pphead = newnode;// 头指针更改为newnode
}
// 尾删
void SListPopBack(SLTNode** pphead)
{
  // 温柔处理
  /*if (*pphead == NULL)
  {
    return;
  }*/
  // 暴力处理 一个节点
  assert(*pphead);
  if ((*pphead)->next == NULL)
  {
    free(*pphead);
    *pphead = NULL;
  }
  else// 两个及以上节点
  {
    // plan1
    SLTNode* prev = NULL;// 记录上一个节点的地址
    SLTNode* tail = *pphead;
    //while (tail->next != NULL)// 计算逻辑表达式的值为真或假决定循环是否继续执行
    while (tail->next)// 当值为空指针，被隐式转换为0，结束循环
    {
      prev = tail;
      tail = tail->next;
    }
    free(tail);// 释放尾结点空间
    tail = NULL;
    // 将前一个节点的next置空
    prev->next = NULL;
  }
  // plan2：
  //SLTNode* tail = *pphead;
  //while (tail->next->next)// 如果当前tail的next的地址访问下一个next为空，则停止
  //{
  //  tail = tail->next;// 将尾结点赋值为最后一个节点的next
  //}
  //free(tail->next);// 释放最后一个节点
  //tail->next = NULL;// 最后一个节点置空
}
// 头删
void SListPopFront(SLTNode** pphead)
{
  // 处理空链表
  assert(*pphead);  
  // 处理1个及以上节点
  SLTNode* newpphead = (*pphead)->next;
  free(*pphead);
  *pphead = newpphead;
}
// 查找
SLTNode* SListFind(SLTNode* phead, SLTDateType x)
{
  SLTNode* cur = phead;
  while (cur)
  {
    if (cur->data == x)
    {
      return cur;
    }
    else
    {
      cur = cur->next;
    }
  }
  return NULL;// 没找到
}
// 在pos位置之前插入节点
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{
  assert(pos);
  SLTNode* newnode = BuyListNode(x);
  // 头插情况特殊处理
  if (*pphead == pos)
  {
    newnode->next = *pphead;// newnode链接头
    *pphead = newnode;// 头变为newnode
  }
  // 其他位置插入
  else
  {
    // 找到pos前一个位置
    SLTNode* posPrev = *pphead;
    while (posPrev->next != pos)
    {
      posPrev = posPrev->next;
    }
    posPrev->next = newnode;// 将pos前一个位置链接到newnode
    newnode->next = pos;// newnode连接到pos
  }
}
// pos不太适合在节点前插入，适合在节点后插入
// 在pos后面 插入节点
void SListInsertAfter(SLTNode* pos, SLTDateType x)
{
  assert(pos);
  SLTNode* newnode = BuyListNode(x);
  newnode->next = pos->next;
  pos->next = newnode; 
}
// 删除pos位置的节点
void SListErase(SLTNode** pphead, SLTNode* pos)
{
  assert(pos);
  // 处理头删
  if (*pphead == pos)
  {
    *pphead = pos->next;
    free(pos);
    // 直接调用头删
    // SListPopFront(pos);
  }
  // 处理其他情况
  else
  {
    SLTNode* prev = *pphead;
    while (prev->next != pos)
    {
      prev = prev->next;
    }
    prev->next = pos->next;
    free(pos);
    pos = NULL;
  }
}
// 删除指定pos位置后的一个节点
void SListEraseAfter(SLTNode** pphead, SLTNode* pos)
{
  assert(pos);
  assert(pos->next);// 删除的不能是尾结点后面的位置
  SLTNode* next = pos->next;// 拷贝pos的下一个节点
  pos->next = next->next;// 将pos的next变为下一个节点的next
  free(next);// 释放之前pos的下一个节点
  next = NULL;
}
void SListDestory(SLTNode** pphead)
{
  SLTNode* cur = *pphead;
  while (cur)
  {
    SLTNode* next = cur->next;
    free(cur);
    cur = next;
  }
    // 这里一定要置空，放置销毁链表后被误使用
  *pphead = NULL;
}

test.c

#define _CRT_SECURE_NO_WARNINGS 1 
#include "SList.h"
// 测试尾插、带节点的头插
void TestList1()
{
  SLTNode* plist = NULL;
  SListPushBack(&plist, 1);
  SListPushBack(&plist, 2);
  SListPushBack(&plist, 3);
  SListPushBack(&plist, 4);
  SListPushBack(&plist, 5);
  SListPrint(plist);
  SListPushFront(&plist, 1);
  SListPushFront(&plist, 2);
  SListPushFront(&plist, 3);
  SListPushFront(&plist, 4);
  SListPushFront(&plist, 5);
  SListPrint(plist);
}
// 测试头插、尾删
void TestList2()
{
  SLTNode* plist = NULL;
  SListPushFront(&plist, 1);
  SListPushFront(&plist, 2);
  SListPushFront(&plist, 3);
  SListPushFront(&plist, 4);
  SListPushFront(&plist, 5);
  SListPrint(plist);
  SListPopBack(&plist);
  SListPopBack(&plist);
  SListPopBack(&plist);
  SListPopBack(&plist);
  SListPopBack(&plist);
  //SListPopBack(&plist);
  SListPrint(plist);
}
// 测试头删
void TestList3()
{
  SLTNode* plist = NULL;
  SListPushFront(&plist, 1);
  SListPushFront(&plist, 2);
  SListPushFront(&plist, 3);
  SListPushFront(&plist, 4);
  SListPushFront(&plist, 5);
  SListPrint(plist);
  SListPopFront(&plist);
  SListPrint(plist);
  SListPopFront(&plist);
  SListPrint(plist);
  SListPopFront(&plist);
  SListPrint(plist);
  SListPopFront(&plist);
  SListPrint(plist);
  SListPopFront(&plist);
  SListPrint(plist);
}
//void TestList4()
//{
//  SLTNode* plist = NULL;
//
//  SListPushFront(&plist, 1);
//  SListPushFront(&plist, 2);
//  SListPushFront(&plist, 3);
//  SListPushFront(&plist, 2);
//  SListPushFront(&plist, 5);
//
//  SLTNode* pos = SListFind(plist, 2);
//  int i = 1;
//  while (pos)
//  {
//    printf("第%d个pos节点：%p->%d\n", i++, pos, pos->data); 
//    pos = SListFind(pos->next, 2);
//  }
//
//  // 修改 3->30
//  pos = SListFind(plist, 3);
//  if (pos)
//  {
//    pos->data = 30;
//  }
//  SListPrint(plist);
//}
void TestList5()
{
  SLTNode* plist = NULL;
  SListPushFront(&plist, 1);
  SListPushFront(&plist, 2);
  SListPushFront(&plist, 3);
  SListPushFront(&plist, 2);
  SListPushFront(&plist, 5);
  // 3前面插入一个30
  SLTNode* pos = SListFind(plist, 3);
  if (pos)
  {
    SListInsert(&plist, pos, 30);
  }
  SListPrint(plist);
  // 5前面插入一个10
  pos = SListFind(plist, 5);
  if (pos)
  {
    SListInsert(&plist, pos, 10);
  }
  SListPrint(plist);
}
int main()
{
  //TestList1();
  //TestList2();
  //TestList3();
  TestList5();
  return 0;
}



到这里本篇博客就到此结束了，仔细阅读这篇文章，你会发现，链表其实也没有那么难！


但是光看懂了还不够，链表是一个面试常考点，所以是十分重要的！于是在接下来几期，anduin 会带着大家一起刷链表的OJ题，多写多练，手撕链表~


更多精彩内容敬请期待~


如果觉得anduin写的还不错的话，还请一键三连！如有错误，还请指正！


我是anduin，一名C语言初学者，我们下期见！



文章标签：
C语言
存储
关键词：
数据结构单链表
数据结构链表
链表数据结构
链表单链表
链表单链
安度因123
目录
相关文章
2的n次方_
|
14天前
|
存储 Java 索引
【数据结构】链表从实现到应用，保姆级攻略
本文详细介绍了链表这一重要数据结构。链表与数组不同，其元素在内存中非连续分布，通过指针连接。Java中链表常用于需动态添加或删除元素的场景。文章首先解释了单向链表的基本概念，包括节点定义及各种操作如插入、删除等的实现方法。随后介绍了双向链表，说明了其拥有前后两个指针的特点，并展示了相关操作的代码实现。最后，对比了ArrayList与LinkedList的不同之处，包括它们底层实现、时间复杂度以及适用场景等方面。
2的n次方_
31 10
【数据结构】链表从实现到应用，保姆级攻略
小徐在进步
|
10天前
|
存储 算法 C语言
数据结构基础详解(C语言):单链表_定义_初始化_插入_删除_查找_建立操作_纯c语言代码注释讲解
本文详细介绍了单链表的理论知识，涵盖单链表的定义、优点与缺点，并通过示例代码讲解了单链表的初始化、插入、删除、查找等核心操作。文中还具体分析了按位序插入、指定节点前后插入、按位序删除及按值查找等算法实现，并提供了尾插法和头插法建立单链表的方法，帮助读者深入理解单链表的基本原理与应用技巧。
小徐在进步
32 6
小徐在进步
|
10天前
|
存储 算法 C语言
C语言手撕实战代码_循环单链表和循环双链表
本文档详细介绍了用C语言实现循环单链表和循环双链表的相关算法。包括循环单链表的建立、逆转、左移、拆分及合并等操作；以及双链表的建立、遍历、排序和循环双链表的重组。通过具体示例和代码片段，展示了每种算法的实现思路与步骤，帮助读者深入理解并掌握这些数据结构的基本操作方法。
小徐在进步
14 2
东方睿赢
|
30天前
|
存储 Java 程序员
"揭秘HashMap底层实现：从数组到链表，再到红黑树，掌握高效数据结构的秘密武器！"
【8月更文挑战第21天】HashMap是Java中重要的数据结构，采用数组+链表/红黑树实现，确保高效查询与更新。构造方法初始化数组，默认容量16，负载因子0.75触发扩容。`put`操作通过计算`hashCode`定位元素，利用链表或红黑树处理冲突。`get`和`remove`操作类似地定位并返回或移除元素。JDK 1.8优化了链表转红黑树机制，提升性能。理解这些原理能帮助我们更高效地应用HashMap。
东方睿赢
30 0
aliyun6365824167
|
1月前
|
算法 索引
【初阶数据结构篇】单链表算法题进阶
深拷贝应该正好由 n 个全新节点组成，其中每个新节点的值都设为其对应的原节点的值。
aliyun6365824167
14 0
aliyun6365824167
|
1月前
|
存储 算法
【初阶数据结构篇】顺序表和链表算法题
此题可以先找到中间节点，然后把后半部分逆置，最近前后两部分一一比对，如果节点的值全部相同，则即为回文。
aliyun6365824167
16 0
aliyun6365824167
|
1月前
|
存储 测试技术
【初阶数据结构篇】双向链表的实现（赋源码）
因为头结点的存在，plist指针始终指向头结点，不会改变。
aliyun6365824167
20 0
aliyun6365824167
|
1月前
|
存储 测试技术
【初阶数据结构篇】单链表的实现（附源码）
在尾插/尾删中，都需要依据链表是否为空/链表是否多于一个节点来分情况讨论，目的是避免对空指针进行解引用造成的错误。
aliyun6365824167
18 0
国中之林
|
1月前
|
算法
【数据结构与算法】共享双向链表
【数据结构与算法】共享双向链表
国中之林
11 0
国中之林
|
1月前
|
算法
【数据结构与算法】双向链表
【数据结构与算法】双向链表
国中之林
10 0