#include<stdio.h>
#include<stdlib.h>
#include<string.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;
    return node;
}

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

}

//尾插
void listPushBack(List* lst, LDataType val){
    if (lst == NULL)
        return;
    ListNode* last = lst->_head->_prev;
    ListNode* newNode = createListNode(val);
    last->_next = newNode;
    newNode->_prev = last;
    newNode->_next = lst->_head;
    lst->_head->_prev = newNode;
}

//尾删
void listPopBack(List* lst){
    if (lst == NULL)
        return;
    //空链表
    if (lst->_head->_next == lst->_head)
        return;

    struct ListNode* last = lst->_head->_prev;
    struct ListNode* prev = last->_prev;
    free(last);

    lst->_head->_prev = prev;
    prev->_next = lst->_head;
}

//头插
void listPushFront(List* lst, LDataType val){
    if (lst == NULL)
        return;
    ListNode* next = lst->_head->_next;
    ListNode* newNode = createListNode(val);
    lst->_head->_next = newNode;
    newNode->_prev = lst->_head;
    newNode->_next = next;
    next->_prev = newNode;
}

//头删
void listPopFront(List* lst){
    if (lst == NULL || lst->_head->_next == lst->_head)
        return;

    ListNode* next = lst->_head->_next;
    ListNode* nextnext = next->_next;

    nextnext->_prev = lst->_head;
    lst->_head->_next = nextnext;

    free(next);
     
}

  
//打印链表
void printfList(List* lst){
    ListNode* cur = lst->_head->_next;
    while (cur != lst->_head){
        printf("%d  ", cur->_data);
        cur = cur->_next;
    }
    printf("\n");
}

//头插头删的
void test(){
    List lst;
    listInit(&lst);
    listPushFront(&lst, 4);
    printfList(&lst);
    listPushFront(&lst, 3);
    printfList(&lst);
    listPushFront(&lst, 2);
    printfList(&lst);
    listPushFront(&lst, 1);
    printfList(&lst);

    listPopFront(&lst);
    printfList(&lst);
    listPopFront(&lst);
    printfList(&lst);
    listPopFront(&lst);
    printfList(&lst);
    listPopFront(&lst);
    printfList(&lst);
}

//尾插尾删的
//void test(){
//    List lst;
//    listInit(&lst);
//    listPushBack(&lst, 1);
//    printfList(&lst);
//    listPushBack(&lst, 2);
//    printfList(&lst);
//    listPushBack(&lst, 3);
//    printfList(&lst);
//    listPushBack(&lst, 4);
//    printfList(&lst);
//
//    listPopBack(&lst);
//    printfList(&lst);
//    listPopBack(&lst);
//    printfList(&lst);
//    listPopBack(&lst);
//    printfList(&lst);
//    listPopBack(&lst);
//    printfList(&lst);
//}

int main(){
    test();
    system("pause");
    return 0;
}