目录

1. 链表的概念及结构
2. 链表的分类
3. 链表的实现

1. 链表的概念及结构

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

1.2 链表的分类

实际中链表的结构非常多样，以下情况组合起来就有8种链表结构

1. 单向带头非循环链表
2. 单向不带头循环链表
3. 单向不带头非循环链表
4. 双向带头循环链表
5. 双向带头非循环链表
6. 双向不带头循环链表
7. 双向不带头非循环链表
8. 双向循环带头链表

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

1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结

构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

1. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都

是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带
来很多优势，实现反而简单了，后面我们代码实现了就知道了

1.2链表的实现

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<assert.h>

typedef int SLDateType;
typedef struct SList
{
    SLDateType data;
    struct SList* next;
}SLNode;


//打印链表
void SListPrint(SLNode* phead);

//销毁链表
void SListDestroy(SLNode** pphead);

//尾插
void SListPushBack(SLNode** pphead,SLDateType x);

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

//头插
void SListPushFront(SLNode** pphead, SLDateType x);

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

//查找，找到了返回x地址，找不到返回NULL
SLNode* SListFind(SLNode* plist, SLDateType x);

//在pos位置后面插入
void SListInsertAfter(SLNode* pos, SLDateType x);

//删除pos位置后一个
void SListEraseAfter(SLNode* pos);

#include"SList.h"

//打印链表
void SListPrint(SLNode* phead)
{
    SLNode* cur = phead;
    while (cur)
    {
        printf("%d->", cur->data);
        cur = cur->next;
    }
    printf("NULL\n");
}


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


//尾插
void SListPushBack(SLNode** pphead,SLDateType x)
{
    SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
    newnode->data = x;
    newnode->next = NULL;

    SLNode* tail = *pphead;
    //如果链表为空，则直接把新的节点给pphead
    if (*pphead==NULL)
    {
        *pphead = newnode;
    }
    else
    {    
        while (tail->next)
        {
            tail = tail->next;
        }
        tail->next = newnode;
    }

}


//尾删
void SListPopBack(SLNode** pphead)
{
    SLNode* tail = *pphead;
    //prev用来记录tail的前一个节点
    SLNode* prev = NULL;
    //只有一个节点的时候
    if (tail->next==NULL)
    {
        free(tail);
        *pphead = prev;
    }
    //两个及两个以上的节点
    else
    {
        //找尾节点
        while (tail->next)
        {
            prev = tail;
            tail = tail->next;
        }
        //释放尾节点
        free(tail);
        //尾节点前一个节点的next置空
        prev->next = NULL;
    }
}


//头插
void SListPushFront(SLNode** pphead, SLDateType x)
{
    //cur记录头节点位置
    SLNode* cur = *pphead;
    SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
    newnode->data = x;
    //新节点的next指向头节点
    newnode->next = cur;
    //newnode作为新的头节点
    *pphead = newnode;
}


//头删
void SListPopFront(SLNode** pphead)
{
    //链表为空就报错
    assert((*pphead) != NULL);
    SLNode* cur = *pphead;
    SLNode* latter = cur->next;    //用latter存储头结点的后一个节点
    free(cur);
    *pphead = latter;    //设置新头节点
}


//查找,找到返回x地址，找不到返回NULL
SLNode* SListFind(SLNode* plist, SLDateType x)
{
    SLNode* cur = plist;
    while (cur)
    {
        if (cur->data == x)
        {
            return cur;
        }
        cur = cur->next;
    }
    return NULL;
}

//在pos位置后面插入
void SListInsertAfter(SLNode* pos, SLDateType x)
{
    assert(pos != NULL);
    //创建新节点
    SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
    newnode->data = x;
    newnode->next = NULL;
    //在pos后插入
    SLNode* tem = pos->next;
        pos->next = newnode;
        newnode->next = tem;

}


//删除pos位置后一个
void SListEraseAfter(SLNode* pos)
{
    //判断要删的节点是否为空，为空就报错
    assert(pos->next != NULL);
    //因为要删pos下一个结点，所以要把pos下一个节点的下一个节点存储起来防止链表断开
    SLNode* latterTwo = pos->next->next;
    free(pos->next);
    pos->next = latterTwo;

}