【数据结构与算法】深入理解单链表-阿里云开发者社区

一、单链表的基本概念

单链表的简介

单链表是一种基本的线性数据结构，它通过链式存储方式而非连续的内存位置来存储元素。（逻辑上连续，物理上不一定连续）在单链表中，每个元素（或称为节点）包含两部分：数据域和指针域。

数据域用于存储实际的数据，而指针域则存储指向下一个节点的地址。

这样，每个节点都链接到列表中的下一个节点，形成一个链条。

本篇文章要介绍的是无头结点，单向，不循环链表，即通常我们所熟知单链表，以下如无特殊说明，均代表此含义。

单链表的特点

动态大小：链表的长度可以在运行时改变，便于灵活地添加和删除元素。

不需要连续空间：与数组不同，链表的节点在内存中不必相邻，这使得它在内存管理上更为灵活。

插入和删除操作高效：在已知节点位置的情况下，插入和删除操作可以仅需常数时间完成，因为只需调整相邻节点的指针即可。

访问速度：相比于随机访问的数组，单链表的元素访问效率较低，因为需要从头节点开始逐个遍历直到目标节点。

二、预备知识

C语言的基本数据类型和变量
掌握指针的概念和用法
掌握动态内存分配（malloc 和 free）

三、单链表的基本结构

在单链表中，每个元素（或称为节点）包含两部分：数据域和指针域。

数据域用于存储实际的数据（可以是任意类型的数据），而指针域则存储指向下一个节点的地址。

下面是一个使用结构体定义单链表节点的示例：

typedef int SLTDataType;//类型重定义
typedef struct SListNode
{
  SLTDataType data;//数据
  struct SListNode* next;//指针
}SLTNode;

注意：

例子中int是要存储的数据类型，但为了方便后期修改存储类型，这里先对int重命名
为了方便使用，简化节点的名字为SLTNode（但要注意在结构体中创建指针时，不可以使用重定义后的结构体名称，因为此时结构体还未定义）

四、单链表的基本操作

注意：

出于文章篇幅所限，未展示每个方法的独立测试结果，建议读者在实现单链表时，每写好一个方法，都单独测试一下

本篇文章介绍的是无头结点的链表，但为了方便表达，会将第一个节点称为首节点，意为第一个存放数据的有效节点

1.链表打印

void SLTPrint(SLTNode* phead)//链表打印
{
  SLTNode* pcur = phead;
  while (pcur)//pcur!=NULL
  {
    printf("%d->", pcur->data);//打印该节点数据
    pcur = pcur->next;//指针指向下一个节点
  }
  printf("NULL\n");
}

该方法的思路是创建一个临时指针变量接收实参传递的链表首节点指针

然后进入循环，当临时指针pcur不为空时，打印该节点的数据，然后指向下一个节点

当传递来的实参为NULL时，不会进入while循环，而是直接打印NULL

2.申请节点

SLTNode* NewNode(SLTDataType x)//申请节点
{
  SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
  if (newnode == NULL)//注意这里不要写成一个=
  {
    perror("newnode");
    exit(1);//如果申请节点失败，异常退出程序
  }
  newnode->data = x; //数据初始化
  newnode->next = NULL;//指针初始化
  return newnode;//返回新申请节点的地址
}

该方法的任务是：

动态开辟一块节点大小的空间，判断是否成功

然后分别对数据和指针部分初始化

3.头插

void SLTPushFront(SLTNode** pphead, SLTDataType x)//头插
{
  assert(pphead);//二级指针不能为空，否则解引用就会报错
  SLTNode* newnode = NewNode(x);
  newnode->next = *pphead;//新节点next指针指向原来的首节点
  *pphead = newnode;//新节点成为首节点
}

该方法主要任务：

根据传递的数据部分，申请新节点

将新节点next指针指向原来的首节点

新节点成为首节点

需要注意的是：

因为传递来的实参需要被改变（即首节点指向的节点需要被改变），所以此处需要传址调用，实参传递首节点的地址，形参使用二级指针接收

因为要对二级指针解引用来修改实参，所以实参传递的指针不能为空，否则解引用就会报错

这段代码对于链表空或非空，都可以正确的处理

4.尾插

void SLTPushBack(SLTNode** pphead, SLTDataType x)//尾插
{
  assert(pphead);//二级指针不能为空，否则解引用就会报错
  SLTNode* newnode = NewNode(x);
  if (*pphead == NULL)
  {
    *pphead = newnode;//如果链表为空，新节点即为第一个节点
  }
  else
  {
    SLTNode* pcur = *pphead;
    while (pcur->next)//找到链表的尾节点
    {
      pcur = pcur->next;
    }
    pcur->next = newnode;//如果不对空链表分别处理
  }           //此处就会对空指针解引用
}

该方法完成的任务：

对二级指针判空

申请新节点

对于空链表和非空链表分开处理

对于空链表，新节点成为首节点

对于非空链表，要先找到尾节点，修改尾节点的next指针指向新节点

5.头删

void SLTPopFront(SLTNode** pphead)//头删
{
  assert(pphead && *pphead);//二级指针不能为空，链表不能为空
  SLTNode* next = (*pphead)->next;//存储第二个节点
  free(*pphead);//删除第一个节点
  *pphead = next;//链表指向第二个节点
}

该方法完成的任务：

判空

先存储下第二个节点，防止删除第一个节点之后找不到第二个节点

删除第一个节点

链表头指针指向第二个节点

（这段代码对于链表只有一个节点的情况也可以正常处理）

6.尾删

void SLTPopBack(SLTNode** pphead)//尾删
{
  assert(pphead && *pphead);//二级指针不能为空，链表不能为空
  if ((*pphead)->next == NULL)//处理链表只有一个节点的情况
  {
    free(*pphead);
    *pphead = NULL;
  }
  else//处理正常情况
  {
    SLTNode* pcur = *pphead;//找到指针的最后一个节点
    SLTNode* prev = *pphead;//找到指针的倒数第二个节点
    while (pcur->next)
    {
      prev = pcur;
      pcur = pcur->next;
    }
    free(pcur);
    pcur = NULL;
    prev->next = NULL;//如果不做特殊处理，此处就会对空指针解引用
  }
}

该方法完成的任务：

判空

对于链表只有一个节点或多个节点的情况分别处理

链表只有一个节点——先删除，再置空

链表有多个节点——先找到链表的最后一个和倒数第二个节点，最后一个节点删除和置空，倒数第二个节点的next指向NULL

7.查找节点

SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
  SLTNode* pcur = phead;
  while (pcur)
  {
    if (pcur->data == x)
      return pcur;//如果找到，返回节点地址
  }
  return NULL;//对未找到的情况和链表为空的情况都可以处理
}

该方法完成的任务：

创建一个临时指针变量接收实参传递的链表首节点指针

while循环，当临时指针pcur不为空时，判断该节点数据是否等于要查找的数据，相等直接返回节点地址，否则指针指向下一个节点

如果while循环中没有return，说明未找到指定数据，或链表为空，此时返回一个空指针

8.指定位置之前插入

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
  assert(pphead && *pphead);//二级指针不能为空，链表不能为空
  assert(pos);//指定位置必须存在
  SLTNode* newnode = NewNode(x);
  if (*pphead == pos)//如果要插入到第一个节点之前
  {
    SLTPushFront(pphead, x);//可以直接调用头插
  }
  else
  {
    SLTNode* prev = *pphead;
    while (prev->next != pos)//需要先找到pos的前一个节点
    {                        //如果不分别处理，最后就会对空指针解引用
      prev = prev->next;
    }
    newnode->next = pos;//新节点指向pos
    prev->next = newnode;//原pos的前一个节点指向新节点
  }
 
}

该方法完成的任务：

判空

申请节点

对于指定的位置分情况处理

如果指定的位置就是第一个节点，那么直接调用头插

对于其他情况，需要先找到pos的前一个节点。然后将三个节点链接在一起：原pos的前一个节点-> 新节点->pos节点

9.指定位置之后插入

void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
  assert(pos);//pos节点必须存在
  SLTNode* newnode = NewNode(x);
  newnode->next = pos->next;//新节点的next指针指向原pos的下一个节点
  pos->next = newnode;//pos的next指针指向新节点
}

该方法完成的任务：

判空

申请节点

新节点的next指针指向原pos的下一个节点

pos的next指针指向新节点（注意这两条语句不能颠倒，否则pos之后的节点就会丢失）

10.删除给定节点

void SLTErase(SLTNode** pphead, SLTNode* pos)
{
  assert(pphead && *pphead);//二级指针不能为空，链表不能为空
  assert(pos);//指定位置必须存在
  if (pos == *pphead)//如果删除的是首节点，或链表只有一个节点
  {
    SLTPopFront(pphead);
  }
  else//链表有多个节点，且删除的不是首节点
  {
    SLTNode* prev = *pphead;
    while (prev->next != pos)//如果不分开处理，这里就可能对空指针解引用
    {
      prev = prev->next;
    }
    prev->next = pos->next;//找到前一个指针，并将其next指针指向pos的next指针所指节点
    free(pos);
    pos = NULL;
  }
}

该方法完成的任务：

判空

对两种情况分别处理

如果删除的是首节点，或链表只有一个节点，直接执行头删

如果链表有多个节点，且删除的不是首节点。那么先找到pos的前一个指针，并将其next指针指向pos的next指针所指节点

11.删除给定节点之后的节点

void SLTEraseAfter(SLTNode* pos)
{
  assert(pos && pos->next);//pos节点必须存在且pos之后必须存在节点
  SLTNode* del = pos->next;//预先存储要删除的节点，防止修改指针之后找不到要删除的节点
  pos->next = del->next;
  free(del);
  del = NULL;
}

该方法完成的任务：

判空

预先存储要删除的节点，防止修改指针之后找不到要删除的节点

pos的next指针指向要删除节点的next指针所指向的节点（或NULL）

删除pos之后的节点并置空

12.链表销毁

void SListDesTroy(SLTNode** pphead)
{
  assert(pphead && *pphead);//二级指针不能为空，链表不能为空
  SLTNode* pcur = *pphead;
  while (pcur)
  {
    SLTNode* next = pcur->next;//需要预先存储当前要删除节点的下一个节点
    free(pcur);         //否则就找不到下一个节点了
    pcur = next;
  }
  *pphead = NULL;//删除完所有节点之后，链表置空
}

该方法完成的任务：

判空

创建一个临时指针变量接收实参传递的链表首节点指针

while循环，当临时指针pcur不为空时，存储下一个节点的地址，并删除该节点，pcur指向下一个节点

删除完所有节点之后，不要忘记给链表指针置为NULL，预防野指针

五、示例程序

SLinkList.h 单链表结构定义及函数声明头文件

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int SLTDataType;//类型重定义
typedef struct SListNode
{
  SLTDataType data;//数据
  struct SListNode* next;//指针
}SLTNode;
 
 
void SLTPrint(SLTNode* phead);//链表打印
 
SLTNode* NewNode(SLTDataType x);//申请节点
 
//头部插入删除/尾部插入删除
void SLTPushBack(SLTNode** pphead, SLTDataType x);
void SLTPushFront(SLTNode** pphead, SLTDataType x);
void SLTPopBack(SLTNode** pphead);
void SLTPopFront(SLTNode** pphead);
 
//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos);
//销毁链表
void SListDesTroy(SLTNode** pphead);

SLinkList.c 单链表方法实现源文件

#include"SLinkList.h"
void SLTPrint(SLTNode* phead)//链表打印
{
  SLTNode* pcur = phead;
  while (pcur)//pcur!=NULL
  {
    printf("%d->", pcur->data);//打印该节点数据
    pcur = pcur->next;//指针指向下一个节点
  }
  printf("NULL\n");
}
 
SLTNode* NewNode(SLTDataType x)//申请节点
{
  SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
  if (newnode == NULL)//注意这里不要写成一个=
  {
    perror("newnode");
    exit(1);//如果申请节点失败，异常退出程序
  }
  newnode->data = x; //数据初始化
  newnode->next = NULL;//指针初始化
  return newnode;//返回新申请节点的地址
} 
 
//头部插入删除/尾部插入删除
void SLTPushBack(SLTNode** pphead, SLTDataType x)//尾插
{
  assert(pphead);//二级指针不能为空，否则解引用就会报错
  SLTNode* newnode = NewNode(x);
  if (*pphead == NULL)
  {
    *pphead = newnode;//如果链表为空，新节点即为第一个节点
  }
  else
  {
    SLTNode* pcur = *pphead;
    while (pcur)//找到链表的尾节点
    {
      pcur = pcur->next;
    }
    pcur->next = newnode;//如果不对空链表分别处理
  }           //此处就会对空指针解引用
}
void SLTPushFront(SLTNode** pphead, SLTDataType x)//头插
{
  assert(pphead);//二级指针不能为空，否则解引用就会报错
  SLTNode* newnode = NewNode(x);
  newnode->next = *pphead;//新节点next指针指向原来的首节点
  *pphead = newnode;//新节点成为首节点
}
 
void SLTPopBack(SLTNode** pphead)//尾删
{
  assert(pphead && *pphead);//二级指针不能为空，链表不能为空
  if ((*pphead)->next == NULL)//处理链表只有一个节点的情况
  {
    free(*pphead);
    *pphead = NULL;
  }
  else//处理正常情况
  {
    SLTNode* pcur = *pphead;//找到指针的最后一个节点
    SLTNode* prev = *pphead;//找到指针的倒数第二个节点
    while (pcur->next != NULL)
    {
      prev = pcur;
      pcur = pcur->next;
    }
    free(pcur);
    pcur = NULL;
    prev->next = NULL;//如果不做特殊处理，此处就会对空指针解引用
  }
}
 
void SLTPopFront(SLTNode** pphead)//头删
{
  assert(pphead && *pphead);//二级指针不能为空，链表不能为空
  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;//如果找到，返回节点地址
  }
  return NULL;//对未找到的情况和链表为空的情况都可以处理
}
 
//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
  assert(pphead && *pphead);//二级指针不能为空，链表不能为空
  assert(pos);//指定位置必须存在
  SLTNode* newnode = NewNode(x);
  if (*pphead == pos)//如果要插入到第一个节点之前
  {
    SLTPushFront(pphead, x);//可以直接调用头插
  }
  else
  {
    SLTNode* prev = *pphead;
    while (prev->next != pos)//需要先找到pos的前一个节点
    {           //如果不分别处理，最后就会对空指针解引用
      prev = prev->next;
    }
    newnode->next = pos;//新节点指向pos
    prev->next = newnode;//原pos的前一个节点指向新节点
  }
 
}
 
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
  assert(pos);//pos节点必须存在
  SLTNode* newnode = NewNode(x);
  newnode->next = pos->next;//新节点的next指针指向原pos的下一个节点
  pos->next = newnode;//pos的next指针指向新节点
}
 
//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
  assert(pphead && *pphead);//二级指针不能为空，链表不能为空
  assert(pos);//指定位置必须存在
  if (pos == *pphead)//如果删除的是首节点，或链表只有一个节点
  {
    SLTPopFront(pphead);
  }
  else//链表有多个节点，且删除的不是首节点
  {
    SLTNode* prev = *pphead;
    while (prev->next != pos)//如果不分开处理，这里就可能对空指针解引用
    {
      prev = prev->next;
    }
    prev->next = pos->next;//找到前一个指针，并将其next指针指向pos的next指针所指节点
    free(pos);
    pos = NULL;
  }
}
 
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos)
{
  assert(pos && pos->next);//pos节点必须存在且pos之后必须存在节点
  SLTNode* del = pos->next;//预先存储要删除的节点，防止修改指针之后找不到要删除的节点
  pos->next = del->next;
  free(del);
  del = NULL;
}
 
//销毁链表
void SListDesTroy(SLTNode** pphead)
{
  assert(pphead && *pphead);//二级指针不能为空，链表不能为空
  SLTNode* pcur = *pphead;
  while (pcur)
  {
    SLTNode* next = pcur->next;//需要预先存储当前要删除节点的下一个节点
    free(pcur);         //否则就找不到下一个节点了
    pcur = next;
  }
  *pphead = NULL;//删除完所有节点之后，链表置空
}

test.c 测试文件

#include"SLinkList.h"
 
void test1()
{
  SLTNode* plist = NULL;
  SLTPrint(plist);//打印初始链表
  SLTPushBack(&plist, 1);//尾插
  SLTPrint(plist);//打印链表
  SLTPushFront(&plist, 2);//头插
  SLTPushFront(&plist, 3);//头插
  SLTPrint(plist);//打印链表
  SLTPopBack(&plist);//尾删
  SLTPrint(plist);//打印链表
  SLTPopFront(&plist);//头删
  SLTPrint(plist);//打印链表
  printf("\n");
  SLTNode* find=SLTFind(plist, 2);//查找
  SLTInsert(&plist, find, 5);//指定位置之前插入数据
  SLTPrint(plist);//打印链表
  SLTInsertAfter(find, 6);//指定位置之后插入数据
  SLTPrint(plist);//打印链表
  SLTEraseAfter(find);//删除指定之后的节点
  SLTPrint(plist);//打印链表
  SLTErase(&plist, find);//删除指定节点
  SLTPrint(plist);//打印链表
  SListDesTroy(&plist);//销毁链表
  SLTPrint(plist);//打印链表
}
 
int main()
{
  test1();
  return 0;
}

测试结果

六、实现单链表的常见问题

内存泄漏：

当创建新节点并为其分配内存后，如果在某个时候不再需要该节点，但没有正确地释放其占用的内存，就会发生内存泄漏。这可能会导致程序在长时间运行后占用越来越多的内存，甚至耗尽系统资源。

野指针：

如果一个指针被赋予了一个非法的内存地址（例如，一个已经被释放的内存地址），那么这个指针就被称为野指针。尝试访问或操作野指针指向的内存可能导致程序崩溃或产生不可预测的行为。
在单链表中，当删除一个节点时，必须确保没有其他的指针（例如，遍历链表的指针）仍然指向该节点，否则这些指针就可能变成野指针。

空指针解引用：

在C语言中，解引用一个空指针（即值为NULL的指针）是未定义的行为，通常会导致程序崩溃。在单链表操作中，必须始终检查指针是否为空，以避免空指针解引用。

链表断裂：

在插入或删除节点时，如果操作不当，可能会导致链表的断裂，即链表中某些节点失去了与前后节点的连接。这通常是由于没有正确更新指针所导致的。

链表遍历错误：

在遍历链表时，如果没有正确设置遍历的起始和结束条件，就可能导致遍历错误。例如，如果遍历的起始节点不是链表的头节点，或者没有正确地检查当前节点是否为NULL就尝试访问其next指针，就可能导致问题。

函数参数传递不当：

使用一级指针而非二级指针：在需要修改链表头指针的函数中，如果没有使用二级指针，就无法在函数内部正确修改头指针。

【数据结构与算法】深入理解单链表

一、单链表的基本概念

单链表的简介

单链表的特点

二、预备知识

三、单链表的基本结构

四、单链表的基本操作

1.链表打印

2.申请节点

3.头插

4.尾插

5.头删

6.尾删

7.查找节点

8.指定位置之前插入

9.指定位置之后插入

10.删除给定节点

11.删除给定节点之后的节点

12.链表销毁

五、示例程序

SLinkList.h 单链表结构定义及函数声明头文件

SLinkList.c 单链表方法实现源文件

test.c 测试文件

测试结果

六、实现单链表的常见问题

热门文章

最新文章

相关课程

相关电子书

相关实验场景

【数据结构与算法】深入理解 单链表

一、单链表的基本概念

单链表的简介

单链表的特点

二、预备知识

三、单链表的基本结构

四、单链表的基本操作

1.链表打印

2.申请节点

3.头插

4.尾插

5.头删

6.尾删

7.查找节点

8.指定位置之前插入

9.指定位置之后插入

10.删除给定节点

11.删除给定节点之后的节点

12.链表销毁

五、示例程序

SLinkList.h 单链表结构定义及函数声明头文件

SLinkList.c 单链表方法实现源文件

test.c 测试文件

测试结果

六、实现单链表的常见问题

热门文章

最新文章

相关课程

相关电子书

相关实验场景

【数据结构与算法】深入理解单链表