【数据结构】第三站：单链表-阿里云开发者社区

一、顺序表的缺陷

在上一篇文章中，我们了解了顺序表的结构以及他的接口的实现。但同时我们也发现了他的一些缺陷

问题：

1. 中间/头部的插入删除，时间复杂度为O(N)

2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。

3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。

思考：如何解决以上问题呢？下面给出了链表的结构来看看

二、链表

1.链表的概念以及结构

概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的

2.链表的分类

链表一共有八种类型，他们可由是单向还是双向，是循环还是非循环，是带头结点还是不带头结点进行排列组合出八种结构

虽然有很多种结构，但是只有两种最为常用

无头单向非循环链表和带头双向循环链表

这里我们先只需要了解无头单向非循环链表，其他链表后续了解

3.单链表的逻辑结构与物理结构

如下图所示，是链表的实际的物理结构与逻辑结构。物理结构就是实实在在数据在内存中的变化，逻辑结构就是为了方便理解，形象化出来的

三、单链表的实现

1.单链表的定义

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

如上代码所示，单链表有数据域和指针域两部分组成，指针是用于指向下一个结点的指针

2.单链表的接口定义

//单链表的打印
void SListPrint(SListNode* plist);
//单链表的尾插
void SListPushBack(SListNode** pplist, SLTDateType x);
//单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x);
//单链表的尾删
void SListPopBack(SListNode** pplist);
//单链表的头删
void SListPopFront(SListNode** pplist);
//单链表的查找
SListNode* SListFind(SListNode* plist,SLTDateType x);
//单链表在pos位置之后插入
void SListInsertAfter(SListNode* pos, SLTDateType x);
//单链表在pos位置之前插入
void SListInsertPrev(SListNode** pplist, SListNode* pos, SLTDateType x);
//单链表在pos之后删除
void SListEraseAfter(SListNode* pos);
//单链表在pos之前删除
void SListErasePrev(SListNode** pplist, SListNode* pos);
//单链表在pos位置删除
void SListErase(SListNode** pplist, SListNode* pos);
//单链表的销毁
void SListDestroy(SListNode** pplist);

如上代码所示，是我们的单链表需要实现的接口，对于链表和顺序表一样都是为了实现数据的管理，区别就是前者是离散的，后者是连续的。我们的目的还是增删查改

3.单链表的接口实现

1.单链表的打印

//单链表的打印
void SListPrint(SListNode* plist)
{
  SListNode* cur = plist;
  while (cur != NULL)
  {
    printf("%d->", cur->data);
    cur = cur->next;
  }
  printf("NULL\n");
}

我们先来完成单链表的打印，对于单链表的打印，还是比较简单的，只需要先将头结点的指针给保存下来，然后依次去遍历单链表即可

2.单链表的尾插以及获取结点函数

//获取一个结点
SListNode* BuySListNode(SLTDateType x)
{
  SListNode* tmp = (SListNode*)malloc(sizeof(SListNode));
  if (tmp == NULL)
  {
    perror("malloc fail");
    return;
  }
  tmp->next = NULL;
  tmp->data = x;
  return tmp;
}
//单链表的尾插
void SListPushBack(SListNode** pplist, SLTDateType x)
{
  assert(pplist);
  SListNode* newnode = BuySListNode(x);
  if (*pplist == NULL)
  {
    *pplist = newnode;
    return;
  }
  SListNode* tail = (*pplist);
  while (tail->next != NULL)
  {
    tail = tail->next;
  }
  tail->next = newnode;
}

对于单链表的尾插，我们要特别注意了。pplist是单链表头结点的地址，所以一定不为空

首先是获取结点，我们为了方便，先直接将其封装为一个函数。

有了结点了，那么我们还要思考如何尾插，那么我们先完成一般情况，假设已经有了一个很长的单链表了，我们还想要继续尾插一个值，那么只需要先找到原来的尾结点，然后将尾结点和新结点进行链接即可

当然还是存在一些特殊情况的，比如说原来的单链表压根就没有尾结点，也就是说链表是空的，那么上面的一般方法肯定行不通，这里其实就需要特殊处理一下，直接将新节点和链表头链接起来即可

3.单链表的头插

//单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x)
{
  assert(pplist);
  SListNode* newnode = BuySListNode(x);
  SListNode* first = *pplist;
  *pplist = newnode;
  newnode->next = first;
}

对于单链表的头插，就比较简单了，我们直接创建一个新结点，然后记录下原来的第一个结点的地址，然后让链表头与新节点链接起来，然后新节点与原来的第一个结点链接起来，这里我们会发下，其实是不需要处理空链表的情况的，这里体现了单链表适合头插

4.单链表的尾删

//单链表的尾删
void SListPopBack(SListNode** pplist)
{
  assert(pplist);
  assert(*pplist);
  if ((*pplist)->next == NULL)
  {
    free(*pplist);
    *pplist = NULL;
  }
  else
  {
    SListNode* tail = *pplist;
    while (tail->next->next != NULL)
    {
      tail = tail->next;
    }
    free(tail->next);
    tail->next = NULL;
  }
}

对于单链表的尾删，我们要想清楚了，首先是一般情况，当链表很长的时候，我们想要删除最后一个结点，那么得先找到前一个结点，然后释放最后一个结点，最后让前一个结点指向空。

我们还需要注意链表为空的状态，这个肯定是不可以删除的，所以我们直接断言掉。

然后是链表为一个结点的情况，如果链表只有一个结点，那么我们会发现，压根找不到前一个结点，所以我们也特殊处理，我们直接释放掉第一个结点，然后置空即可。

5.单链表的头删

//单链表的头删
void SListPopFront(SListNode** pplist)
{
  assert(pplist);
  assert(*pplist);
  SListNode* second = (*pplist)->next;
  free(*pplist);
  *pplist = second;
}

对于单链表的头删，我们同样断言掉链表为空的状态

然后我们需要做的就是记录第二个结点，然后释放原来的第一个结点，最后连接链表头和第二个结点。这样我们就实现了我们的目的。值得注意的是，我们发现链表的头删也是比较有优势的。

6.单链表的查找

//单链表的查找
SListNode* SListFind(SListNode* plist,SLTDateType x)
{
  SListNode* cur = plist;
  while (cur != NULL)
  {
    if (cur->data == x)
    {
      return cur;
    }
    cur = cur->next;
  }
  return NULL;
}

对于单链表的查找，这个也很简单，他和单链表的打印思路是一样的，不同的是只需要返回结点的地址即可。

7.单链表在pos位置之后的插入

//单链表在pos位置之后插入
void SListInsertAfter(SListNode* pos, SLTDateType x)
{
  assert(pos);
  SListNode* newnode = BuySListNode(x);
  SListNode* next = pos->next;
  pos->next = newnode;
  newnode->next = next;
}

单链表在pos位置之后的插入也是比较简单的，我们只需要先申请一个结点，然后记录pos位置的下一个结点，然后连接就可以了。值得注意的是，pos的位置不可能为空。因为他不是一个有效的结点地址

8.单链表在pos位置之前的插入

//单链表在pos位置之前插入
void SListInsertPrev(SListNode** pplist, SListNode* pos, SLTDateType x)
{
  assert(pplist);
  assert(pos);
  assert(*pplist);
  SListNode* newnode = BuySListNode(x);
  if (*pplist == pos)
  {
    *pplist = newnode;
    newnode->next = pos;
  }
  else
  {
    SListNode* prev = *pplist;
    while (prev->next != pos)
    {
      prev = prev->next;
    }
    prev->next = newnode;
    newnode->next = pos;
  }
}

对于在pos位置之前的插入，确实是比较繁琐了。我们要思考，首先pos和pplist不可能为空，然后这个链表也是不可能为空链表的，至少也要有一个值。否则如果存在pos这个结点呢？

然后我们在来考虑一般情况，我们假设链表很长，在中间位置pos之前插入一个结点，那么毫无疑问的是，我们需要先申请一个结点，然后在通过遍历的方式要找到pos之前的那个结点。

有了这两个结点，那么我们就可以进行连接了。

然后是特殊情况，假如这个链表只有一个结点呢，这个结点正好就是pos，我们发现pos就没有前一个结点，其实这个就等效于头插。我们采用头插的方式即可

9.单链表在pos之后删除

//单链表在pos之后删除
void SListEraseAfter(SListNode* pos)
{
  assert(pos);
  assert(pos->next);
  SListNode* next = pos->next;
  pos->next = next->next;
  free(next);
  next = NULL;
}

单链表在pos之后删除的话，首先pos和pos的下一个结点不会为空，否则题目就矛盾了。所以我们得断言，然后我们直接记录pos 的下一个结点，然后连接pos和pos之后的结点。最后释放掉pos的下一个结点即可。

10.单链表在pos之前删除

//单链表在pos之前删除
void SListErasePrev(SListNode** pplist, SListNode* pos)
{
  assert(pos);
  assert(pplist);
  assert(pos != *pplist);
  assert(*pplist);
  if ((*pplist)->next == pos)
  {
    SListNode* del = *pplist;
    *pplist = pos;
    free(del);
    del = NULL;
  }
  else
  {
    SListNode* prev = *pplist;
    while (prev->next->next != pos)
    {
      prev = prev->next;
    }
    SListNode* del = prev->next;
    prev->next = pos;
    free(del);
    del = NULL;
  }
}

对于单链表在pos之前删除确实就比较复杂了，首先pos，pplist，*pplist肯定不可能为空，然后pos也绝不可以是头节点，所以pos！=*pplist

我们现在来思考，假设一般情况，链表很长，在中间位置是pos，删除pos的前一个结点，那么我们就需要找到pos 的前一个的前一个结点。然后记录pos的前一个结点。释放pos 的前一个结点，然后进行连接即可

对于特殊情况，也就是，pos在第二个结点上，这样我们无法找到pos的前一个的前一个结点，但是这个就是头删，我们直接采用类似的思路即可

11.单链表在pos位置的删除

//单链表在pos位置删除
void SListErase(SListNode** pplist, SListNode* pos)
{
  assert(pplist);
  assert(pos);
  assert(*pplist);
  if (*pplist == pos)
  {
    free(pos);
    *pplist = pos = NULL;
  }
  else
  {
    SListNode* prev = *pplist;
    while (prev->next != pos)
    {
      prev = prev->next;
    }
    prev->next = pos->next;
    free(pos);
    pos = NULL;
  }
}

这个与上一个接口是基本一致的思路。不同的是，pos可以在头结点了，如果是头节点就是头删。

如果不是，就是先找到前一个结点，然后进行删除连接即可

12.单链表的销毁

//单链表的销毁
void SListDestroy(SListNode** pplist)
{
  SListNode* cur = *pplist;
  while (cur != NULL)
  {
    SListNode* next = cur->next;
    free(cur);
    cur = next;
  }
}

对于单链表的销毁，这个也很简单，就直接遍历销毁即可，与打印和查找的思路是一致的

四、单链表的实现完整代码

SList.h文件

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<assert.h>
typedef int SLTDateType;
typedef struct SListNode
{
  SLTDateType data;
  struct SListNode* next;
}SListNode;
//单链表的打印
void SListPrint(SListNode* plist);
//单链表的尾插
void SListPushBack(SListNode** pplist, SLTDateType x);
//单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x);
//单链表的尾删
void SListPopBack(SListNode** pplist);
//单链表的头删
void SListPopFront(SListNode** pplist);
//单链表的查找
SListNode* SListFind(SListNode* plist,SLTDateType x);
//单链表在pos位置之后插入
void SListInsertAfter(SListNode* pos, SLTDateType x);
//单链表在pos位置之前插入
void SListInsertPrev(SListNode** pplist, SListNode* pos, SLTDateType x);
//单链表在pos之后删除
void SListEraseAfter(SListNode* pos);
//单链表在pos之前删除
void SListErasePrev(SListNode** pplist, SListNode* pos);
//单链表在pos位置删除
void SListErase(SListNode** pplist, SListNode* pos);
//单链表的销毁
void SListDestroy(SListNode** pplist);

SList.c文件

#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"
//单链表的打印
void SListPrint(SListNode* plist)
{
  SListNode* cur = plist;
  while (cur != NULL)
  {
    printf("%d->", cur->data);
    cur = cur->next;
  }
  printf("NULL\n");
}
//获取一个结点
SListNode* BuySListNode(SLTDateType x)
{
  SListNode* tmp = (SListNode*)malloc(sizeof(SListNode));
  if (tmp == NULL)
  {
    perror("malloc fail");
    return;
  }
  tmp->next = NULL;
  tmp->data = x;
  return tmp;
}
//单链表的尾插
void SListPushBack(SListNode** pplist, SLTDateType x)
{
  assert(pplist);
  SListNode* newnode = BuySListNode(x);
  if (*pplist == NULL)
  {
    *pplist = newnode;
    return;
  }
  SListNode* tail = (*pplist);
  while (tail->next != NULL)
  {
    tail = tail->next;
  }
  tail->next = newnode;
}
//单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x)
{
  assert(pplist);
  SListNode* newnode = BuySListNode(x);
  SListNode* first = *pplist;
  *pplist = newnode;
  newnode->next = first;
}
//单链表的尾删
void SListPopBack(SListNode** pplist)
{
  assert(pplist);
  assert(*pplist);
  if ((*pplist)->next == NULL)
  {
    free(*pplist);
    *pplist = NULL;
  }
  else
  {
    SListNode* tail = *pplist;
    while (tail->next->next != NULL)
    {
      tail = tail->next;
    }
    free(tail->next);
    tail->next = NULL;
  }
}
//单链表的头删
void SListPopFront(SListNode** pplist)
{
  assert(pplist);
  assert(*pplist);
  SListNode* second = (*pplist)->next;
  free(*pplist);
  *pplist = second;
}
//单链表的查找
SListNode* SListFind(SListNode* plist,SLTDateType x)
{
  SListNode* cur = plist;
  while (cur != NULL)
  {
    if (cur->data == x)
    {
      return cur;
    }
    cur = cur->next;
  }
  return NULL;
}
//单链表在pos位置之后插入
void SListInsertAfter(SListNode* pos, SLTDateType x)
{
  assert(pos);
  SListNode* newnode = BuySListNode(x);
  SListNode* next = pos->next;
  pos->next = newnode;
  newnode->next = next;
}
//单链表在pos位置之前插入
void SListInsertPrev(SListNode** pplist, SListNode* pos, SLTDateType x)
{
  assert(pplist);
  assert(pos);
  assert(*pplist);
  SListNode* newnode = BuySListNode(x);
  if (*pplist == pos)
  {
    *pplist = newnode;
    newnode->next = pos;
  }
  else
  {
    SListNode* prev = *pplist;
    while (prev->next != pos)
    {
      prev = prev->next;
    }
    prev->next = newnode;
    newnode->next = pos;
  }
}
//单链表在pos之后删除
void SListEraseAfter(SListNode* pos)
{
  assert(pos);
  assert(pos->next);
  SListNode* next = pos->next;
  pos->next = next->next;
  free(next);
  next = NULL;
}
//单链表在pos之前删除
void SListErasePrev(SListNode** pplist, SListNode* pos)
{
  assert(pos);
  assert(pplist);
  assert(pos != *pplist);
  assert(*pplist);
  if ((*pplist)->next == pos)
  {
    SListNode* del = *pplist;
    *pplist = pos;
    free(del);
    del = NULL;
  }
  else
  {
    SListNode* prev = *pplist;
    while (prev->next->next != pos)
    {
      prev = prev->next;
    }
    SListNode* del = prev->next;
    prev->next = pos;
    free(del);
    del = NULL;
  }
}
//单链表在pos位置删除
void SListErase(SListNode** pplist, SListNode* pos)
{
  assert(pplist);
  assert(pos);
  assert(*pplist);
  if (*pplist == pos)
  {
    free(pos);
    *pplist = pos = NULL;
  }
  else
  {
    SListNode* prev = *pplist;
    while (prev->next != pos)
    {
      prev = prev->next;
    }
    prev->next = pos->next;
    free(pos);
    pos = NULL;
  }
}
//单链表的销毁
void SListDestroy(SListNode** pplist)
{
  SListNode* cur = *pplist;
  while (cur != NULL)
  {
    SListNode* next = cur->next;
    free(cur);
    cur = next;
  }
}

Test.c文件

#define _CRT_SECURE_NO_WARNINGS 1
#include"Slist.h"
void TestSList1()
{
  SListNode* phead = NULL;
  SListPushBack(&phead, 1);
  SListPushBack(&phead, 2);
  SListPushBack(&phead, 3);
  SListPushBack(&phead, 4);
  SListPushBack(&phead, 5);
  SListPrint(phead);
  SListPushFront(&phead, 6);
  SListPushFront(&phead, 7);
  SListPushFront(&phead, 8);
  SListPushFront(&phead, 9);
  SListPushFront(&phead, 10);
  SListPrint(phead);
  SListPopBack(&phead);
  SListPopBack(&phead);
  SListPopBack(&phead);
  SListPopBack(&phead);
  SListPrint(phead);
  SListPopBack(&phead);
  SListPrint(phead);
}
void TestSList2()
{
  SListNode* phead = NULL;
  SListPushBack(&phead, 1);
  SListPushBack(&phead, 2);
  SListPushBack(&phead, 3);
  SListPushBack(&phead, 4);
  SListPushBack(&phead, 5);
  SListPrint(phead);
  SListPopFront(&phead);
  SListPopFront(&phead);
  SListPopFront(&phead);
  SListPopFront(&phead);
  SListPrint(phead);
  SListPopFront(&phead);
  SListPrint(phead);
}
void TestSList3()
{
  SListNode* phead = NULL;
  SListPushBack(&phead, 1);
  SListPushBack(&phead, 2);
  SListPushBack(&phead, 3);
  SListPushBack(&phead, 4);
  SListPushBack(&phead, 5);
  SListPrint(phead);
  SListNode* pos = SListFind(phead, 3);
  pos->data = 100;
  SListPrint(phead);
  SListInsertAfter(pos, 200);
  SListInsertAfter(pos, 300);
  SListInsertAfter(pos, 400);
  SListInsertAfter(pos, 500);
  SListPrint(phead);
  SListNode* pos2 = SListFind(phead, 1);
  SListInsertPrev(&phead, pos2, 101);
  SListInsertPrev(&phead, pos2, 102);
  SListInsertPrev(&phead, pos2, 103);
  SListInsertPrev(&phead, pos2, 104);
  SListPrint(phead);
  SListEraseAfter(pos2);
  SListEraseAfter(pos2);
  SListEraseAfter(pos2);
  SListPrint(phead);
}
void TestSList4()
{
  SListNode* phead = NULL;
  SListPushBack(&phead, 1);
  SListPushBack(&phead, 2);
  SListPushBack(&phead, 3);
  SListPushBack(&phead, 4);
  SListPushBack(&phead, 5);
  SListPrint(phead);
  SListNode* pos = SListFind(phead, 5);
  SListErasePrev(&phead, pos);
  SListPrint(phead);
  SListErasePrev(&phead, pos);
  SListPrint(phead);
  SListErase(&phead, pos);
  SListPrint(phead);
  SListDestroy(&phead);
}
int main()
{
  //TestSList1();
  //TestSList2();
  //TestSList3();
  TestSList4();
  return 0;
}

本节内容到此位置，感谢您的阅读

如果对你有帮助的话，不要忘记点赞加收藏哦！！！

【数据结构】第三站：单链表

一、顺序表的缺陷

二、链表

1.链表的概念以及结构

2.链表的分类

3.单链表的逻辑结构与物理结构

三、单链表的实现

1.单链表的定义

2.单链表的接口定义

3.单链表的接口实现

四、单链表的实现完整代码

热门文章

最新文章

相关课程

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

【数据结构】第三站：单链表

一、顺序表的缺陷

二、链表

1.链表的概念以及结构

2.链表的分类

3.单链表的逻辑结构与物理结构

三、单链表的实现

1.单链表的定义

2.单链表的接口定义

3.单链表的接口实现

四、单链表的实现完整代码

热门文章

最新文章

相关课程

相关电子书