# ===== CodeLab: c-linkedlist =====
# 以下代码片段按文章出现顺序拼接, 共 6 段

# ----- 片段 1 (c) -----
#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;            /* 数据域 */
    struct Node *next;   /* 指针域:指向下一个节点 */
} Node;

Node *create_node(int value) {
    Node *p = (Node *)malloc(sizeof(Node));
    if (p == NULL) {
        fprintf(stderr, "malloc failed\n");
        exit(1);
    }
    p->data = value;
    p->next = NULL;
    return p;
}

# ----- 片段 2 (c) -----
Node *insert_head(Node *head, int value) {
    Node *p = create_node(value);
    p->next = head;      /* 新节点指向旧的头 */
    return p;            /* 新节点成为头 */
}

Node *insert_tail(Node *head, int value) {
    Node *p = create_node(value);
    if (head == NULL) {
        return p;        /* 空链表:新节点就是头 */
    }
    Node *cur = head;
    while (cur->next != NULL) {
        cur = cur->next; /* 一路走到最后一个节点 */
    }
    cur->next = p;
    return head;
}

# ----- 片段 3 (c) -----
void print_list(Node *head) {
    for (Node *cur = head; cur != NULL; cur = cur->next) {
        printf("%d -> ", cur->data);
    }
    printf("NULL\n");
}

Node *delete_value(Node *head, int value) {
    Node *prev = NULL;
    Node *cur = head;
    while (cur != NULL && cur->data != value) {
        prev = cur;
        cur = cur->next;
    }
    if (cur == NULL) {
        return head;          /* 没找到,原样返回 */
    }
    if (prev == NULL) {
        head = cur->next;     /* 删除的是头节点 */
    } else {
        prev->next = cur->next;
    }
    free(cur);
    return head;
}

void free_list(Node *head) {
    while (head != NULL) {
        Node *tmp = head;
        head = head->next;
        free(tmp);
    }
}

# ----- 片段 4 (c) -----
#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node *next;
} Node;

Node *create_node(int value) {
    Node *p = (Node *)malloc(sizeof(Node));
    if (p == NULL) {
        fprintf(stderr, "malloc failed\n");
        exit(1);
    }
    p->data = value;
    p->next = NULL;
    return p;
}

Node *insert_head(Node *head, int value) {
    Node *p = create_node(value);
    p->next = head;
    return p;
}

Node *insert_tail(Node *head, int value) {
    Node *p = create_node(value);
    if (head == NULL) return p;
    Node *cur = head;
    while (cur->next != NULL) cur = cur->next;
    cur->next = p;
    return head;
}

void print_list(Node *head) {
    for (Node *cur = head; cur != NULL; cur = cur->next)
        printf("%d -> ", cur->data);
    printf("NULL\n");
}

Node *delete_value(Node *head, int value) {
    Node *prev = NULL, *cur = head;
    while (cur != NULL && cur->data != value) {
        prev = cur;
        cur = cur->next;
    }
    if (cur == NULL) return head;
    if (prev == NULL) head = cur->next;
    else prev->next = cur->next;
    free(cur);
    return head;
}

void free_list(Node *head) {
    while (head != NULL) {
        Node *tmp = head;
        head = head->next;
        free(tmp);
    }
}

int main(void) {
    Node *list = NULL;
    list = insert_head(list, 3);
    list = insert_head(list, 2);
    list = insert_tail(list, 4);
    list = insert_tail(list, 5);
    print_list(list);              /* 2 -> 3 -> 4 -> 5 -> NULL */
    list = delete_value(list, 3);
    print_list(list);              /* 2 -> 4 -> 5 -> NULL */
    free_list(list);
    return 0;
}

# ----- 片段 5 (c) -----
#include <stdio.h>
#include <stdlib.h>

typedef struct DNode {
    int data;
    struct DNode *prev;
    struct DNode *next;
} DNode;

DNode *dlist_insert_head(DNode *head, int value) {
    DNode *p = (DNode *)malloc(sizeof(DNode));
    if (p == NULL) {
        fprintf(stderr, "malloc failed\n");
        exit(1);
    }
    p->data = value;
    p->prev = NULL;
    p->next = head;
    if (head != NULL) {
        head->prev = p;   /* 别忘改旧头的 prev */
    }
    return p;
}

# ----- 片段 6 (c) -----
DNode *dlist_delete(DNode *head, DNode *target) {
    if (target->prev != NULL) {
        target->prev->next = target->next;
    } else {
        head = target->next;   /* 删除的是头节点 */
    }
    if (target->next != NULL) {
        target->next->prev = target->prev;
    }
    free(target);
    return head;
}