带头双向链表的增删打印等操作实现

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

typedef int LDataType;
//双向带头循环链表的节点
typedef struct ListNode
{
    LDataType _data;
    //指向下一个节点的起始位置
    struct ListNode* _next;
    //指向上一个节点的起始位置
    struct ListNode* _prev;
}ListNode;
//双向带头循环链表
typedef struct List
{
    struct ListNode* _head;
}List;
ListNode* createListNode(LDataType val)
{
    ListNode* node = (ListNode*)malloc(sizeof(ListNode));
    node->_data = val;
    node->_next = NULL;
    node->_prev = NULL;

}

void listInit(List* lst)
{
    if (!lst)return;
    //空链表
    lst->_head = createListNode(0);
    lst->_head->_next = lst->_head->_prev = lst->_head;
}

//尾插 O(1)；
void listPushBack(List* lst, LDataType val)
{
    if (!lst)return;
    struct ListNode* last = lst->_head->_prev;
    struct ListNode* newNode = createListNode(val);
    last->_next = newNode;
    newNode->_prev = last;
    newNode->_next = lst->_head;
    lst->_head->_prev = newNode;
}
//尾删
void listPopBack(List* lst)
{
    if (!lst)return;
    if (lst->_head == lst->_head->_prev)
        return;
    struct ListNode* last = lst->_head->_prev;
    struct ListNode* prev = lst->_head->_prev->_prev;
    free(last);
    prev->_next = lst->_head;
        lst->_head->_prev = prev;
}
//打印
void printList(List* lst)
{
    struct ListNode* cur = lst->_head->_next;
    while (cur != lst->_head)
    {
        printf("%d", cur->_data);
        cur = cur->_next;
    }
    printf("\n");
}
//头插
void listPushFront(List* lst, LDataType val)
{
    if (!lst)return;
    struct ListNode* next = lst->_head->_next;
    struct ListNode* newNode = createListNode(val);
    lst->_head->_next = newNode;
    newNode->_prev = lst->_head;
    newNode->_next = next;
    next->_prev = newNode;
}
//头删
void listPopFront(List* lst)
{
    if (!lst||lst->_head == lst->_head->_next)return;
    struct ListNode* next = lst->_head->_next->_next;
    struct ListNode* prev = lst->_head->_next;
    lst->_head->_next = next;
    next->_prev = lst->_head;
    free(prev);
}
//删除某一节点
void listErase(List* lst,struct ListNode* node)
{
    //不能删除head节点
    if (!lst || lst->_head == node)return;
    struct ListNode* prev = node->_prev;
    struct ListNode* next = node->_next;
    prev->_next = next;
    next->_prev = prev;
    free(node);
}
//某一节点前插入
void listInsert(ListNode* lst, struct ListNode* node, LDataType val)
{
    if (!lst)return;
    struct ListNode* newNode = createListNode(val);
    struct ListNode* prev = node->_prev;
    //prev newNode node
    node->_prev = newNode;
    newNode->_next = node;

    newNode->_prev = prev;
    prev->_next = newNode;
}
listDestroy(List* lst)
{
    if (lst)
    {
        if (lst->_head)
        {
            struct ListNode* cur = lst->_head->_next;
            while (cur != lst->_head)
            {
                struct ListNode* next = cur->_next;
                free(cur);
                cur = next;
            }
            free(lst->_head);
        }
    }
}
void test()
{
    List lst;
    listInit(&lst);
    listPushBack(&lst, 1);
    printList(&lst);
    listPushBack(&lst, 2);
    printList(&lst);
    listPushBack(&lst, 3);
    printList(&lst);
    listPushBack(&lst, 4);
    printList(&lst);
    listPushBack(&lst, 5);
    printList(&lst);
    listPopFront(&lst);
    printList(&lst);
    listPopFront(&lst);
    printList(&lst);
    listPopFront(&lst);
    printList(&lst);
    listPopFront(&lst);
    printList(&lst);
    listPopFront(&lst);
    printList(&lst);

}
int main()
{
    test();

    return 0;
}