在C中优雅实现循环单链表？

Question

经历了经典的数据结构并停止在链表上.只是实现了一个循环的单链表,但我印象深刻的是这个列表可以用更优雅的方式表达,特别是remove_node函数.记住效率和代码可读性,任何人都可以为单链循环列表提供更简洁有效的解决方案吗？

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


struct node{
    struct node* next;
    int value;
};


struct list{
    struct node* head;
};


struct node* init_node(int value){
    struct node* pnode;
    if (!(pnode = (struct node*)malloc(sizeof(struct node)))){
        return NULL;
    }
    else{
        pnode->value = value;   
    }
    return pnode;
}

struct list* init_list(){
    struct list* plist;
    if (!(plist = (struct list*)malloc(sizeof(struct list)))){
        return NULL;        
    }
    plist->head = NULL;
    return plist;
}


void remove_node(struct list*a plist, int value){

    struct node* current, *temp;
    current = plist->head;
    if (!(current)) return; 
    if ( current->value == value ){
        if (current==current->next){
            plist->head = NULL; 
            free(current);
        }
        else {
            temp = current;
            do {    
                current = current->next;    
            } while (current->next != plist->head);

            current->next = plist->head->next;
            plist->head = current->next;
            free(temp);
        }
    }
    else {
        do {
            if (current->next->value == value){
                temp = current->next;
                current->next = current->next->next;
                free(temp);
            }
            current = current->next;
        } while (current != plist->head);
    }
}

void print_node(struct node* pnode){
    printf("%d %p %p\n", pnode->value, pnode, pnode->next); 
}
void print_list(struct list* plist){

    struct node * current = plist->head;

    if (!(current)) return;
    if (current == plist->head->next){
        print_node(current);
    }
    else{
        do {
            print_node(current);
            current = current->next;

        } while (current != plist->head);
    }

}

void add_node(struct node* pnode,struct list* plist){

    struct node* current;
    struct node* temp;
    if (plist->head == NULL){
        plist->head = pnode;
        plist->head->next = pnode;
    }
    else {
        current = plist->head;
        if (current == plist->head->next){
            plist->head->next = pnode;
            pnode->next = plist->head;      
        }
        else {
            while(current->next!=plist->head)
                current = current->next;

            current->next = pnode;
            pnode->next = plist->head;
        }

    }
}

Answer 1

看一下Linux内核源代码中的循环链表:http://lxr.linux.no/linux+v2.6.36/include/linux/list.h

它的美妙之处在于,您没有特殊的结构来使您的数据适合列表,您只需要struct list_head *在结构中包含要作为列表的结构.用于访问列表中项目的宏将处理偏移计算以从struct list_head指针获取数据.

可以在kernelnewbies.org/FAQ/LinkedLists上找到对内核中使用的链表的更详细说明(对不起,我没有足够的业力来发布两个超链接).

编辑:嗯,列表是一个双链表,而不是像你一样的单链表,但你可以采用这个概念并创建自己的单链表.