单链表专题-阿里云开发者社区

1. 链表的概念及结构

概念：

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

链表是由一个一个节点（结点）组成的，一个节点由两个部分组成：要存储的数据 + 指针（结构体指针）

因此，只要定义节点的结构，就等于定义了链表：

typedef int SLTDataType;
//链表是由节点组成
typedef struct SListNode
{
  SLTDataType data;
  struct SListNode* next;
}SLTNode;

2. 实现单链表

2.1 链表的打印

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

2.2 链表的尾插

void SLTPushBack(SLTNode* phead, SLTDataType x)
{
  SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
  newnode->data = x;
  newnode->next = NULL;
  
  //链表为空，新节点作为phead
  if (NULL == phead)
  {
    phead = newnode;
    return;
  }
  
  //链表不为空，找尾节点
  SLTNode* ptail = phead;
  while (ptail->next)
  {
    ptail = ptail->next;
  }
  //ptail就是尾节点
  ptail->next = newnode;
}

这样写是错误的！当一开始链表为空时，尾插的节点就变成了第一个节点，因此要把phead中的NULL改为第一个节点的地址，所以要传phead的地址，而不是传值。

应该这样写：

//因为头插、尾插、指定位置插入都需要申请新节点，所以单独封装成一个函数
SLTNode* SLTBuyNode(SLTDataType x)
{
  SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
  
  if (NULL == newnode)
  {
    perror("malloc fail!");
    exit(1);
  }
  newnode->data = x;
  newnode->next = NULL;
  return newnode;
}
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
  assert(pphead);
  SLTNode* newnode = SLTBuyNode(x);
  //链表为空，新节点作为phead
  if (NULL == *pphead)
  {
    *pphead = newnode;
    return;
  }
  //链表不为空，找尾节点
  SLTNode* ptail = *pphead;
  while (ptail->next)
  {
    ptail = ptail->next;
  }
  //ptail就是尾节点
  ptail->next = newnode;
}

2.3 链表的头插

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

2.4 链表的尾删

void SLTPopBack(SLTNode** pphead)
{
  assert(pphead);
  //链表不能为空
  assert(*pphead);
  //链表不为空
  //链表只有一个节点，有多个节点
  if (NULL == (*pphead)->next)
  {
    free(*pphead);
    *pphead = NULL;
    return;
  }
  SLTNode* ptail = *pphead;
  SLTNode* prev = NULL;
  while (ptail->next)
  {
    prev = ptail;
    ptail = ptail->next;
  }
  prev->next = NULL;
  //销毁尾节点
  free(ptail);
  ptail = NULL;
}

2.5 链表的头删

void SLTPopFront(SLTNode** pphead)
{
  assert(pphead);
  //链表不能为空
  assert(*pphead);
  //让第二个节点成为新的头
  //把旧的头节点释放掉
  SLTNode* next = (*pphead)->next;//->的优先级高于*
  free(*pphead);
  *pphead = next;
}

2.6 查找

SLTNode* SLTFind(SLTNode** pphead, SLTDataType x)
{
  assert(pphead);
  //遍历链表
  SLTNode* pcur = *pphead;
  while (pcur) //等价于pcur != NULL
  {
    if (pcur->data == x)
    {
      return pcur;
    }
    pcur = pcur->next;
  }
  //没有找到
  return NULL;
}

2.7 在指定位置之前插入数据

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
  assert(pphead);
  assert(pos);
  //要加上链表不能为空
  assert(*pphead);
  SLTNode* newnode = SLTBuyNode(x);
  //pos刚好是头节点
  if (pos == *pphead)
  {
    //头插
    SLTPushFront(pphead, x);
    return;
  }
  //pos不是头节点的情况
  SLTNode* prev = *pphead;
  while (prev->next != pos)
  {
    prev = prev->next;
  }
  //prev -> newnode -> pos
  prev->next = newnode;
  newnode->next = pos;
}

2.8 在指定位置之后插入数据

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

2.9 删除pos节点

void SLTErase(SLTNode** pphead, SLTNode* pos)
{
  assert(pphead);
  assert(*pphead);
  assert(pos);
  //pos刚好是第一个节点，没有前驱节点，执行头删
  if (*pphead == pos)
  {
    //头删
    SLTPopFront(pphead);
    return;
  }
  SLTNode* prev = *pphead;
  while (prev->next != pos)
  {
    prev = prev->next;
  }
  prev->next = pos->next;
  free(pos);
  pos = NULL;
}

2.10 删除pos之后的节点

void SLTEraseAfter(SLTNode* pos)
{
  assert(pos);
  //pos->next不能为空
  assert(pos->next);
  SLTNode* del = pos->next;
  pos->next = pos->next->next;
  free(del);
  del = NULL;
}

2.11 销毁链表

void SListDesTroy(SLTNode** pphead)
{
  assert(pphead);
  assert(*pphead);
  SLTNode* pcur = *pphead;
  while (pcur)
  {
    SLTNode* next = pcur->next;
    free(pcur);
    pcur = next;
  }
  *pphead = NULL;
}

完整代码：

//SList.h
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLTDataType;
//链表是由节点组成
typedef struct SListNode
{
  SLTDataType data;
  struct SListNode* next;
}SLTNode;
void SLTPrint(SLTNode* phead);
//链表的头插、尾插
//void SLTPushBack(SLTNode* phead, SLTDataType x);//err
void SLTPushBack(SLTNode** pphead, SLTDataType x);
void SLTPushFront(SLTNode** pphead, SLTDataType x);
//链表的头删、尾删
void SLTPopBack(SLTNode** pphead);
void SLTPopFront(SLTNode** pphead);
//查找
SLTNode* SLTFind(SLTNode** pphead, SLTDataType x);
//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos);
//销毁链表
void SListDesTroy(SLTNode** pphead);

//SList.c
#include "SList.h"
void SLTPrint(SLTNode* phead)
{
  SLTNode* pcur = phead;
  while (pcur)
  {
    printf("%d->", pcur->data);
    pcur = pcur->next;
  }
  printf("NULL\n");
}
//因为头插、尾插、指定位置插入都需要申请新节点，所以单独封装成一个函数
SLTNode* SLTBuyNode(SLTDataType x)
{
  SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
  
  if (NULL == newnode)
  {
    perror("malloc fail!");
    exit(1);
  }
  newnode->data = x;
  newnode->next = NULL;
  return newnode;
}
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
  assert(pphead);
  SLTNode* newnode = SLTBuyNode(x);
  //链表为空，新节点作为phead
  if (NULL == *pphead)
  {
    *pphead = newnode;
    return;
  }
  //链表不为空，找尾节点
  SLTNode* ptail = *pphead;
  while (ptail->next)
  {
    ptail = ptail->next;
  }
  //ptail就是尾节点
  ptail->next = newnode;
}
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
  assert(pphead);
  SLTNode* newnode = SLTBuyNode(x);
  newnode->next = *pphead;
  *pphead = newnode;
}
void SLTPopBack(SLTNode** pphead)
{
  assert(pphead);
  //链表不能为空
  assert(*pphead);
  //链表不为空
  //链表只有一个节点，有多个节点
  if (NULL == (*pphead)->next)
  {
    free(*pphead);
    *pphead = NULL;
    return;
  }
  SLTNode* ptail = *pphead;
  SLTNode* prev = NULL;
  while (ptail->next)
  {
    prev = ptail;
    ptail = ptail->next;
  }
  prev->next = NULL;
  //销毁尾节点
  free(ptail);
  ptail = NULL;
}
void SLTPopFront(SLTNode** pphead)
{
  assert(pphead);
  //链表不能为空
  assert(*pphead);
  //让第二个节点成为新的头
  //把旧的头节点释放掉
  SLTNode* next = (*pphead)->next;//->的优先级高于*
  free(*pphead);
  *pphead = next;
}
//查找
SLTNode* SLTFind(SLTNode** pphead, SLTDataType x)
{
  assert(pphead);
  //遍历链表
  SLTNode* pcur = *pphead;
  while (pcur) //等价于pcur != NULL
  {
    if (pcur->data == x)
    {
      return pcur;
    }
    pcur = pcur->next;
  }
  //没有找到
  return NULL;
}
//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
  assert(pphead);
  assert(pos);
  //要加上链表不能为空
  assert(*pphead);
  SLTNode* newnode = SLTBuyNode(x);
  //pos刚好是头节点
  if (pos == *pphead)
  {
    //头插
    SLTPushFront(pphead, x);
    return;
  }
  //pos不是头节点的情况
  SLTNode* prev = *pphead;
  while (prev->next != pos)
  {
    prev = prev->next;
  }
  //prev -> newnode -> pos
  prev->next = newnode;
  newnode->next = pos;
}
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
  assert(pos);
  SLTNode* newnode = SLTBuyNode(x);
  newnode->next = pos->next;
  pos->next = newnode;
}
//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
  assert(pphead);
  assert(*pphead);
  assert(pos);
  //pos刚好是第一个节点，没有前驱节点，执行头删
  if (*pphead == pos)
  {
    //头删
    SLTPopFront(pphead);
    return;
  }
  SLTNode* prev = *pphead;
  while (prev->next != pos)
  {
    prev = prev->next;
  }
  prev->next = pos->next;
  free(pos);
  pos = NULL;
}
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos)
{
  assert(pos);
  //pos->next不能为空
  assert(pos->next);
  SLTNode* del = pos->next;
  pos->next = pos->next->next;
  free(del);
  del = NULL;
}
//销毁链表
void SListDesTroy(SLTNode** pphead)
{
  assert(pphead);
  assert(*pphead);
  SLTNode* pcur = *pphead;
  while (pcur)
  {
    SLTNode* next = pcur->next;
    free(pcur);
    pcur = next;
  }
  *pphead = NULL;
}

//Test.c
//int removeElement(int* nums, int numsSize, int val)
//{
//  //定义两个变量
//  int src = 0, dst = 0;
//
//  while (src < numsSize)
//  {
//    //nums[src] == val,src++
//    //否则赋值,src和dst都++
//    if (nums[src] == val)
//    {
//      src++;
//    }
//    else
//    {
//      //说明src指向位置的值不等于val
//      nums[dst] = nums[src];
//      dst++;
//      src++;
//    }
//  }
//
//  //此时dst的值刚好是数组的新长度
//  return dst;
//}
//void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
//{
//  int l1 = m - 1;
//  int l2 = n - 1;
//  int l3 = m + n - 1;
//
//  while (l1 >= 0 && l2 >= 0)
//  {
//    //从后往前比大小
//    if (nums1[l1] > nums2[l2])
//    {
//      nums1[l3--] = nums1[l1--];
//    }
//    else
//    {
//      nums1[l3--] = nums2[l2--];
//    }
//  }
//
//  //要么是l1 < 0，要么是l2 < 0
//  while (l2 >= 0)
//  {
//    nums1[l3--] = nums2[l2--];
//  }
//}
#include "SList.h"
void SListTest01()
{
  //一般不会这样去创建链表，这里只是为了给大家展示链表的打印
  SLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode));
  node1->data = 1;
  SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode));
  node2->data = 2;
  SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode));
  node3->data = 3;
  SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode));
  node4->data = 4;
  node1->next = node2;
  node2->next = node3;
  node3->next = node4;
  node4->next = NULL;
  SLTNode* plist = node1;
  SLTPrint(plist);
}
void SListTest02()
{
  SLTNode* plist = NULL;
  SLTPushBack(&plist, 1);
  SLTPushBack(&plist, 2);
  SLTPushBack(&plist, 3);
  SLTPushBack(&plist, 4);
  SLTPrint(plist);
  //SLTPushBack(NULL, 5);
  //SLTPushFront(&plist, 5);
  //SLTPrint(plist);
  //SLTPushFront(&plist, 6);
  //SLTPrint(plist);
  //SLTPushFront(&plist, 7);
  //SLTPrint(plist);
  SLTPopBack(&plist);
  SLTPrint(plist);
  SLTPopBack(&plist);
  SLTPrint(plist);
  SLTPopBack(&plist);
  SLTPrint(plist);
  SLTPopBack(&plist);
  SLTPrint(plist);
  //SLTPopBack(&plist);
  //SLTPrint(plist);
}
void SListTest03()
{
  SLTNode* plist = NULL;
  SLTPushBack(&plist, 1);
  SLTPushBack(&plist, 2);
  SLTPushBack(&plist, 3);
  SLTPushBack(&plist, 4);
  SLTPrint(plist);
  //头删
  //SLTPopFront(&plist);
  //SLTPrint(plist);
  //SLTPopFront(&plist);
  //SLTPrint(plist);
  //SLTPopFront(&plist);
  //SLTPrint(plist);
  //SLTPopFront(&plist);
  //SLTPrint(plist);
  SLTPopFront(&plist);
  SLTPrint(plist);
  //SLTNode* FindRet = SLTFind(&plist, 3);
  if (FindRet)
  {
    printf("找到了！\n");
  }
  else
  {
    printf("未找到！\n");
  }
  SLTInsert(&plist, FindRet, 100);
  SLTPrint(plist);
  SLTInsertAfter(FindRet, 100);
  SLTPrint(plist);
  删除指定位置的节点
  //SLTErase(&plist, FindRet);
  //SLTPrint(plist);
  SListDesTroy(&plist);
}
int main()
{
  //SListTest01();
  //SListTest02();
  SListTest03();
  return 0;
}

3. 链表的分类

链表的结构非常多样，以下情况组合起来就有8种（2 x 2 x 2）链表结构：

链表说明：

注：

之前代码里写的 SList 意思是 single linked list --> 单链表（不带头单向不循环链表）
刚才在单链表中提到的“头节点”指的是第一个有效的节点；“带头”链表里的“头”指的是无效的节点
“带头”中的“头”：放哨的；头节点：哨兵位（不保存任何有效的数据）

虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：单链表和双向带头循环链表。

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

单链表专题