数据结构入门指南：单链表（附源码）-阿里云开发者社区

前言

前边关于链表的基础如果已经理解透彻，那么接下来就是对链表各功能的实现，同时也希望大家能把这部分内容熟练于心，这部分内容对有关链表部分的刷题很有帮助。废话不多讲我们步入正题。

前边已经实现了头插、尾插的操作，今天主要的内容是：头删、尾删、位置删除、位置后删除、查找、位置前插入、位置后插入。

尾删

要想进行尾删，就要先找到链表的尾。

我们知道单链表的缺点之一就是只可以单向遍历，所以要想删除最后一个节点，就要先找到倒数第二个节点，然后释放掉最后一个节点，将倒数第二个节点的next（指针域）置为NULL。

具体代码实现：

void SLPopBlack(SLNode** pphead)
{
  assert(*pphead);
  if ((*pphead)->next == NULL)
  {
    free(*pphead);
    *pphead = NULL;
  }
  SLNode* tail = *pphead;
  while (tail->next->next)
  {
    tail = tail->next;
  }
  free(tail->next);
  tail->next = NULL;
}

这里为什么要传二级指针？有人可能会有这样的疑惑，传二级指针就是为了防止链表被删空的情况，在链表的许多情节中都要考虑像链表删空等这种极端情况，要做到面面俱到。

当然我们也可以选择不使用二级指针，而是直接返回头指针的地址。但这样函数的类型就变成了结构体指针类型，而要调用这个函数还需要相同类型的结构体指针变量接收，这种情况在刷题中经常遇到，但在写链表时不推荐，这样写调用函数会比较麻烦。

头删

头删大家可以先思考一下，需不需要使用二级指针。

有这样一个链表：

想要删除第一个节点，只需要把头指针指向的位置改为指向第二个节点。把头指针修改，这是修改结构体指针，到这里想必大家已经清楚，需要使用二级指针。

接下来我们理一下删除的逻辑，直接将头指针指向第二个节点，这样就会造成第一个节点丢失没办法释放掉空间。如果先将第一个节点释放就会使第二个节点丢失，头指针无法连接剩余节点。

这要怎么解决呢？这里就需要创建一个新的变量来存储一下第二个节点的地址，然后再将第一个节点释放。

具体代码实现：

void SLPopFront(SLNode** pphead)
{
  assert(*pphead);
  SLNode* newhead = (*pphead)->next;
  free(*pphead);
  *pphead = newhead;
}

查找

查找很简单，顺序表的查找返回的是下标，而链表返回的是节点的地址，后续的操作也是比较简单，我就不再画逻辑图。

SLNode* SLFind(SLNode* phead, Datatype x)
{
  SLNode* cur = phead;
  while (cur)
  {
    if (cur->data == x)
    {
      return cur;
    }
    cur = cur->next;
  }
  return NULL;
}

位置前插入

位置前插入，如果是在第一个节点位置前插入，就是头插，其次是要想在位置前插入就必须要知道前有个节点，单链表是无法逆向遍历的，所以要想知道前一个节点就必须要传头指针。然后将前一个节点的next置为新节点的地址，新节点的next置为pos位置节点的地址。

void SLFrontInsert(SLNode** pphead, SLNode* pos, Datatype x)
{
  assert(pos);
  if (pos == *pphead)
  {
    SLPushFront(pphead, x);
  }
  else
  {
    SLNode* prev = *pphead;
    SLNode* newnode = NewNode(x);
    while (prev->next != pos)
    {
      prev = prev->next;
    }
    newnode->next = pos;
    prev->next = newnode;
  }
}

位置后插入

位置后插入，可以不需要头指针。操作也非常简单，把pos位置的下一个节点赋给新节点的next，把新节点的地址赋给pos位置节点的next。这里有人可能会有疑惑，不考虑极端情况吗？位置后插入是无法进行头插的，如果链表为空，传进来pos就为空，就会直接保错，至于尾插，这段代码也是可以解决的。

void SLAfterInsert(SLNode* pos, Datatype x)
{
  assert(pos);
  SLNode* newnode = NewNode(x);
  newnode->next = pos->next;
  pos->next = newnode;
}

位置删除

位置删除，需要把pos位置前一个节点的next置为pos位置下一个节点的地址，同时还需要将删除的节点释放空间。考虑极端情况，如果删除位置是第一个节点，这种方法就失效了，因为没有第一个节点的前一个节点，这时也就是头删，我们可以调用前边已经实现的函数接口。

void SLErase(SLNode** pphead, SLNode* pos) {
  assert(pphead);
  assert(pos);
  if (pos == *pphead)
  {
    SLPopFront(pphead);
  }
  else
  {
    SLNode* prev = *pphead;
    while (prev->next != pos)
    {
      prev = prev->next;
    }
    prev->next = pos->next;
    free(pos);
    pos = NULL;
  }
}

位置后删除

位置后删除，如果位置为最后一个节点，就不需要删除，且位置后删除无法进行头删，然后是正常情况，把pos位置节点的next置为pos位置后第二个节点的地址，就完成了。那是否可以这样写呢？

pos->next = pos->next->next

答案是不可以，这样会造成pos后一个节点丢失，无法释放。所以这里我们需要分成两步来写：

void SLEraseAfter(SLNode* pos)
{
  assert(pos);
  if (pos->next == NULL)
  {
    return;
  }
  else
  {
    SLNode* posnext = pos->next;//不可以写成一步，否则pos后一个节点就会丢失，无法释放
    pos->next = posnext->next;
    free(posnext);
    posnext = NULL;
  }
}

链表销毁

执行完所有操作后，就需要将链表销毁了

void SLDestory(SLNode** pphead)
{
  assert(pphead);
  SLNode* cur = *pphead;
  while (cur)
  {
    SLNode* next =cur->next;
    free(cur);
    cur = next;
  }
  *pphead = NULL;
}

完整代码：

SList.c

#include"SList.h"
void SLprint(SLNode* phead)
{
  SLNode* cur = phead;
  while (cur)
  {
    printf("%d->", cur->data);
    cur = cur->next;
  }
  printf("NULL\n");
}
SLNode* NewNode(Datatype x)
{
  SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
  if (newnode == NULL)
  {
    perror("malloc");
    exit(-1);
  }
  newnode->data = x;
  newnode->next = NULL;
  return newnode;
}
void SLPushBlack(SLNode** pphead, Datatype x)
{
  assert(pphead);
  SLNode* newnode = NewNode(x);
  SLNode* tail = *pphead;
  if (*pphead == NULL)
  {
    *pphead = newnode;
  }
  else
  {
    while (tail->next)
    {
      tail = tail->next;
    }
    tail->next = newnode;
  }
}
void SLPushFront(SLNode** pphead, Datatype x)
{
  assert(pphead);
  SLNode* newnode = NewNode(x);
  newnode->next = *pphead;
  *pphead = newnode;
}
void SLPopBlack(SLNode** pphead)
{
  assert(pphead);
  assert(*pphead);
  if ((*pphead)->next == NULL)
  {
    free(*pphead);
    *pphead = NULL;
  }
  SLNode* tail = *pphead;
  while (tail->next->next)
  {
    tail = tail->next;
  }
  free(tail->next);
  tail->next = NULL;
}
void SLPopFront(SLNode** pphead)
{
  assert(pphead);
  assert(*pphead);
  SLNode* newhead = (*pphead)->next;
  free(*pphead);
  *pphead = newhead;
}
SLNode* SLFind(SLNode* phead, Datatype x)
{
  SLNode* cur = phead;
  while (cur)
  {
    if (cur->data == x)
    {
      return cur;
    }
    cur = cur->next;
  }
  return NULL;
}
void SLFrontInsert(SLNode** pphead, SLNode* pos, Datatype x)
{
  assert(pphead);
  assert(pos);
  if (pos == *pphead)
  {
    SLPushFront(pphead, x);
  }
  else
  {
    SLNode* prev = *pphead;
    SLNode* newnode = NewNode(x);
    while (prev->next != pos)
    {
      prev = prev->next;
    }
    newnode->next = pos;
    prev->next = newnode;
  }
}
void SLAfterInsert(SLNode* pos, Datatype x)
{
  assert(pos);
  SLNode* newnode = NewNode(x);
  newnode->next = pos->next;
  pos->next = newnode;
}
void SLErase(SLNode** pphead, SLNode* pos) {
  assert(pphead);
  assert(pos);
  if (pos == *pphead)
  {
    SLPopFront(pphead);
  }
  else
  {
    SLNode* prev = *pphead;
    while (prev->next != pos)
    {
      prev = prev->next;
    }
    prev->next = pos->next;
    free(pos);
    pos = NULL;
  }
}
void SLEraseAfter(SLNode* pos)
{
  assert(pos);
  if (pos->next == NULL)
  {
    return;
  }
  else
  {
    SLNode* posnext = pos->next;
    pos->next = posnext->next;
    free(posnext);
    posnext = NULL;
  }
}
void SLDestory(SLNode** pphead)
{
  assert(pphead);
  SLNode* cur = *pphead;
  while (cur)
  {
    SLNode* next =cur->next;
    free(cur);
    cur = next;
  }
  *pphead = NULL;
}

SList.h

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int Datatype;
typedef struct SLNode
{
  Datatype data;
  struct SLNode* next;
}SLNode;
//打印链表
void SLprint(SLNode* phead);
//创建新节点
SLNode* NewNode(Datatype x);
//尾插
void SLPushBlack(SLNode** phead, Datatype x);
//头插
void SLPushFront(SLNode** pphead, Datatype x);
//尾删
void SLPopBlack(SLNode** pphead);
//头删
void SLPopFront(SLNode** pphead);
//查找
SLNode* SLFind(SLNode* phead, Datatype x);
//pos位置前插入
void SLFrontInsert(SLNode** pphead, SLNode* pos, Datatype x);
//pos位置后插入
void SLAfterInsert(SLNode* pos, Datatype x);
//pos位置后删除
void SLEraseAfter(SLNode* pos);
//pos位置删除
void SLErase(SLNode** pphead, SLNode* pos);
void SLDestory(SLNode** pphead);

test.c

这里基本都是测试接口，没有什么太大的参考价值，代码如下，便于大家调试。

#include"SLNode.h"
void test1()
{
  SLNode* plist = NULL;
  int n = 0;
  printf("请输入链表的长度\n");
  scanf("%d", &n);
  printf("请输入数据\n");
  for (int i = 0; i < n; i++)
  {
    int val = 0;
    scanf("%d", &val);
    SLNode *newnode= NewNode(val);
    newnode->next = plist;
    plist = newnode;
  }
  SLNode* pos= SLFind(plist, 2);
  if (pos)
  {
    pos->data *= 10;
  }
  SLFrontInsert(&plist, pos, 10);
  SLprint(plist);
  SLPushBlack(&plist,100);
  SLprint(plist);
  SLPushFront(&plist, 200);
  SLprint(plist);
  SLPopBlack(&plist);
  SLprint(plist);
  SLPopFront(&plist);
  SLprint(plist);
}
void test2()
{
  SLNode* plist = NULL;
  SLPushBlack(&plist, 1);
  SLPushBlack(&plist, 2);
  SLPushBlack(&plist, 3);
  SLPushBlack(&plist, 4);
  SLPushBlack(&plist, 5);
  SLprint(plist);
  SLNode* pos = SLFind(plist, 5);
  SLAfterInsert(pos, 20);
  SLprint(plist);
  SLFrontInsert(&plist, pos, 10);
  SLprint(plist);
}
void test3()
{
  SLNode* plist = NULL;
  SLPushBlack(&plist, 1);
  SLPushBlack(&plist, 2);
  SLPushBlack(&plist, 3);
  SLPushBlack(&plist, 4);
  SLPushBlack(&plist, 5);
  SLprint(plist);
  SLNode* pos = SLFind(plist, 1);
  //SLErase(&plist, pos);
  SLEraseAfter(pos);
  SLprint(plist);
  SLDestory(&plist);
}
int main()
{
  test2();
  return 0;
}

总结

好的，内容到这里就要结束了，这部分内容或许看来很繁琐，但在刷链表相关的题时就会惊奇的发现，题解都是这些操作的变形。熟练这部分内容，可以让你在刷链表相关的题时会感觉非常的爽，刷题也会更加顺利。最后，感谢阅读！

数据结构入门指南：单链表（附源码）

前言

尾删

头删

查找

位置前插入

位置后插入

位置删除

位置后删除

链表销毁

总结

热门文章

最新文章

相关课程

相关电子书