双向链表——（有头双向循环链表）

LIst.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
//定义双向链表节点的结构
typedef int LTDataType;
typedef struct ListNode
{
    LTDataType data;
    struct ListNode* next;
    struct ListNode* prev;
}LTNode;
//单链表为空的时候，就是一个空链表。
//双向链表为空时，此时链表中只剩下一个头结点，即哨兵位
// 
// 
//

//声明双向链表中提供的方法

//初始化
void LTInit(LTNode** pphead);

void LTPrint(LTNode* phead);

//尾插
void LTPushBack(LTNode* phead, LTDataType x);
//插入数据之前要先将双向链表插入哨兵位
//哨兵位节点不能被改变，节点的地址也不能发生改变，所以建议采用一级指针

//头插
void LTPushFront(LTNode* phead, LTDataType x);

//头删
void LTPopFront(LTNode* phead);

//尾删
void LTPopBack(LTNode* phead);

//在指定位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x);

//删除指定位置的数据
void LTErase(LTNode* pos);

LTNode* LTFind(LTNode* phead, LTDataType x);

List.c

#define _CRT_SECURE_NO_WARNINGS
#include "List.h"

LTNode* LTBuyNode(LTDataType x)
{
    LTNode* node = (LTNode*)malloc(sizeof(LTNode));
    if (node == NULL)
    {
        perror("malloc fail");
        exit(1);
    }
    //初始化时是否可以将next和prev指针向单链表一样指向空
    //要满足双向循环
    node->data = x;
    node->next = node;
    node->prev = node;
    return node;
}
void LTInit(LTNode** pphead)
{
    //给双向链表创建一个哨兵位
    *pphead = LTBuyNode(-1);
}

void LTPushBack(LTNode* phead, LTDataType x)
{
    assert(phead);
    LTNode* newnode = LTBuyNode(x);

    newnode->prev = phead->prev;
    newnode->next = phead;

    phead->prev->next = newnode;
    phead->prev = newnode;//这两行代码不能交换位置
    //若双向链表为空，仍然成立，因为哨兵位的prev和next都指向自己
}

void LTPrint(LTNode* phead)
{
    LTNode* pcur = phead->next;//打印第一个有效节点
    while (pcur != phead)
    {
        printf("%d->", pcur->data);
        pcur = pcur->next;
    }
    printf("哨兵位\n");
}

void LTPushFront(LTNode* phead, LTDataType x)
{
    assert(phead);
    LTNode* newnode = LTBuyNode(x);
    newnode->prev = phead;
    newnode->next = phead->next;

    phead->next->prev = newnode;
    phead->next = newnode;

}

void LTPopBack(LTNode* phead)
{
    assert(phead&&phead->next != phead);
    //双向链表不需要循环
    LTNode* del = phead->prev;
    //改变指针指向
    del->prev->next = phead;
    phead->prev = del->prev;
    //删除del结点
    free(del);
    del = NULL;
}

void LTPopFront(LTNode* phead)
{
    assert(phead && phead->next != phead);

    LTNode* del = phead->next;
    phead->next = del->next;
    del->next->prev = phead;

    //删除del结点
    free(del);
    del = NULL;
}

LTNode* LTFind(LTNode* phead, LTDataType x)
{
    LTNode* pcur = phead->next;
    while (pcur != phead)
    {
        if (pcur->data == x)
        {
            return pcur;
        }
        pcur = pcur->next;
    }
    return NULL;
}

//在pos指定位置之后插入节点
void LTInsert(LTNode* pos, LTDataType x)
{
    assert(pos);
    //不能调用尾插，没有phead形参
    LTNode* newnode = LTBuyNode(x);
    newnode->prev = pos;
    newnode->next = pos->next;

    pos->next = newnode;
    newnode->next->prev = newnode;
}

//LTErase和LTDestroy参数理论上要传二级，因为我们需要让形参的改变影响实参，但是为了保持接口的一致性才传的一级
//传一级的问题是，当形参phead置为空后，实参plist不会被释放，若继续使用plist会导致野指针
//所以解决方法是调用完以后将plist手动设为空
void LTErase(LTNode* pos)
{
    //pos理论上不能为phead，但是没有参数phead，无法进行校验
    //尽量保证接口一致性
    assert(pos);
    LTNode* del = pos;
    del->prev->next = del->next;
    del->next->prev = del->prev;
    free(del);
    del = NULL;
}

LTNode* LTFind(LTNode* phead, LTDataType x)
{
    assert(phead);
    LTNode* pcur = phead;
    while (pcur != phead)
    {
        LTNode* next = pcur->next;
        free(pcur);//要销毁的是空间，而不是指向空间的指针
        pcur = next;
    }
    free(phead);
    phead = NULL;
}

test.c

#define _CRT_SECURE_NO_WARNINGS
#include "List.h"
void ListTest01()
{
    LTNode* plist = NULL;
    LTInit(&plist);

    LTPushBack(plist, 1);
    LTPrint(plist);
    LTPushBack(plist, 2);
    LTPrint(plist);
    LTPushBack(plist, 3);
    LTPrint(plist);

    /*LTPushFront(plist,5);
    LTPrint(plist);
    LTPushFront(plist, 6);
    LTPrint(plist);
    LTPushFront(plist, 7);
    LTPrint(plist);
    LTPushFront(plist, 8);
    LTPrint(plist);*/

    /*LTPopBack(plist);
    LTPrint(plist);

    LTPopFront(plist);
    LTPrint(plist);*/
    LTNode* find = LTFind(plist, 3);

    LTInsert(find, 66);//先通过查找找到要进行插入的节点，然后再将这个节点传给函数，让函数在她的后面插入
    LTErase(find->next);
    LTDestroy(plist);
    LTPrint(plist);
}
int main()
{
    ListTest01();
    return 0;
}