一、为什么会存在链表

因为我们常用的顺序表会存在以下的一些问题：

1. 中间/头部的插入删除，时间复杂度为O(N)
2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到
200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。

针对以上顺序表中存在的问题，有人就设计出了链表这一结构。下面我将就链表中结构最简单的单链表做一个详细的介绍。

二、链表的介绍

2.1链表的概念和结构

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

结构：链表逻辑图和物理图的结合

 从上图我们可以看出：链表的每一个结点都包含数据域和指针域，头结点存储的是第一个节点的地址，最后一个节点的指针域为空指针。从逻辑图上看，就好像每个结点间都有箭头指向下一个结点，从物理图上来看，就是因为每个结点都存储了下一个结点的地址。在链表的结构中需要注意的是：

1.从上图可以看出，链式结构在逻辑上是连续的，但是在物理上不一定连续。

2.现实中的结点一般都是在堆上申请出来的。

3.从堆上申请的空间，是按照一定策略来分配的，两次申请的空间可能连续也可能不连续。

2.2链表的分类

1.单向或双向

2.带头或不带头

3.循环或非循环

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

三、单链表的实现

见以下代码：

#pragma once
#include <stdio.h>
#include <stdlib.h>
typedef int SLTDateType;
typedef struct SListNode
{
	SLTDateType data;
	struct SListNode* next;
}SLTNode;

//打印链表的数据域的内容
void SListPrint(SLTNode* phead);

//尾插
void SListPushBack(SLTNode** pphead, SLTDateType x);

//头插
void SListPushFront(SLTNode** pphead, SLTDateType x);

//尾删
void SListPopBack(SLTNode** pphead);

//头删
void SListPopFront(SLTNode** pphead);

//查找/修改结点的值
SLTNode* SListFind(SLTNode* phead, SLTDateType x);

//在pos位置之前插入一个结点
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x);

//在pos位置之后插入一个结点
void SListInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDateType x);

//删除pos结点
void SListErase(SLTNode** pphead, SLTNode* pos);

//删pos的后一个结点
void SListEraseAfter(SLTNode* pos);

//销毁链表
void SListDestrory(SLTNode** pphead);

#include "Slist.h"

//创建一个新结点
SLTNode* BuyListNode(SLTDateType x)
{
    SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
    if (newnode == NULL)
    {
        printf("malloc fail
");
        exit(-1);
    }
    newnode->data = x;
    newnode->next = NULL;
    return newnode;
}

//打印链表的数据域的内容
void SListPrint(SLTNode* phead)
{
    SLTNode* cur = phead;
    while (cur != NULL)
    {
        printf("%d->", cur->data);
        cur = cur->next;
    }
    printf("NULL
");
}

//尾插
void SListPushBack(SLTNode** pphead, SLTDateType x)
{
    SLTNode* newnode = BuyListNode(x);
    if (*pphead == NULL)
    {
        *pphead = newnode;
    }
    else
    {
        SLTNode* tail = *pphead;
        while (tail->next != NULL)
        {
            tail = tail->next;//找到最后一个结点
        }
        tail->next = newnode;
    }
    
}

//头插
void SListPushFront(SLTNode** pphead, SLTDateType x)
{
    SLTNode* newnode = BuyListNode(x);
    newnode->next = *pphead;
    *pphead = newnode;
}

//尾删
void SListPopBack(SLTNode** pphead)
{
    if (*pphead == NULL)
    {
        return;//链表为空直接返回
    }
    if ((*pphead)->next == NULL)//头结点就是尾节点
    {
        free(*pphead);
        *pphead = NULL;
    }
    else
    {
        SLTNode* tail = *pphead;
        SLTNode* prev = NULL;//最后会走到倒数第二个结点
        while (tail->next != NULL)
        {
            prev = tail;
            tail = tail->next;
        }
        free(tail);
        tail = NULL;
        prev->next = NULL;
    }
}

//头删
void SListPopFront(SLTNode** pphead)
{
    if (*pphead == NULL)//链表为空直接返回
    {
        return;
    }
    SLTNode* next = (*pphead)->next;
    free(*pphead);
    *pphead = next;//头结点指向原来的第二个结点
}

//查找x出现的结点
SLTNode* SListFind(SLTNode* phead, SLTDateType x)
{
    SLTNode* cur = phead;
    while (cur)
    {
        if (cur->data == x)
        {
            return cur;
        }
        else
        {
            cur = cur->next;
        }
    }
    return NULL;
}

//在pos位置之前插入一个结点
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{
    SLTNode* newnode = BuyListNode(x);
    if (*pphead == pos)//头结点就是pos的位置
    {
        //头插
        newnode->next = *pphead;
        *pphead = newnode;
    }
    //找到pos前一个位置
    else
    {
        SLTNode* posPrev = *pphead;
        while (posPrev->next != pos)
        {
            posPrev = posPrev->next;
        }
        posPrev->next = newnode;
        newnode->next = pos;
    }
}

//在pos位置之后插入一个结点
void SListInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{
    SLTNode* newnode = BuyListNode(x);
    //以下两行代码的顺序不能调换，若调换会形成类似互指的问题
    newnode->next = pos->next;
    pos->next = newnode;
}

//删除pos结点
void SListErase(SLTNode** pphead, SLTNode* pos)
{
    if (*pphead == pos)//头删
    {
        SListPopFront(pphead);
    }
    else
    {
        SLTNode* prev = *pphead;
        while (prev->next != pos)
        {
            prev = prev->next;
        }
        prev->next = pos->next;
        free(pos);
    }
}

//删除pos结点后的一个结点
void SListEraseAfter(SLTNode* pos)
{
    SLTNode* next = pos->next;
    pos->next = next->next;
    free(next);
    next = NULL;
}

//销毁链表
void SListDestrory(SLTNode** pphead)
{
    SLTNode* cur = *pphead;
    while (cur)
    {
        SLTNode* next = cur->next;
        free(cur);
        cur = next;
    }
    *pphead = NULL;
}

#include "Slist.h"


void TestSList()
{
    SLTNode* plist = NULL;
    //尾插结点
    SListPushBack(&plist, 1);
    SListPushBack(&plist, 2);
    SListPushBack(&plist, 3);
    SListPushBack(&plist, 4);
    SListPrint(plist);

    //头插结点
    SListPushFront(&plist, 1);
    SListPushFront(&plist, 2);
    SListPushFront(&plist, 3);
    SListPushFront(&plist, 4);
    SListPrint(plist);

    //尾删结点
    SListPopBack(&plist);
    SListPopBack(&plist);
    SListPrint(plist);

    //头删结点
    SListPopFront(&plist);
    SListPrint(plist);

    //查找数值2出现的结点
    SLTNode* pos = SListFind(plist, 2);
    int i = 1;
    while (pos)
    {
        printf("第%d个pos结点：%p->%d
", i++, pos, pos->data);
        pos = SListFind(pos->next, 2);
    }

    //在pos2结点前插入一个结点
    SLTNode* pos2 = SListFind(plist, 1);
    if (pos2)
    {
        SListInsert(&plist, pos2, 30);
    }
    SListPrint(plist);

    //在pos3结点后插入一个结点
    SLTNode* pos3 = SListFind(plist, 3);
    if (pos3)
    {
        SListInsertAfter(&plist, pos3, 20);
    }
    SListPrint(plist);

    //删除pos4结点
    SLTNode* pos4 = SListFind(plist, 2);
    SListErase(&plist, pos4);
    SListPrint(plist);

    //删除pos5结点的后一个结点
    SLTNode* pos5 = SListFind(plist, 3);
    SListEraseAfter(pos5);
    SListPrint(plist);

    //销毁链表
    SListDestrory(&plist);
}

int main()
{
    TestSList();
    return 0;

}

注：有人可能会不明白为什么有的参数传的是二级指针。当你需要对链表进行修改时，参数就需要传二级指针。如果需要对链表进行修改而你传参用的是一级指针，那么就相当于是形参重新开辟了一块空间来存放传过来的一级指针中的值。那么你在函数中对新开辟的空间中做修改就不会改变实参。如果需要在函数中对一级指针做修改，形参就需要传二级指针。