链表（C语言）

LinkList.h

#define _CRT_SECURE_N0_WARNINGS 1
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>

typedef int DataType;

typedef struct ListNode {
    DataType data;
    struct ListNode *next;
}ListNode;

void ListInit(ListNode *    *ppFirst)//二级指针 
{
    assert(ppFirst != NULL);
    *ppFirst = NULL;
}

void ListDestory(ListNode **ppFirst)
{
    *ppFirst = NULL;
}

static ListNode * CreateNode(DataType data)
{
    ListNode *newNode = (ListNode *)malloc(sizeof(ListNode));
    assert(newNode);
    newNode->data = data;
    newNode->next = NULL;

    return newNode;
}

void ListPushFront(ListNode **ppFirst, DataType data)
{
    assert(ppFirst != NULL);
    // 考虑特殊情况，链表为空 *ppFirst == NULL

    // 正常情况
    // 1. 指针 vs 指向空间；从堆上申请空间
    ListNode *newNode = CreateNode(data);
    newNode->next = *ppFirst;

    *ppFirst = newNode;
}

void ListPushBack(ListNode **ppFirst, DataType data)
{
    ListNode *newNode = CreateNode(data);

    // 特殊情况，找倒数第一个 -> 至少有一个，所以特殊情况是链表为空
    if (*ppFirst == NULL) {
        *ppFirst = newNode;
        return;
    }

    // 通常情况
    ListNode *cur = *ppFirst;
    while (cur->next != NULL) {
        cur = cur->next;
    }

    // cur 就是最后一个结点
    cur->next = newNode;
}

void ListPopFront(ListNode **ppFirst)
{
    assert(ppFirst != NULL);//变量地址不为NULL
    assert(*ppFirst != NULL);//不能为空链表

    ListNode* del = *ppFirst;
    *ppFirst = del->next;

    free(del);
}

void ListPopBack(ListNode **ppFirst)
{
    assert(ppFirst != NULL);//变量地址不为NULL
    assert(*ppFirst != NULL);//不能为空链表
    //只有一个结点
    if ((*ppFirst)->next == NULL)
    {
        free(*ppFirst);
        *ppFirst = NULL;
        return;
    }

    //正常情况
    ListNode* del;
    ListNode* cur = *ppFirst;
    while (cur->next->next != NULL)
    {
        cur = cur->next;
    }
    del = cur->next;
    cur->next = NULL;
    free(del);
}

//查找
ListNode *SearchListNode(ListNode* first,DataType data)
{
    //顺序查找 去遍历
    for (ListNode* cur = first; cur != NULL; cur = cur->next)
    {
        if (data = cur->data)
            return cur;
    }
    return NULL;
}

//在指定结点前插入 链表不为空&&指定结点存在
void ListInsert(ListNode** ppFirst,ListNode *pos, DataType data)//二级指针 可能是第一个结点
{
    if (*ppFirst == pos)
    {
        ListPushFront(ppFirst, data);
        return;
    }

    //中间插入
    ListNode* cur = *ppFirst;
    while (cur->next != pos)
    {
        cur = cur->next;
    }
    ListNode* newNode = CreateNode(data);
    newNode->next = pos;
    cur->next = newNode;
}

//删除指定结点 链表不为空&&指定结点存在
void ListErase(ListNode **ppFirst, ListNode *pos)
{
    if (*ppFirst == pos)
    {
        ListPopFront(ppFirst);
        return;
    }

    //中间删除
    ListNode *cur = *ppFirst;
    while (cur->next != pos)
        cur = cur->next;
    cur->next = pos->next;

    free(pos);
}


void Test()
{
    ListNode *first;
    ListInit(&first);//经过初始化 first==NULL;更改了first的值 函数中应该传地址。

    ListPushBack(&first, 1);
    ListPushBack(&first, 2);
    ListPushBack(&first, 3);
    
    ListNode *result = SearchListNode(first, 1);

    ListInsert(&first, result, 0);
    ListErase(&first,first);
}

LinkList.c

#define _CRT_SECURE_N0_WARNINGS 1
#include "LinkList.h"

int main()
{
    Test();

    return 0;
}