数据结构——单链表(不带头节点)

链表的概念

链表是一种物理存储结构上非联系，非顺序的存储结构，但数据元素的逻辑顺序是通过链表中的指针链接实现的

逻辑结构：

实际物理结构：

每个链表节点都有自己的地址，链表的物理结构实际上是前一个结点保存着下一个结点的地址

所以从上面图中可以看出：

1.链表在逻辑上是连续的，但在物理上不是连续的

2.现实中，每个结点都是从堆中申请的

3.在堆中申请空间，按照一定规则进行分配，所以两次连续的开辟空间可以连续，可能不连续

链表的分类

实际中的链表有多种结构

分别为：

带头节点或不带头结点

单向或双向

循环或不循环

所以链表一共有8种结构

但是常用的只有：不带头节点非循环单链表 和 带头循环双向链表两种

单链表的实现

这里我们介绍的是不带头节点非循环单链表

单链表的结构

一个节点即存放了元素的值，也存放了下一个节点的地址，所以在结构体中，定义一个SLTDataType类型的data，以及结构体的自引用：struct SListNode* next作为指向下一个节点的指针

所以结构体如下：

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

到这里，我们知道了可以通过一个节点找到下一个节点，但是我们如何找到头节点呢？

解决办法就是用一个结构体类型的指针去指向头节点，也解释存放头节点的地址。

所以在接下来的函数中，传这个头指针就可以了

单链表的接口函数

创建节点函数

因为每个节点都需要在堆中开辟，所以可以封装成一个函数，需要调用malloc去开辟空间

同时，在这个函数中，将data的值存放到节点中，因为不知道当前下一个节点的地址，所以next指针赋为NULL，最后返回这个节点的地址

SLTNode* SLTBuyNode(SLTDataType x)
{
  SLTNode* new = (SLTNode*)malloc(sizeof(SLTNode));
  if (new == NULL)
  {
  perror("malloc fail");
  return;
  }
  new->next = NULL;
  new->data = x;
  return new;
}

打印函数

从头节点开始，直到NULL，遍历链表，并且打印出来

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

尾插函数

在实现尾插函数前，如果此时头指针指向的为NULL，在尾插函数中便会改变头指针的指向，也就是改变头指针的值，如果这个函数是传的一级指针的话，虽然在尾插函数中改变了头指针的指向，但在主函数中，头指针的改变并没有改变

传一级指针的情况图如下

所以这样的情况下，就需要传二级指针，将头节点的二级指针pphead传过去，让后通过解引用*pphead去改变头指针的指向

所以在后面的会改变头指针指向的函数中，都需要传二级指针

接下来，实现尾插函数

我们应先创建节点，调用SLTBuyNode函数

接下来还有一点要注意的：

如果此时头指针是空，就说明它后面没有任何节点，所以需要把newnode的节点地址赋值给头指针

如果不为空，找到尾节点，在尾节点的后面插入新节点

这里还需要注意的一个点是：二级指针是头指针的地址，这个地址一定不能为空，如果为空就出问题了，所以在函数开始应用assert断言判断一下pphead是否为空

头节点的值可能为NULL，所以不用断言判断*pphead

void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
  assert(pphead);
  SLTNode* newnode = SLTBuyNode(x);
  if (*pphead == NULL)
  {
  *pphead = newnode;
  }
  else
  {
  SLTNode* tail = *pphead;
  while (tail->next != NULL)
  {
    tail = tail->next;
  }
  tail->next = newnode;
  }
}
1

头插函数

头插函数在头部插入，所以一点会改变头指针的指向，所以仍需传二级指针

然后灵newnode->next等于*pphead，然会再将newnode的值赋给头指针

void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
  assert(pphead);
  SLTNode* newnode = SLTBuyNode(x);
  newnode->next = *pphead;
  *pphead = newnode;
}

头删函数

头删函数一定会改变头指针指向，所以需要传二级指针

头删，一定必须是链表中有节点，如果没有节点，则头删没有意义，如果链表为空，那么头指针的值就为null，所以我们可以通过断言判断*pphead是否为空，同时仍需判断pphead，所以这个函数的开头需要断言2次

因为节点都是动态开辟出来的，所以要用free函数释放，如果直接直接free*pphead，那么后面的节点都找不到了，因为也free掉了next的值

所以可以定义一个head变量指向第一个节点，然后先将head->next赋给*pphead，接下来再free掉head就可以了

void SLTPopFront(SLTNode** pphead)
{
  assert(pphead);
  assert(*pphead);
  SLTNode* head = *pphead;
  *pphead = head->next;
  free(head);
  head = NULL;
}