30003：单链表所有权

题目

实现由链表对象统一拥有结点的整数单链表，支持两端插入、头部删除和删除首个指定值。

解析

链表同时保存头指针、尾指针和元素数量。空表满足：

head == NULL
tail == NULL
size == 0

非空表的尾结点满足 tail->next == NULL。尾部插入直接连接 tail->next，无需从头遍历；删除头结点或删除指定结点时，如果删掉的是最后一个结点，还要同步更新尾指针。

所有插入都先完成结点分配，再修改链接关系。这样分配失败时链表保持原状。结点地址不通过公开接口交给调用方，销毁链表时可以沿 next 逐个释放。

解析

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdlib.h>

typedef struct IntChain IntChain;

IntChain *int_chain_create(void);
void int_chain_destroy(IntChain *chain);
bool int_chain_push_front(IntChain *chain, int value);
bool int_chain_push_back(IntChain *chain, int value);
bool int_chain_pop_front(IntChain *chain, int *out_value);
bool int_chain_remove_first(IntChain *chain, int value);
size_t int_chain_size(const IntChain *chain);

typedef struct IntNode {
    int value;
    struct IntNode *next;
} IntNode;

struct IntChain {
    IntNode *head;
    IntNode *tail;
    size_t size;
};

IntChain *int_chain_create(void) {
    IntChain *chain = malloc(sizeof *chain);
    if (chain == NULL) {
        return NULL;
    }

    chain->head = NULL;
    chain->tail = NULL;
    chain->size = 0;
    return chain;
}

void int_chain_destroy(IntChain *chain) {
    if (chain == NULL) {
        return;
    }

    IntNode *node = chain->head;
    while (node != NULL) {
        IntNode *next = node->next;
        free(node);
        node = next;
    }
    free(chain);
}

static IntNode *int_node_create(int value) {
    IntNode *node = malloc(sizeof *node);
    if (node == NULL) {
        return NULL;
    }

    node->value = value;
    node->next = NULL;
    return node;
}

bool int_chain_push_front(IntChain *chain, int value) {
    if (chain == NULL || chain->size == SIZE_MAX) {
        return false;
    }

    IntNode *node = int_node_create(value);
    if (node == NULL) {
        return false;
    }

    node->next = chain->head;
    chain->head = node;
    if (chain->tail == NULL) {
        chain->tail = node;
    }
    ++chain->size;
    return true;
}

bool int_chain_push_back(IntChain *chain, int value) {
    if (chain == NULL || chain->size == SIZE_MAX) {
        return false;
    }

    IntNode *node = int_node_create(value);
    if (node == NULL) {
        return false;
    }

    if (chain->tail == NULL) {
        chain->head = node;
    } else {
        chain->tail->next = node;
    }
    chain->tail = node;
    ++chain->size;
    return true;
}

bool int_chain_pop_front(
    IntChain *chain,
    int *out_value
) {
    if (chain == NULL ||
        out_value == NULL ||
        chain->head == NULL) {
        return false;
    }

    IntNode *removed = chain->head;
    int value = removed->value;

    chain->head = removed->next;
    if (chain->head == NULL) {
        chain->tail = NULL;
    }
    --chain->size;
    free(removed);

    *out_value = value;
    return true;
}

bool int_chain_remove_first(
    IntChain *chain,
    int value
) {
    if (chain == NULL) {
        return false;
    }

    IntNode *previous = NULL;
    IntNode *current = chain->head;

    while (current != NULL && current->value != value) {
        previous = current;
        current = current->next;
    }
    if (current == NULL) {
        return false;
    }

    if (previous == NULL) {
        chain->head = current->next;
    } else {
        previous->next = current->next;
    }
    if (chain->tail == current) {
        chain->tail = previous;
    }

    --chain->size;
    free(current);
    return true;
}

size_t int_chain_size(const IntChain *chain) {
    return chain == NULL ? 0 : chain->size;
}

来源与改编

题型借鉴 MIT 6.087 Practical Programming in C 的 Assignment 5，采用 CC BY-NC-SA 4.0；本题补充了不透明接口、尾指针不变式和所有权约定。