链表的概念及结构

链表是一种物理存储结构上非连续、非顺序的存储结构，数是据元素的逻辑顺序是通过链表中的指针链接次序实现的 。C语言结构体指针在这里得到了充分的利用，可以在节点中定义多种数据类型, 并可以根据需要进行增删查改功能.

对于线性表来说，总得有个头有个尾，链表也不例外。我们把链表中第一个结点的存储位置叫做头指针，那么整个链表的存取就必须是从头指针开始进行了。之后的每一个结点，其实就是上一个的后继指针指向的位置。想象一下，最后一个结点，它的指针指向哪里?

最后一个，当然就意味着直接后继不存在了，所以我们规定，线性链表的最后一个结点指针为“空” 用NULL表示

• 单链表的存储结构

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

• 链表存储结构图

注意:

• 图可看出，链式结构在逻辑上是连续的，但是在物理上不一定连续
• 现实中的结点一般都是从malloc堆上申请出来的
• 从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续，也可能不

连续

链表的分类

实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：

• 虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：

1.无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结

构的子结构

2.带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了

• 该章节我们讲解的是无头单向循环链表

链表接口的实现

无头+单向+非循环链表增删查改实现

链表打印

• 链表与顺序表不同，顺序表是通过下标来访问每个元素。而链表是通过结构体存储的指针

指向下一个节点来遍历整个数据的.

void SListPrint(SListNode* plist)
{
  assert(plist); //断言 判断是否为空指针
  SListNode* tmp = plist; 
  while (tmp != NULL)  //遍历整个链表，直到tmp指针指向空
  {
    printf("%d-> ", tmp->data); //打印节点数据
    tmp = tmp->next;  //将指针指向下一个结点
  }
  printf("NULL\n");
}

链表申请节点

• 链表添加一个节点数据时候，每次都要写一段代码，这样做是不是太繁琐了，我们可以封

装一个函数来解决问题，每次添加一个节点时，将结点存放的数据置为需要存放的值，在将结构体存放节点的地址置为NULL, 需要增加节点时调用一下改函数即可。

SListNode* BuySListNode(SLTDateType x)
{
  SListNode* newnode = (SListNode*)malloc(sizeof(SListNode)); //申请一个结构体节点
  //判断是否申请成功
  if (newnode == NULL)
    perror("malloc:\n");
  newnode->data = x;
  newnode->next = NULL;
  //申请成功返回节点
  return newnode;
}

链表尾插

• 在单链表进行尾插时，我们需要遍历整个链表直到找到最后一个节点才可以进行尾插，但

如果此时链表为空时，我们直接插入节点数据即可。

错误代码示例：

相信许多人会写出这样的代码

错误原因:

tail最后找到NULL了，tail和newnode 都是一个临时变量，把newnode给了tail，tail存放的是newnode里面的内容，tail出了作用域就不存在了。把newnode给了tail 并不会链接上链表的节点。最后还会存在内存泄漏. 所有我们这里要使用结构体指针来链接节点,正确写法应该让上一节节点找下一个节点的地址，让tmp->next （next这些节点都是在堆上的，并不会销毁） 找尾 ，将结构体指针指向的尾结点(NULL)指向新结点

正确代码示例

// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x)
{
  //申请一个节点
  SListNode* newnode = BuySListNode(x);
  //当链表还没有节点时为空时，我们直接插入数据即可.
  if (*pplist == NULL)
  {
    *pplist = newnode;
  }
  else
  {
    //进行找尾进行尾插
    //找到指针指向的尾结点(NULL)指向新结点
    SListNode* tmp = *pplist;
    while (tmp->next != NULL)  
    {
      tmp = tmp->next;
    }
    tmp->next = newnode;//将尾结点中存放的指针置为插入结点的地址即可链接上
  }
}

链表头插

• 头插逻辑相对简单.只需要申请一个节点，让节点的指针指向头指针，在把头指针指向申请

节点的位置

// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x)
{
  //申请一个节点
  SListNode* newnode = BuySListNode(x);
  newnode->next = *pplist;
  *pplist = newnode;
}