#pragma once
#define NULL  0 
#include <stdio.h>
#include <stdlib.h>

typedef int type;

struct node {
    node* next;
    type data;
};

static node* h;
static int n;

node* head();

int size();

void ins_node(node* curr, node* succ);

void del_node(node* curr);

node* tail();

node* before_tail();

node* create_node(type data);

void insert(type data, int nInsHead = 1);

void remove(type data, int nDelSame = 1);

void find(type data, int nFindMulti = 1);

void remove_all_form_head();

void remove_all_from_tail();

void remove_all(int nDelFromHead = 1);

// list.cpp
#include "list.h"

node* head() {
    return h;
}

int size() {
    return n;
}

void ins_node(node* curr, node* succ) {
    if (!curr) {
        succ->next = h;
        h = succ;
    }
    else {
        succ->next = curr->next;
        curr->next = succ;
    }
    n++;
}

void del_node(node* curr) {
    if (!head()) return;
    node* succ = NULL;
    if (!curr) {
        succ = h;
        h = h->next;
    }
    else {
        if (!(succ = curr->next)) return;
        curr->next = succ->next;
    }
    free(succ);
    n--;
}

node* tail() {
    node* tail = NULL;
    for (tail = head(); tail && tail->next; tail = tail->next);
    return tail;
}

node* before_tail() {
    node* before = NULL;
    for (before = head(); before && before->next && before->next->next; before = before->next);
    return before;
}

node* create_node(type data) {
    node* succ = (node*)malloc(sizeof(node));
    if (!succ) return NULL;
    succ->next = NULL;
    succ->data = data;
    return succ;
}

void insert(type data, int nInsHead) {
    node* succ = create_node(data);
    if (!succ) return;
    nInsHead ? ins_node(NULL, succ) : ins_node(tail(), succ);
}

void remove(type data, int nDelSame) {
    if (!head()) return;
    for (node* curr = head(); curr->next; curr = curr->next) {
        while (curr->data == data || curr->next->data == data) {
            if (curr->data == data) {
                del_node(NULL);
                if (!nDelSame || !(curr == head())) return;
            }
            else if (curr->next->data == data) {
                del_node(curr);
                if (!nDelSame || !curr->next) return;
            }
        }
    }
}

void find(type data, int nFindMulti) {
    int cnt = 0;
    for (node* curr = head(); curr; curr = curr->next) {
        if (curr->data == data) {
            cnt++;
            if (!nFindMulti) return;
            printf("data = [%2d] in list and node address = [%p]\n", curr->data, curr);
        }
    }
    printf("find [%d]'s data = [%d]\n", cnt, data);
}

void modify(type found, type data, int nModifyMulti) {
    int cnt = 0;
    for (node* curr = head(); curr; curr = curr->next) {
        if (curr->data == found) {
            cnt++;
            curr->data = data;
            if (!nModifyMulti) return;
        }
    }
    printf("modified [%d]'s datas\n", cnt);
}

void remove_all_form_head() {
    while (size()) del_node(NULL);
    n = 0, h = NULL;
}

void remove_all_from_tail() {
    while (size()) {
        node* p = before_tail();
        if (!p) return;
        del_node(p);
    }
    n = 0, h = NULL;
}

void remove_all(int nDelFromHead) {
    nDelFromHead ? remove_all_form_head() : remove_all_from_tail();
}

#pragma once
#include <stdio.h>
#include <stdlib.h>
#define nil 0

typedef int type;

struct node {
    node* proir;
    node* next;
    type data;
};

node* head();

node* tail();

int size();

void insert(type data, int nInsHead = 1);

void remove(type data, int nDelSame = 1);

void remove_all();

void del_succ(node* curr);

// Dlist.cpp
#include "dlist.h"

static node *h, *t;
static int n;

node* head() { return h; }

node* tail() { return t; }

int size() { return n; }

int empty() { return !n; }

void ins_node(node* curr, node* succ) { // 插入时显然后继节点一定不为空
    if (!curr) {                        // 但是前驱节点有可能是空的
        succ->next = h;
        head() == nil ? 
            h = t = succ : h->proir = succ, h = succ;
    }
    else if (!curr->next) {
        curr->next = succ;
        succ->proir = curr;
        succ->next = nil;
        t = succ;
    }
    else {
        succ->next = curr->next;
        curr->next->proir = succ;
        succ->proir = curr;
        curr->next = succ;
    }
    n++;
}

void del_succ(node* curr) {
    if (!head()) return;
    node* succ = NULL;
    if (!curr) {  // 前驱节点为空，删除表头节点
        succ = h;
        h = h->next;
        h ? h->proir = nil : h = t = nil, n = 0;

    }
    else {  // 否者删除非表头得节点
        if (!(succ = curr->next)) return;  // 后继节点为空，退出
        curr->next = succ->next;           // 前驱的后继是后继的后继
        if (succ->next) succ->next->proir = curr; // 后继的后继为不为空，后继的后继的前驱是前驱节点
        else t = curr;    // 否则，后继就是尾节点，让尾指针指向前驱节点
    }
    if (succ) {     // 后继节点非空才做释放动作
        free(succ);
        n--;
    }
    else {   // 后继为空

        free(curr);
        n--;
        h = t = NULL;  
    }
}

void remove_all() {
    while(size()) {
        node* tmp = h;
        if (h) {
            h = h->next;
            free(tmp);
            n--;
        }
    }
    if (!n) t = h = nil;
} 

node* create_node(type data) {
    node* succ = (node*)malloc(sizeof(node));
    if (!succ) return NULL;
    succ->next = NULL;
    succ->proir = NULL;
    succ->data = data;
    return succ;
}

void insert(type data, int nInsTail) {
    node* succ = create_node(data);
    if (!succ) return;
    !nInsTail ? ins_node(nil, succ) : ins_node(tail(), succ);
}

void remove(type data, int nDelSame) {
    if (!head()) return;
    bool flag = false;
    for (node* p = head(); p->next; p = p->next) {
        while (p->next->data == data) {
                del_succ(p);
                if (!p->next) {
                    flag = true;
                    break;
                }
        }
        if (flag) break;
    }

    for (node* p = head(); p; p = p->next) {
        while (p->data == data) {
                del_succ(NULL);
                p = head();
                if (!p) return;
        }
    }

}