一、什么是单链表？

单链表是一种链式存取的数据结构，，链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。以“结点的序列”表示的线性表称作线性链表（单链表），单链表是链式存取的结构。简单来说单链表就是一个一个的节点链接起来的链式结构，每个节点里面存储着一个数据和与它链接的下一个节点的（指针）地址。（注意，每一个节点都是同一种结构体类型）

二、单链表的增删查改

2.1 结构体变量的声明

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

2.2 申请新结点

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

2.2 链表的头插

void SListPushFront(SLTNode** pphead, SLTDataType x)
{
  assert(pphead);
  SLTNode* newNode = BuySListNode(x);
  newNode->next = *pphead;
  *pphead = newNode;
}

2.3 链表的尾插

void SListPushBack(SLTNode** pphead, SLTDataType x)
{
  assert(pphead);
  SLTNode* newNode = BuySListNode(x);
  if (*pphead == NULL)
  {
    *pphead = newNode;
  }
  else
  {
    SLTNode* tail = *pphead;
    while (tail->next)
    {
      tail = tail->next;
    }
    tail->next = newNode;
  }
}

2.4 链表的头删

void SListPopFront(SLTNode** pphead)
{
  assert(pphead && *pphead);
  SLTNode* del = *pphead;
  *pphead = (*pphead)->next;
  free(del);
  del = NULL;
}

2.5 链表的尾删

void SListPopBack(SLTNode** pphead)
{
  assert(pphead);
  assert(*pphead);
  if ((*pphead)->next == NULL)
  {
    free(*pphead);
    *pphead = NULL;
  }
  else
  {
    SLTNode* tailPrev = NULL;
    SLTNode* tail = *pphead;
    while (tail->next)
    {
      tailPrev = tail;
      tail = tail->next;
    }
    tailPrev->next = NULL;
    free(tail);
    tail = NULL;
  }
}

2.6 链表的查找

SLTNode* SListFind(SLTNode* pphead, SLTDataType x)
{
  SLTNode* cur = pphead;
  while (cur)
  {
    if (cur->data == x)
    {
      return cur;
    }
    else
    {
      cur = cur->next;
    }
  }
  printf("找不到%d\n",x);
  return NULL;
}

2.7 链表的任意位置后面插入

void SListInsertAfter(SLTNode* pos, SLTDataType x)
{
  assert(pos);
  SLTNode* newNode = BuySListNode(x);
  SLTNode* posNext = pos->next;
  pos->next = newNode;
  newNode->next = posNext;
}

2.8 链表的任意位置后面删除

void SListEraseAfter(SLTNode* pos)
{
  assert(pos && pos->next);
  SLTNode* posNext = pos->next;
  pos->next = posNext->next;
  free(posNext);
  posNext = NULL;
}

2.9 链表的销毁

//建议传二级指针，因为销毁的话需要把这个指向链表的指针置空
//传一级指针无法把指向链表的指针置空
void SListDestroy(SLTNode** pphead)
{
  SLTNode* cur = *pphead;
  while (cur)
  {
    SLTNode* del = cur;
    cur = cur->next;
    free(del);
    del = NULL;
  }
  *pphead = NULL;
}

2.10 链表的打印

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

三、代码汇总

3.1 SLish.h

#pragma once
//SList.h
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
typedef int SLTDataType;
typedef struct SLTNode
{
  SLTDataType data;
  struct SLTNode* next;
}SLTNode;
// 动态申请一个节点
extern SLTNode* BuySListNode(SLTDataType x);
// 单链表打印
extern void SListPrint(SLTNode* phead);
// 单链表尾插
extern void SListPushBack(SLTNode** pphead, SLTDataType x);
// 单链表的头插
extern void SListPushFront(SLTNode** pphead, SLTDataType x);
// 单链表的尾删
extern void SListPopBack(SLTNode** pphead);
// 单链表头删
extern void SListPopFront(SLTNode** pphead);
// 单链表查找
extern SLTNode* SListFind(SLTNode* pphead, SLTDataType x);
// 单链表在pos位置之后插入x
// 分析思考为什么不在pos位置之前插入？
extern void SListInsertAfter(SLTNode* pos, SLTDataType x);
// 单链表删除pos位置之后的值
// 分析思考为什么不删除pos位置？
extern void SListEraseAfter(SLTNode* pos);
// 单链表的销毁
extern void SListDestroy(SLTNode** pphead);

3.2 SLish.c

#define _CRT_SECURE_NO_WARNINGS 1
//Slist.c
#include "SList.h"
SLTNode* BuySListNode(SLTDataType x)
{
  SLTNode* newNode = (SLTNode*)malloc(sizeof(SLTNode));
  if (newNode == NULL)
  {
    perror("malloc fail");
    return NULL;
  }
  else
  {
    newNode->data = x;
    newNode->next = NULL;
    return newNode;
  }
}
void SListPrint(SLTNode* phead)
{
  SLTNode* cur = phead;
  while (cur)
  {
    printf("%d->", cur->data);
    cur = cur->next;
  }
  printf("NULL\n");
}
void SListPushBack(SLTNode** pphead, SLTDataType x)
{
  assert(pphead);
  SLTNode* newNode = BuySListNode(x);
  if (*pphead == NULL)
  {
    *pphead = newNode;
  }
  else
  {
    SLTNode* tail = *pphead;
    while (tail->next)
    {
      tail = tail->next;
    }
    tail->next = newNode;
  }
}
void SListPushFront(SLTNode** pphead, SLTDataType x)
{
  assert(pphead);
  SLTNode* newNode = BuySListNode(x);
  newNode->next = *pphead;
  *pphead = newNode;
}
void SListPopBack(SLTNode** pphead)
{
  assert(pphead);
  assert(*pphead);
  if ((*pphead)->next == NULL)
  {
    free(*pphead);
    *pphead = NULL;
  }
  else
  {
    SLTNode* tailPrev = NULL;
    SLTNode* tail = *pphead;
    while (tail->next)
    {
      tailPrev = tail;
      tail = tail->next;
    }
    tailPrev->next = NULL;
    free(tail);
    tail = NULL;
  }
}
void SListPopFront(SLTNode** pphead)
{
  assert(pphead && *pphead);
  SLTNode* del = *pphead;
  *pphead = (*pphead)->next;
  free(del);
  del = NULL;
}
SLTNode* SListFind(SLTNode* pphead, SLTDataType x)
{
  SLTNode* cur = pphead;
  while (cur)
  {
    if (cur->data == x)
    {
      return cur;
    }
    else
    {
      cur = cur->next;
    }
  }
  printf("找不到%d\n",x);
  return NULL;
}
void SListInsertAfter(SLTNode* pos, SLTDataType x)
{
  assert(pos);
  SLTNode* newNode = BuySListNode(x);
  SLTNode* posNext = pos->next;
  pos->next = newNode;
  newNode->next = posNext;
}
void SListEraseAfter(SLTNode* pos)
{
  assert(pos && pos->next);
  SLTNode* posNext = pos->next;
  pos->next = posNext->next;
  free(posNext);
  posNext = NULL;
}
void SListDestroy(SLTNode** pphead)
{
  SLTNode* cur = *pphead;
  while (cur)
  {
    SLTNode* del = cur;
    cur = cur->next;
    free(del);
    del = NULL;
  }
  *pphead = NULL;
}

3.3 test.c

#define _CRT_SECURE_NO_WARNINGS 1
//test.c
#include "SList.h"
void test_SListPushBack(void)
{
  SLTNode* plist = NULL;
  SListPushBack(&plist, 1);
  SListPushBack(&plist, 2);
  SListPushBack(&plist, 3);
  SListPushBack(&plist, 4);
  SListPushBack(&plist, 5);
  SListPrint(plist);
  SLTNode* ret = SListFind(plist, 1);
  if (ret != NULL)
  {
    printf("找到了，地址为：%p\n", ret);
    SListInsertAfter(ret, 6);
    SListPrint(plist);
  }
  ret = SListFind(plist, 1);
  if (ret != NULL)
  {
    printf("找到了，地址为：%p\n", ret);
    SListInsertAfter(ret, 7);
    SListPrint(plist);
  }
  ret = SListFind(plist, 1);
  if (ret != NULL)
  {
    printf("找到了，地址为：%p\n", ret);
    SListInsertAfter(ret, 8);
    SListPrint(plist);
  }
  ret = SListFind(plist, 1);
  if (ret != NULL)
  {
    printf("找到了，地址为：%p\n", ret);
    SListInsertAfter(ret, 9);
    SListPrint(plist);
  }
  ret = SListFind(plist, 1);
  if (ret != NULL)
  {
    printf("找到了，地址为：%p\n", ret);
    SListInsertAfter(ret, 10);
    SListPrint(plist);
  }
  /*SLTNode* ret = SListFind(plist, 1);
  if (ret != NULL)
  {
    printf("找到了，地址为：%p\n", ret);
    SListEraseAfter(ret);
    SListPrint(plist);
  }
  ret = SListFind(plist, 1);
  if (ret != NULL)
  {
    printf("找到了，地址为：%p\n", ret);
    SListEraseAfter(ret);
    SListPrint(plist);
  }
  ret = SListFind(plist, 1);
  if (ret != NULL)
  {
    printf("找到了，地址为：%p\n", ret);
    SListEraseAfter(ret);
    SListPrint(plist);
  }
  ret = SListFind(plist, 1);
  if (ret != NULL)
  {
    printf("找到了，地址为：%p\n", ret);
    SListEraseAfter(ret);
    SListPrint(plist);
  }*/
  /*ret = SListFind(plist, 1);
  if (ret != NULL)
  {
    printf("找到了，地址为：%p\n", ret);
    SListEraseAfter(ret);
    SListPrint(plist);
  }*/
  //SListInsertAfter(ret, 8);
  /*SListPrint(plist);
  SListPopFront(&plist);
  SListPrint(plist);
  SListPopFront(&plist);
  SListPrint(plist); 
  SListPopFront(&plist);
  SListPrint(plist); 
  SListPopFront(&plist);
  SListPrint(plist); 
  SListPopFront(&plist);
  SListPrint(plist);*/
}
void test_SListPushFront(void)
{
  SLTNode* plist = NULL;
  SListPushFront(&plist, 1);
  SListPushFront(&plist, 2);
  SListPushFront(&plist, 3);
  SListPushFront(&plist, 4);
  SListPushFront(&plist, 5);
  SListPrint(plist);
  SListPopFront(&plist);
  SListPrint(plist);
  SListPopFront(&plist);
  SListPrint(plist);
  SListPopFront(&plist);
  SListPrint(plist);
  SListPopFront(&plist);
  SListPrint(plist);
  SListPopFront(&plist);
  SListPrint(plist);
  /*SListPopFront(&plist);
  SListPrint(plist);*/
  //SListDestroy(plist);
  //SListPrint(plist);
  /*SListPopBack(&plist);
  SListPrint(plist);
  SListPopBack(&plist);
  SListPrint(plist);
  SListPopBack(&plist);
  SListPrint(plist);
  SListPopBack(&plist);
  SListPrint(plist);
  SListPopBack(&plist);
  SListPrint(plist);*/
}
int main()
{
  //test_SListPushBack();
  test_SListPushFront();
  return 0;
}

单链表（增删查改）