链表的概念

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

链表的分类

链表总共有8种结构：单向有4种，双向有4种，分别与2，3中的组合即可。

单链表基本操作函数

单链表的声明

typedef int SLTDataType;
typedef struct SListNode
{
   
   
    SLTDataType data;    //存储的数据
    struct SListNode* next;   //指向下一个结点的指针
}SListNode;

各个操作总的函数声明

// 动态申请一个节点
SListNode* BuySListNode(SLTDataType x);
// 单链表打印
void SListPrint(SListNode* plist);
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDataType x);
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDataType x);
// 单链表的尾删
void SListPopBack(SListNode** pplist);
// 单链表头删
void SListPopFront(SListNode** pplist);
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDataType x);
// 单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDataType x);
// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos);
// 在pos的前面插入
void SListInsert(SListNode** pplist, SListNode* pos, SLTDataType x);
// 删除pos位置 
void SListErase(SListNode** pplist, SListNode* pos);
//销毁链表
void SLTDestroy(SListNode** pplist);

打印

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

创建新节点

SListNode* BuySListNode(SLTDataType x)
{
   
   
    SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
    if (newnode == NULL)
    {
   
   
        perror("malloc fail");
        exit(-1);
    }
    newnode->data = x;
    newnode->next = NULL;
    return newnode;
}

尾插

void SListPushBack(SListNode** pplist, SLTDataType x)
{
   
   
    //pplist无论什么时候都不为空，因为它是plist的地址
    assert(pplist);
    SListNode* newnode = BuySListNode(x);

    if (*pplist == NULL)
    {
   
   
        *pplist = newnode;
    }
    else
    {
   
   
        //找尾
        SListNode* tail = *pplist;
        while (tail->next != NULL)
        {
   
   
            tail = tail->next;
        }
        tail->next = newnode;
    }
}

头插

void SListPushFront(SListNode** pplist, SLTDataType x)
{
   
   
    assert(pplist);
    SListNode* newnode = BuySListNode(x);
    newnode->next = *pplist;
    *pplist = newnode;
}

尾删

void SListPopBack(SListNode** pplist)
{
   
   
    assert(pplist);
    assert(*pplist);
    //一个节点和多个节点
    if ((*pplist)->next == NULL)
    {
   
   
        free(*pplist);
        *pplist = NULL;
    }
    else
    {
   
   
        //找尾
        SListNode* prev = NULL;
        SListNode* tail = *pplist;
        while (tail->next != NULL)
        {
   
   
            prev = tail;
            tail = tail->next;
        }
        free(tail);
        prev->next = NULL;
    }
}

头删

void SListPopFront(SListNode** pplist)
{
   
   
    assert(pplist);
    assert(*pplist); 
    SListNode* tmp = (*pplist)->next;
    free(*pplist);
    *pplist = tmp;
}

单链表的查找

SListNode* SListFind(SListNode* plist, SLTDataType x)
{
   
   
    SListNode* cur = plist;
    while (cur)
    {
   
   
        if (cur->data == x)
        {
   
   
            return cur;
        }
        else
        {
   
   
            cur = cur->next;
        }
    }
    return NULL;
}

在pos前面插入

void SListInsert(SListNode** pplist, SListNode* pos, SLTDataType x)
{
   
   
    //严格限定pos一定是链表里面的一个有效节点
    assert(pplist);
    assert(pos);
    assert(*pplist);
    if (*pplist == pos)
    {
   
   
        //头插
        SListPushFront(pplist, x);
    }
    else
    {
   
   
        SListNode* prev = *pplist;
        while (prev->next != pos)
        {
   
   
            prev = prev->next;
        }
        SListNode* newnode = BuySListNode(x);
        prev->next = newnode;
        newnode->next = pos;
    }
}

删除pos位置

void SListErase(SListNode** pplist, SListNode* pos)
{
   
   
    assert(pplist);
    assert(*pplist);
    assert(pos);
    if (*pplist == pos)
    {
   
   
        //头删
        SListPopFront(pplist);
    } 
    else
    {
   
   
        SListNode* prev = *pplist;
        while (prev->next != pos)
        {
   
   
            prev = prev->next;
        }
        prev->next = pos->next;
        free(pos);
        pos = NULL;
    }
}

pos位置之后插入

void SListInsertAfter(SListNode* pos, SLTDataType x)
{
   
   
    //为什么这里不用传**pplist?
    //因为这里是往后插，不需要往前找  
    assert(pos);
    SListNode* newnode = BuySListNode(x);
    newnode->next = pos->next;
    pos->next = newnode;
}

删除pos位置之后的值

void SListEraseAfter(SListNode* pos)
{
   
   
    assert(pos);
    assert(pos->next);
    SListNode* tmp = pos->next;
    pos->next = pos->next->next;
    free(tmp);
    tmp = NULL;
}

销毁单链表

void SLTDestroy(SListNode** pplist)
{
   
   
    assert(pplist);
    SListNode* cur = *pplist;
    while (cur)
    {
   
   
        SListNode* next = cur->next;
        free(cur);
        cur = next;
    }
    *pplist = NULL;
}

注意：上面的函数中，有的传的是二级指针，有的是一级指针。我们可以这样理解：因为实参是一级指针，如果我们的操作需要改变实参，那么我们的实参就要传指针的地址，形参就要用二级指针接受。如果只是更改后面的结点，不涉及到头结点，我们只需要传值，因为更改后面的结点是改变结构体，因此只需用一级指针接受。