汎用連結リストの実装

汎用連結リストの設計思想は、ノード構造体を定義し、その中に前のノードと次のノードを指すポインタを含むことです。その後、具体的な要件に応じて、ノード構造体内に他のデータ構造をネストすることで、異なる種類の連結リストを実現します。

構造体メンバの先頭アドレス計算

// 構造体メンバmemberが構造体内の最初のメンバアドレスからのオフセット値を計算
#define offset(type, member) \
    ((size_t)&(((type*)0)->member))

// 構造体メンバのポインタから構造体変数の先頭アドレスを計算
#define container_of(ptr, type, member) \
    ((type*)((char*)(ptr) - offsetof(type, member)))

// 構造体ポインタobj、連結リストの先頭ノードhead、構造体メンバ名mem
#define list_for_each_entry(obj, head, member) \
    for (obj = container_of((head)->next, typeof(*obj), member); \
         &obj->member != (head); \
         obj = container_of(obj->member.next, typeof(*obj), member))

汎用連結リストの実装

#include 
#include 
#include 
#include 

// リストの走査
#define list_for_each(pos, head) \
    for (pos = (head)->next; pos != (head); pos = pos->next)

// 構造体メンバmemberが構造体内の最初のメンバアドレスからのオフセット値を計算
#define offset(type, member) \
    ((size_t)&(((type*)0)->member))

// 構造体メンバのポインタから構造体変数の先頭アドレスを計算
#define container_of(ptr, type, member) \
    ((type*)((char*)(ptr) - offsetof(type, member)))

// 構造体ポインタobj、連結リストの先頭ノードhead、構造体メンバ名member
#define list_for_each_entry(obj, head, member) \
    for (obj = container_of((head)->next, typeof(*obj), member); \
         &obj->member != (head); \
         obj = container_of(obj->member.next, typeof(*obj), member))

typedef struct ListNode {
    struct ListNode *prev;
    struct ListNode *next;
} ListNode;

// ノードの作成
ListNode *create_node(void)
{
    ListNode *node = malloc(sizeof(ListNode));
    if (node) {
        node->prev = node;
        node->next = node;
    }
    return node;
}

// リストへのノード追加（内部関数）
void _add_node(ListNode *prev, ListNode *next, ListNode *new_node)
{
    next->prev = new_node;
    new_node->next = next;
    new_node->prev = prev;
    prev->next = new_node;
}

// 先頭にノードを追加
void add_node_head(ListNode *head, ListNode *node)
{
    _add_node(head, head->next, node);
}

// 末尾にノードを追加
void add_node_tail(ListNode *head, ListNode *node)
{
    _add_node(head->prev, head, node);
}

// リストが空か判定
bool is_list_empty(ListNode *head)
{
    return head->next == head;
}

// ノードの削除
void _remove_node(ListNode *node)
{
    node->prev->next = node->next;
    node->next->prev = node->prev;
    node->next = NULL;
    node->prev = NULL;
}

// 先頭ノードの削除
ListNode *remove_node_head(ListNode *head)
{
    if (is_list_empty(head)) return NULL;
    ListNode *node = head->next;
    _remove_node(node);
    return node;
}

// 末尾ノードの削除
ListNode *remove_node_tail(ListNode *head)
{
    if (is_list_empty(head)) return NULL;
    ListNode *node = head->prev;
    _remove_node(node);
    return node;
}

// 指定位置のノードを削除
ListNode *remove_node_at_index(ListNode *head, size_t index)
{
    ListNode *node = head->next;
    for (size_t i = 0; i < index; i++) {
        node = node->next;
        if (node == head) return NULL;
    }
    _remove_node(node);
    return node;
}

// サンプルデータ構造
typedef struct Employee {
    ListNode node;
    char department[30];
    char name[30];
    char gender;
    unsigned short age;
    double salary;
} Employee;

int main(int argc, const char *argv[])
{
    ListNode *head = create_node();
    if (!head) {
        fprintf(stderr, "Failed to create head node\n");
        return 1;
    }

    // 従業員データの追加
    for (int i = 0; i < 10; i++) {
        Employee *emp = malloc(sizeof(Employee));
        if (!emp) {
            fprintf(stderr, "Failed to allocate employee\n");
            continue;
        }
        
        snprintf(emp->department, sizeof(emp->department), "Development");
        snprintf(emp->name, sizeof(emp->name), "Tanaka%d", i);
        emp->gender = i % 2 ? 'F' : 'M';
        emp->age = 25 + (i % 10);
        emp->salary = 200000 + (i * 10000);
        
        add_node_tail(head, &emp->node);
    }

    // リストの走査と表示
    ListNode *pos = NULL;
    list_for_each(pos, head) {
        Employee *emp = container_of(pos, Employee, node);
        printf("%s %s %c %u %.0f\n", 
               emp->department, emp->name, emp->gender, 
               emp->age, emp->salary);
    }

    // メモリ解放（省略）
    return 0;
}