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


typedef struct lnode {
    int data;
    struct lnode *next;
} lnode, *linklist; // 节点 链表

// 定义所有函数的原型
bool empty(linklist l);
bool deletenode(lnode **p);
bool listdelete(linklist *l, int i, int *e);
bool listinsert(linklist *l, int i, int e);
bool insertpriornode(lnode **p, int e);
bool insertnextnode(lnode **s, int e);
bool initlist(linklist *l);
void printlist(linklist l);

// 判断链表是否为空
bool empty(linklist l) {
    if (l->next == NULL)
        return true;
    return false;
}

// 删除指定节点 p
bool deletenode(lnode **p) {
    if (*p == NULL || (*p)->next == NULL)
        return false;
    (*p)->data = (*p)->next->data;
    lnode *s = (*p)->next;
    (*p)->next = s->next;
    free(s);
    return true;
}

// 删除操作：删除表 l 中的第 i 个位置的元素，并且用 e 返回被删除节点的值
bool listdelete(linklist *l, int i, int *e) {
    if (i < 1)
        return false;
    lnode *r;
    r = *l;
    int j = 0;
    while (r != NULL && j < i - 1) { // 找第 i-1 个位置
        r = r->next;
        j++;
    }
    if (r == NULL)
        return false;
    if (r->next == NULL)
        return false;
    *e = r->next->data;
    lnode *s = r->next->next;
    free(r->next);
    r->next = s;
    return true;
}

// 在第 i 个地方插入元素 e 带头节点
bool listinsert(linklist *l, int i, int e) {
    if (i < 1)
        return false;
    lnode *r = *l;
    int j = 0;
    while (r != NULL && j < i - 1) { // 因为要插入第 i 个位置，那就找第 i-1 个节点插入其后面
        r = r->next;
        j++;
    }
    return insertnextnode(&r, e);
}

// 在 p 节点前插入新的节点
bool insertpriornode(lnode **p, int e) {
    if (*p == NULL)
        return false;
    lnode *r = (lnode *)malloc(sizeof(lnode));
    if (r == NULL)
        return false; // 内存分配失败
    r->data = (*p)->data;
    r->next = (*p)->next;
    (*p)->next = r;
    (*p)->data = e;
    return true;
}

// 在 s 节点之后插入新节点
bool insertnextnode(lnode **s, int e) {
    if (*s == NULL)
        return false;
    lnode *r = (lnode *)malloc(sizeof(lnode));
    if (r == NULL)
        return false;
    r->data = e;
    r->next = (*s)->next;
    (*s)->next = r;
    return true;
}

// 初始化带头节点的链表
bool initlist(linklist *l) {
    *l = (lnode *)malloc(sizeof(lnode)); // l 指向头节点
    if (*l == NULL)
        return false;
    (*l)->next = NULL;
    return true;
}

// 打印链表
void printlist(linklist l) {
    lnode *current = l->next;
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }
    printf("\n");
}

int main() {
    linklist l; // 声明一个指向单链表的指针
    initlist(&l); // 初始化链表

    // 测试插入
    listinsert(&l, 1, 10);
    listinsert(&l, 2, 20);
    listinsert(&l, 3, 30);

    // 打印链表
    printf("List after insertions: ");
    printlist(l);

    // 测试删除
    int deletedValue;
    if (listdelete(&l, 2, &deletedValue)) {
        printf("Deleted value: %d\n", deletedValue);
    } else {
        printf("Deletion failed\n");
    }

    // 打印链表
    printf("List after deletion: ");
    printlist(l);

    // 释放链表
    while (l != NULL) {
        lnode *temp = l;
        l = l->next;
        free(temp);
    }

    return 0;
}