C语言手撕单链表

一、链表的概念

链表是一种物理存储结构上非连续、非顺序的存储结构，也就是内存存储不是像顺序表那么连续存储，而是以结点的形式一块一块存储在堆上的（用动态内存开辟）。

既然在内存上不是连续存储，那我们如何将这一块一块单独的空间链接起来呢？

我们可以创建一个结构体充当我们的结点，里面分别存放数据（数据域）和下一个结点的地址（指针域），这样我们就可以将一块一块单独的空间链接起来了。

而单链表，顾名思义就是单向链接的链表，效果如同下图

前言：

在讲解单链表的各个接口前，很有必要讲解以下单链表的物理内存到底是如何存储的，先掌握这个，接下来的讲解就会更容易理解

头结点指向的地址就是第一个结点的总地址

第一个结点的指针域指向的是第二个结点的总地址，所以分为两个地址

一个是结点的总地址，另一个是结点总地址里面的next指针存放的指针域的地址，这个指针域的地址又指向了下一个结点的总地址。

看下面的图解内存存储的数据，实际中是没有箭头的，把箭头去掉，才是内存中真正的存储模式

二、接口实现

对数据结构我们一般采用增删查改去实现。

1.  
   #pragma once
2.  
   #include<stdio.h>
3.  
   #include<stdlib.h>
4.  
   #include<assert.h>
5.  
    
6.  
   typedef int SLTDataType;
7.  
    
8.  
   typedef struct SListNode
9.  
   {
10.  
    SLTDataType data;//数据域
11.  
    struct SListNode* next;//指针域
12.  
    }SLTNode;
13.  
     
14.  
    void SLTPrint(SLTNode* phead);
15.  
     
16.  
    SLTNode* BuySListNode(SLTDataType x);
17.  
     
18.  
    void SLTPushBack(SLTNode** phead, SLTDataType x);
19.  
     
20.  
    void SLTPushFront(SLTNode** phead, SLTDataType x);
21.  
     
22.  
    void SLTPopFront(SLTNode** phead);
23.  
     
24.  
    void SLTPopBack(SLTNode** phead);
25.  
     

 1、遍历单链表打印函数

一般需要创建一个临时变量去接收头结点

1.  
   //遍历链表肯定需要头结点
2.  
   void SLTPrint(SLTNode* phead)
3.  
   {
4.  
   SLTNode* cur = phead;//一般需要临时创建变量
5.  
   while (cur != NULL)
6.  
   {
7.  
   printf("%d->", cur->data);
8.  
   cur = cur->next;
9.  
   }
10.  
    printf("NULL");
11.  
    }

2、创建单链表函数

1.  
   SLTNode* BuySListNode(SLTDataType x)
2.  
   {
3.  
   SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
4.  
   if (newnode == NULL)
5.  
   {
6.  
   perror(malloc);
7.  
   exit(-1);
8.  
   }
9.  
   newnode->data = x;
10.  
    newnode->next = NULL;
11.  
    }

3、尾插

需要分情况讨论，

• 如果链表本身是空，直接改变头结点的指针，直接指向新建的结点
• 若不为空，需要找到尾结点

TIP:何时用指针变量，何时用二级指针？

改变结构体本身，需要结构体指针

改变结构体指针，需要结构体指针指针（二级指针），并且要有解引用的操作！

刚才第一种情况，直接将头结点的指针改变成新指针的地址，这种直接改变指针的模式，就需要二级指针，进行解引用才能达到目的。

1.  
   void SLTPushBack(SLTNode** phead, SLTDataType x)
2.  
   {
3.  
   //需要分情况讨论，如果链表本身是空
4.  
   if (*phead == NULL)
5.  
   {
6.  
   SLTNode* newnode = BuySListNode(x);
7.  
   //改变结构体本身，需要结构体的指针
8.  
   //改变结构体指针，需要结构体指针指针（二级指针），并且要有解引用的操作
9.  
   *phead = newnode;
10.  
    }
11.  
    else
12.  
    {
13.  
    //先找尾结点
14.  
    SLTNode* newnode = BuySListNode(x);
15.  
    SLTNode* tail = *phead;
16.  
    while (tail->next != NULL)
17.  
    {
18.  
    tail = tail->next;
19.  
    }
20.  
    tail->next = newnode;
21.  
    }
22.  
     
23.  
    }

4、头插

头插肯定需要二级指针，因为每次头插都要改变头指针指向的位置

1.  
   //头插肯定需要二级指针，因为每次头插都要改变头指针指向的位置
2.  
   void SLTPushFront(SLTNode** phead, SLTDataType x)
3.  
   {
4.  
   SLTNode* newnode = BuySListNode(x);
5.  
   newnode->next = *phead;
6.  
   *phead = newnode;
7.  
   }

5、尾删

分三种情况

• 第一种是链表为空，需要assert断言检查
• 第二种链表中只有一个结点，需要改变结构体指针，因此函数传参也是需要二级指针
• 第三种链表有多于一个的结点，需要先找到尾结点。

1.  
   void SLTPopBack(SLTNode** pphead)
2.  
   {
3.  
   //分三种情况
4.  
   // 第一种就是链表为空
5.  
   assert(*pphead);
6.  
   // 第二种链表只有一个结点，需要改变结构体指针
7.  
   if ((*pphead)->next == NULL)
8.  
   {
9.  
   free(*pphead);
10.  
    pphead = NULL;
11.  
    }
12.  
    //第三种链表多于一个结点
13.  
    else
14.  
    {
15.  
    SLTNode* tail = *pphead;
16.  
    SLTNode* tailprev = NULL;
17.  
    while (tail->next != NULL)
18.  
    {
19.  
    tailprev = tail;
20.  
    tail = tail->next;
21.  
    }
22.  
    free(tail);
23.  
    tailprev->next = NULL;//严格要求尾指针前一个的next指向null
24.  
    }
25.  
    }

6、头删

不需要分类讨论，直接改变头节点的指针指向，但是需要一个临时变量存储结点，便于后面的操作

1.  
   void SLTPopFront(SLTNode** phead)
2.  
   {
3.  
   assert(*phead);
4.  
   SLTNode* newnode = (*phead)->next;
5.  
   free(*phead);
6.  
   *phead = newnode;
7.  
   }

这篇好文章是转载于：学新通技术网