C语言中使用双向循环链表

双向循环链表插入和删除都非常方便，c编码中常常使用，下边代码是一个双向循环链表的例子。分为3个文件，list.h,  list.c,  main.c。main.c中是测试代码，将三个文件一起编译得到测试结果。list.h中的list_node_t可以嵌入任何结构体，能很方便的生成链表。而list_for_each_entry_next(pos, head), list_for_each_entry_prev(pos, head)和list_for_each_entry_safe(pos, n, head) 可以方便的实现链表的遍历。

  文件list.h

#ifndef LIST_H
#define LIST_H

typedef struct list_node {
    struct list_node * next, * prev;
} list_node_t;

/** 初始化list_node_t */
#define INIT_LIST_NODE(node) {&(node), &(node)}

/** 得到member成员的偏移量 */
#define member_offset(type, member)    \
    ((size_t)&(((type*)0)->member))

/** 从member_ptr指针计算出其所在type类型的首地址 */
#define type_list_entry(member_ptr, type, member) \
    (type*)((char*)member_ptr - member_offset(type, member))

/** 循环遍历head->next */
#define list_for_each_entry_next(pos, head) \
    for (pos = type_list_entry((head)->next, typeof(*pos), list); \
         pos && (&pos->list != (head)); \
         pos = type_list_entry(pos->list.next, typeof(*pos), list))

/** 循环遍历head->prev */
#define list_for_each_entry_prev(pos, head) \
    for (pos = type_list_entry((head)->prev, typeof(*pos), list); \
         pos && (&pos->list != (head)); \
         pos = type_list_entry(pos->list.prev, typeof(*pos), list))

/** 循环遍历head->next, 删除节点时使用 */
#define list_for_each_entry_safe(pos, n, head) \
    for (pos = type_list_entry((head)->next, typeof(*pos), list), \
         n = type_list_entry((pos->list).next, typeof(*pos), list); \
         pos && (&pos->list != (head)); \
         pos = n, n = type_list_entry(n->list.next, typeof(*pos), list))

/** 初始化list_node_t */
void init_list_node(list_node_t * list);
/** 把new节点插入到prev和next之间 */
void add_node_to_list(list_node_t * new, list_node_t * prev, list_node_t * next);
/** 把new节点插入到链表的第一个 */
void add_node_to_list_head(list_node_t * new, list_node_t * head);
/** 把new节点插入到链表的追后一个 */
void add_node_to_list_tail(list_node_t * new, list_node_t * head);
/** 把node节点从链表中分离出来 */
void detach_node_from_list(list_node_t * node);
/** 判断节点是否为空 */
int list_is_empty(list_node_t * head);

#endif

 文件list.c

#include "list.h"

void init_list_node(list_node_t * list)
{
    list->next = list;
    list->prev = list;
}

void add_node_to_list(list_node_t * new, list_node_t * prev, list_node_t * next)
{
    next->prev = new;
    new->next = next;
    new->prev = prev;
    prev->next = new;
}

void add_node_to_list_head(list_node_t * new, list_node_t * head)
{
    add_node_to_list(new, head, head->next);
}

void add_node_to_list_tail(list_node_t * new, list_node_t * head)
{
    add_node_to_list(new, head->prev, head);
}

void detach_node_from_list(list_node_t * node)
{
    list_node_t * prev = node->prev;
    list_node_t * next = node->next;
    next->prev = prev;
    prev->next = next;
}

int list_is_empty(list_node_t * head)
{
    return head->next == head;
}

  测试文件main.c

#include "list.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct test_info {
    int count;
    list_node_t list;
} test_info_t;

void test_node_list()
{
    /* 新建并初始化头结点 */
    list_node_t list_node_head = INIT_LIST_NODE(list_node_head);

    /* 新建由test_info_t节点构成的链表 */
    int i = 0;
    for(; i < 5; i++) {
        test_info_t * new_node = (test_info_t * )malloc(sizeof(test_info_t));
        memset(new_node, 0, sizeof(test_info_t));

        new_node->count = i;
        add_node_to_list_tail(&new_node->list, &list_node_head);
    }

    /* 从头到尾循环遍历 */
    test_info_t * pos = NULL;
    list_for_each_entry_next(pos, &list_node_head) {
        printf("%d, ", pos->count);
    }
    printf("\n");

    /* 从尾到头循环遍历 */
    pos = NULL;
    list_for_each_entry_prev(pos, &list_node_head) {
        printf("%d, ", pos->count);
    }
    printf("\n");

    /* 删除节点 */
    test_info_t * n = NULL;
    pos = NULL;
    list_for_each_entry_safe(pos, n, &list_node_head) {
        if (2 == pos->count) {
            detach_node_from_list(&pos->list);
            free(pos);
        }
    }

    pos = NULL;
    list_for_each_entry_prev(pos, &list_node_head) {
        printf("%d, ", pos->count);
    }
    printf("\n");
}

int main()
{
    test_node_list();
    return 0;
}

  编译后执行结果：

[root@192 demo]# ./main
0, 1, 2, 3, 4,
4, 3, 2, 1, 0,
4, 3, 1, 0,