数据结构——链表-阿里云开发者社区

链表的引入

对于顺序表存在一些缺陷：

中间/头部的插入删除，时间复杂度为O(N) 。头部插入需要挪动后面的元素

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

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

对于链表而言，能够避免上述问题的出现。头部插入数据不需要挪动大量的数据，按需申请释放空间，不会造成空间的浪费。

链表的概念及结构

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

现实中数据结构中（箭头实际上并不存在，这里只是形象化）:

链表的种类有很多

以下情况组合起来就有8种链表结构：

单向或者双向：

带头或者不带头：

循环或者非循环：

面对这么多种类的链表，我们该如何选择？虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：

无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等
带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了

话不多说，直接进入我们单链表的实现：

单链表的接口我们需要实现：

打印销毁
头插尾插创建新结点(由于后面会频繁使用，故将其封装成函数)
尾删头删查找
在pos之前插入、在pos之后插入
删除pos、删除pos之后的位置

我们还是老样子，通过三个部分组成：

**SList.h:**包括头文件的引用，结构体的声明定义，接口函数的声明。

**SList.c:**对SList.h中接口函数进行实现。

**test.c:**主函数进行测试：通过void TestSList()函数对SList.c的函数进行调用，测试有没有错误。

注意：对于一些问题的所在，我已经通过注释进行相关说明。注释才是精髓。

SList.h

#define _CRT_SECURE_NO_WARNINGS
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLTDataType;
typedef struct SListNode
{
  SLTDataType data;
  struct SLTNode* next;
}SLTNode;
//打印
void SListPrint(SLTNode* phead);
//创建新结点
SLTNode* BuySLTNode(SLTDataType x);
//销毁
void SListDestory(SLTNode** pphead);
//头插
void SListPushFront(SLTNode** pphead, SLTDataType x);
//尾插
void SListPushBack(SLTNode** pphead, SLTDataType x);
//尾删
void SListPopBack(SLTNode**pphead);
//头删
void SListPopFront(SLTNode**pphead);
//查找
SLTNode* SListFind(SLTNode* pphead,SLTDataType x);
//在pos之前插入
void SListInsert(SLTNode** pphead,SLTNode*pos,SLTDataType x);
//在pos之后插入
void SListInsertAfter(SLTNode* pos, SLTDataType x);
//删除pos
void SListErase(SLTNode** pphead,SLTNode*pos);
//删除pos后面位置,了解
void SListEraseAfter(SLTNode* pos);

SList.c

#define _CRT_SECURE_NO_WARNINGS
#include "SList.h"
//打印
void SListPrint(SLTNode* phead)
{
  //phead不需要断言。因为phead有可能有空，没有数据
  //而顺序表的结构体不可能为空，所以要进行断言
  SLTNode* cur = phead;
  while (cur != NULL)
  {
    printf("%d->", cur->data);
    cur = cur->next;
  }
  printf("NULL\n");
}
//创建新结点
SLTNode* BuySLTNode(SLTDataType x)
{
  SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
  if (newnode == NULL)
  {
    perror("mail fail");
    exit(-1);
  }
  newnode->data = x;
  newnode->next = NULL;
  return newnode;
}
//销毁
void SListDestory(SLTNode** pphead)
{
  assert(pphead);
  SLTNode* cur = *pphead;
  while (cur)
  {
    SLTNode* next = cur->next;
    free(cur);
    cur = next;
  }
  *pphead = NULL;
}
//头插
void SListPushFront(SLTNode** pphead, SLTDataType x)
{
  assert(pphead);
  SLTNode* newnode = BuySLTNode(x);
  newnode->next = *pphead;
  *pphead = newnode;
}
//尾插——有无结点。需要找前一个
void SListPushBack(SLTNode** pphead, SLTDataType x)
{
  assert(pphead);
  SLTNode* newnode = BuySLTNode(x);
  //空,改变的是SListNode*,需要二级指针
  //非空。尾插要改变的是结构体SListNode，只需要结构体的指针
  if (*pphead == NULL)
  {
    *pphead = newnode;
  }
  else
  {
    //找尾
    SLTNode* tail = *pphead;
    while (tail->next != NULL)
    {
      tail = tail->next;
    }
    tail->next = newnode;
  }
}
//尾删——有无结点。需要找前一个
void SListPopBack(SLTNode** pphead)
{
  assert(pphead);
  SLTNode* tail = *pphead;
  SLTNode* prev = NULL;
  assert(*pphead != NULL);
  if ((*pphead)->next == NULL)
  {
    free(*pphead);
    *pphead = NULL;
  }
  else
  {
    while (tail->next != NULL)
    {
      prev = tail;
      tail = tail->next;
    }
    prev->next = NULL;
    free(tail);
    tail = NULL;
    /*while (tail->next->next!=NULL)
    {
      tail = tail->next;
    }
    free(tail->next);
    tail->next = NULL;*/
  }
}
//头删
void SListPopFront(SLTNode** pphead)
{
  assert(pphead);
  assert(*pphead);
  /*if (*pphead == NULL)
  {
    return;
  }*/
  SLTNode* del = *pphead;
  *pphead = (*pphead)->next;
  free(del);
  del = NULL;
}
//查找
SLTNode* SListFind(SLTNode* pphead, SLTDataType x)
{
  assert(pphead);
  SLTNode* cur = pphead;
  while (cur)
  {
    if (cur->data == x)
    {
      return cur;
    }
    cur = cur->next;
  }
  return NULL;
}
//在pos之前插入，需要找前一个
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
  assert(pphead);
  assert(pos);
  if (pos == *pphead)
  {
    SListPushFront(pphead, x);
  }
  else
  {
    SLTNode* newnode = BuySLTNode(x);
    SLTNode* prev = *pphead;
    while (prev->next != pos)
    {
      prev = prev->next;
      assert(prev);
    }
    prev->next = newnode;
    newnode->next = pos;
  }
}
//在pos后插入
void SListInsertAfter(SLTNode* pos, SLTDataType x)
{
  assert(pos);
  SLTNode* newnode = BuySLTNode(x);
  newnode->next = pos->next;
  pos->next = newnode;
}
//删除pos位置，需要找前一个
void SListErase(SLTNode** pphead, SLTNode* pos)
{
  assert(pphead);
  assert(pos);
  if (pos == *pphead)
  {
    SListPopFront(pphead);
  }
  else
  {
    SLTNode* prev = *pphead;
    while (prev->next != pos)
    {
      prev = prev->next;
      //检查pos不是链表中的结点
      assert(prev);
    }
    prev->next = pos->next;
    free(pos);
  }
}
//删除pos后面位置
void SListEraseAfter(SLTNode* pos)
{
  assert(pos);
  if (pos->next == NULL)
  {
    return;
  }
  else
  {
    SLTNode* next = pos->next;
    pos->next = next->next;
    free(next);
  }
}

test.c

#define _CRT_SECURE_NO_WARNINGS
#include "SList.h"
//头插、头删
void TestSList1()
{
  SLTNode* plist = NULL;
  SListPushFront(&plist, 1);
  SListPushFront(&plist, 2);
  SListPushFront(&plist, 3);
  SListPushFront(&plist, 4);
  SListPrint(plist);
  SListPopFront(&plist);
  SListPrint(plist);
  SListPopFront(&plist);
  SListPrint(plist);
  SListPopFront(&plist);
  SListPrint(plist);
  SListPopFront(&plist);
  SListPrint(plist);
  SListPopFront(&plist);
  SListPrint(plist);
  SListDestory(&plist);
}
//尾插、尾删
void TestSList2()
{
  SLTNode* plist = NULL;
  SListPushBack(&plist, 1);
  SListPushBack(&plist, 2);
  SListPushBack(&plist, 3);
  SListPushBack(&plist, 4);
  SListPrint(plist);
  SListPopBack(&plist);
  SListPopBack(&plist);
  SListPopBack(&plist);
  SListPopBack(&plist);
  SListPopBack(&plist);
  SListDestory(&plist);
}
//查找、在pos之前插入
void TestSList3()
{
  SLTNode* plist = NULL;
  SListPushBack(&plist, 1);
  SListPushBack(&plist, 2);
  SListPushBack(&plist, 3);
  SListPushBack(&plist, 4);
  SListPrint(plist);
  SLTNode* pos = SListFind(plist, 3);
  if (pos)
  {
    //修改
    pos->data *= 10;
    printf("找到了\n");
  }
  else
  {
    printf("找不到\n");
  }
  pos = SListFind(plist, 1);
  if (pos)
  {
    SListInsert(&plist, pos, 10);
  }
  SListPrint(plist);
  SListDestory(&plist);
}
//删除pos位置、删除pos后面的位置
void TestSList4()
{
  SLTNode* plist = NULL;
  SListPushBack(&plist, 1);
  SListPushBack(&plist, 2);
  SListPushBack(&plist, 3);
  SListPushBack(&plist, 4);
  SListPrint(plist);
  SLTNode* pos = SListFind(plist, 3);
  if (pos)
  {
    SListErase(&plist, pos);
  }
  SListPrint(plist);
  pos = SListFind(plist, 1);
  if (pos)
  {
    SListErase(&plist, pos);
  }
  SListPrint(plist);
}
int main()
{
  //TestSList1();
  //TestSList2();
  //TestSList3();
  TestSList4();
  return 0;
}

以上就是单链表的相关操作，我们不难发现，单链表的优势在于头插头删

而对于一些操作：如尾插尾删而言，我们都需要去找前一个位置，这是比较麻烦的。单链表我们就先介绍到这里了。

这里同时也有一个问题存在：

删除当前位置我们需要去找前一个位置，这效率是比较低的，我们如何改进这个问题❓

找pos位置删除，而就是不找前一个位置（即要求是O（1））：替换法删除，把pos的值和下一个节点的值进行交换，再把pos进行释放掉。但是有一个缺陷：pos不能是尾节点。尾节点没有下一项。

那如果在pos位置之前插入，要求为O（1）呢：

直接插入到pos后面，然后进行交换

数据结构——链表

链表的引入

链表的概念及结构

SList.h

SList.c

test.c

热门文章

最新文章

相关课程

相关电子书