什么是链表

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

通俗地讲，就是一个结构体有两个成员，一个是存放数据的成员，一个是指针成员，通常的单链表是第一个节点的指针成员存着下一个节点的地址，下一个节点的指针成员又存下一个节点的地址，这样每个节点之间连接起来，就叫做链表。

本文主要讲的是链表中的一种重要的形式：单链表。

上图就是链表的逻辑图，head 是一个指针，存放链表第一个节点的地址，所以可以形象地称为头指针。

在真实的物理地址中，并不存在所谓的箭头，这些箭头是我们想象出来的，助于理解的东西。

假设地址都是随机的，那么上图才是真实的物理图。

每个节点的指针存储的都是下一个节点的地址，这样就像链条一样连接起来。

有了这些，我们就可以实现单链表的各种操作了

1.单链表的结构

typedef int SLTDataType;
typedef struct SListNode
{
  SLTDataType data;
  struct SListNode* next;
}SLTNode;

注意这里有一个细节，定义结构体指针的时候，不能使用SListNodenext，涉及到一个编译器的查找规则。

类型的重命名是再结构体完成定义之后的，而编译器去查找SListNode是从next定义这一行的上面查找的，不会往下找。

就像上面单链表的结构所讲，每个节点都有一个data 和一个指针，用来保存下一个节点的地址。

2.单链表的头文件包含

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

3.单链表节点的创建

SLTNode* BuyListNode(SLTDataType x)
{
  SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
  assert(newnode);
  newnode->data = x;
  newnode->next = NULL;
  return newnode;
  //创建节点
}

断言的目的是防止申请空间失败而出错。

4.单链表的打印

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

打印的时候不需要断言，空链表也可以打印出来。只是打印出来是空。

下面的头插尾插头删尾删都需二级指针的原因是：

传参过来的时候传的是一个一级指针的地址。

当我们想要改变一级指针时，就需要用二级指针来接收。

5.单链表尾插法

void SListPushBack(SLTNode** pphead, SLTDataType x)
{
  assert(pphead);//*pphead = plist,pphead = &plist,地址是不可能为空的，如果为空，就是传过来的参数传错了。
  SLTNode*newnode = BuyListNode(x);//创建节点
  //如果一开始链表为空，即没有节点
  if (*pphead == NULL)
  {
    *pphead = newnode;
  }
  else
  {
    //找到尾结点
    SLTNode* ptail = *pphead;
    while (ptail->next != NULL)
    {
      ptail = ptail->next;
    }
    //找到尾了，插入新节点
    if (newnode != NULL)
    {
      newnode->data = x;
      newnode->next = NULL;
      ptail->next = newnode;
      //就是让尾节点的next存newnode的地址
    }
  }
}

尾插需要分情况来讨论，当链表为空时如何插入。

6.单链表头插

void SListPushFront(SLTNode** pphead, SLTDataType x)
{
  assert(pphead);//*pphead = plist,pphead = &plist,地址是不可能为空的，如果为空，就是传过来的参数传错了。
  SLTNode* newnode = BuyListNode(x);//创建节点
  //头插法不需要分情况讨论
  newnode->next = *pphead;
  *pphead = newnode;
}

头插不需要分情况讨论，不管链表是否为空，都可以满足要求。

7.单链表的尾删

void SListPopBack(SLTNode** pphead)
{
  assert(pphead);//*pphead = plist,pphead = &plist,地址是不可能为空的，如果为空，就是传过来的参数传错了。
  assert(*pphead != NULL);//空链表
  //一个节点的情况
  if ((*pphead)->next == NULL)
  {
    free(*pphead);
    *pphead = NULL;
    return;
  }
  //法1：不需要临时变量
  //assert(*pphead);
  //SLTNode* ptail = *pphead;
  //while (ptail->next->next!=NULL)
  //{
  //  ptail = ptail->next;
  //}
  找到尾结点
  //free(ptail->next);
  //ptail->next =  NULL;
  //法2：需要临时变量
  SLTNode* ptail = *pphead;
  SLTNode* prev = ptail;
  while (ptail->next!=NULL)
  {
    prev = ptail;
    ptail = ptail->next;
  }
  free(ptail);
  ptail = NULL;
  prev->next = NULL;
}

在尾删中，有两种方法，可以使用临时变量，也可以不使用临时变量，空间复杂度为O(1)。

8.单链表头删

void SListPopFront(SLTNode** pphead) // 头删
{
  assert(pphead);//*pphead = plist,pphead = &plist,地址是不可能为空的，如果为空，就是传过来的参数传错了。
  assert(*pphead != NULL);//针对链表为空的情况
  //让指向头节点的指针指向下一个节点
  SLTNode* pnext = (*pphead)->next;
  free(*pphead);
  *pphead = pnext;
}
{

值得注意的是，单链表的头插和尾插都可以使用带哨兵位的头节点来进行头插和尾插，带哨兵位的头节点式的头插或尾插的好处是，当链表为空时，不需要分类判断。
但是带哨兵位的头节点的头插或尾插也有劣势，就是哨兵位节点需要申请，并且需要释放掉。

9.单链表查找

SLTNode* SListFind(SLTNode* phead, SLTDataType x)//查找节点
{
  assert(phead!=NULL);
  SLTNode* cur = phead;
  while (cur)
  {
    if (cur->data == x)
    {
      return cur;
    }
    else
    {
      cur = cur->next;
    }
  }
  //最后没找到
  return NULL;
}

10.在pos位置之后插入节点

void SListInsertAfter(SLTNode* pos, SLTDataType x)
{
  SLTNode* newnode = BuyListNode(x);
  assert(newnode);
  //注意二者位置不能更换，否则整条链表的数据就丢失了
  newnode->next = pos->next;
  pos->next = newnode;
}

11.在pos位置之前插入节点

//在pos的前面插入节点
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
  assert(pphead);//*pphead = plist,pphead = &plist,地址是不可能为空的，如果为空，就是传过来的参数传错了。
  assert(pos);//地址不能为空
  //不管三七二十一，先创建一个节点
  SLTNode* newnode = BuyListNode(x);
  SLTNode* posPrev = *pphead;
  //判断头插的情况
  if (*pphead == pos)
  {
    newnode->next = pos;
    *pphead = newnode;
  }//或者调用头插接口
  else
  {
    while (posPrev->next != pos)
    {
      posPrev = posPrev->next;
    }
    posPrev->next = newnode;
    newnode->next = pos;
  }
}

可以比较发现，在pos位置之前和在pos位置之后插入节点的区别是，在pos位置之后插入节点的方法更简单，效率更高。

12.单链表删除pos位置之后的节点

void SlistEraseAfter(SLTNode* pos)//删除pos后一个节点
{
  assert(pos);//地址不能为空
  assert(pos->next!=NULL);
  SLTNode* Erasenode = pos->next;
  pos->next = Erasenode->next;
  free(Erasenode);
  Erasenode = NULL;
}

13.单链表删除pos位置的节点

void SlistErase(SLTNode** pphead, SLTNode* pos)//删除pos位置
{
  assert(pphead);//*pphead = plist,pphead = &plist,地址是不可能为空的，如果为空，就是传过来的参数传错了。
  assert(pos);//地址不能为空
  assert(*pphead != NULL);//空链表无法删除
  //链表只有一个节点的情况
  if ((*pphead)->next == NULL)
  {
    free(*pphead);
    *pphead = NULL;
    return;
  }
  //删除头节点的情况，相当于头删，可以调用头删接口
  if (*pphead == pos)
  {
    (*pphead) = pos->next;
    free(pos);
    pos = NULL;
    return;
  }
  if (pos->next == NULL)//尾删的情况
  {
    SLTNode* pnext = *pphead;
    while (pnext->next != pos)
    {
      pnext = pnext->next;
    }
    free(pos);
    //pos = NULL;//这里pos是形参，置空无意义
    pnext->next = NULL;
    return;
  }
  SLTNode* posprev = *pphead;
  while (posprev->next != pos)
  {
    posprev = posprev->next;
  }
  posprev->next = pos->next;
  free(pos);
  //pos = NULL;//这里pos是形参，置空无意义，
  //不过好习惯还是置空
}

对比删除pos位置和删除pos位置之后的节点的方法比较可知，删除pos位置的节点需要知道pos位置之前的节点，需要遍历链表，时间复杂度为O(n)。

删除pos位置之后的节点，不需要遍历链表，只需直接删除即可。
在参数部分，pos可以使用int类型，也可以使用结构体类型，个人认为使用结构体类型更全面，使用结构体类型可以使用更多功能。

【链表之单链表】