需求

相信很多项目中用动态内存来管理数据的时候会有用到链表，这比数组等方式方便多了。

网上收集的一个C语言双向链表，适合嵌入式等环境使用。

代码实现

C语言实现的双向通用链表，代码如下：

node_link_list.h

/*************************
* File node_link_list.h
**************************/
 
#ifndef _NODE_LINK_LIST_H
#define _NODE_LINK_LIST_H
 
#ifdef __cplusplus
extern "C" {
#endif
 
#include <stdio.h>
#include <stdbool.h>
#include <string.h>
#include <stdarg.h>
#include <stdlib.h>
 
// 节点,外部创建结构体将其挂在data成员上即可
typedef struct link_list_data_node
{
    void * data;
    struct link_list_data_node * next;
}link_list_data_node_t;
 
 
 // 链表
typedef struct node_link_list
{
    link_list_data_node_t * head; // 头部
    link_list_data_node_t * tail; // 尾部
    unsigned int count; // 节点数
    int (*equal)(void * data1, void * data2);
}node_link_list_t;
 
 
//迭代器
typedef struct node_link_list_iterator
{
    link_list_data_node_t * node;
    unsigned int count;
    unsigned int all_size;
} node_link_list_iterator_t;
 
 
//创建链表
node_link_list_t * create_node_link_list();
  
//创建链表，带有相等参数，用于查找
node_link_list_t* create_search_link_list(int(*equal)(void * a, void * b));
 
//释放链表
void destroy_node_link_list(node_link_list_t * list);
 
//释放链表的同时销毁数据节点，主要用于每个节点单独从分配内存后插入链表数据节点的情况
void destroy_node_link_list2(node_link_list_t * list, bool data_release);
 
void destroy_node_link_list3(node_link_list_t * list, bool data_release, void (*data_node_release)(void *data));
 
//插入在头部
void node_link_list_insert_at_head(node_link_list_t * list, void* data);
 
//插入在尾部
void node_link_list_insert_at_tail(node_link_list_t * list, void* data);
 
//指定位置插入
void node_link_list_insert_at_index(node_link_list_t * list, void * data, unsigned int index);
 
//删除头部
void* node_link_list_remove_at_head(node_link_list_t * list);
 
//删除尾部
void* node_link_list_remove_at_tail(node_link_list_t * list);
 
//删除指定位置的节点
void* node_link_list_remove_at_index(node_link_list_t * list, unsigned int index);
 
//获取链表长度
unsigned int node_link_list_get_size(node_link_list_t * list);
 
//打印
void node_link_list_print(node_link_list_t * list, void(*print)(void * data));
  
// 链表判空
int node_link_list_is_empty(node_link_list_t * list);
 
//取得第一个数据
void* node_link_list_get_data_at_head(node_link_list_t * list);
 
//取得最后一个数据
void* node_link_list_get_data_at_tail(node_link_list_t * list);
 
//获取指定位置数据
void* node_link_list_get_data_at_index(node_link_list_t * list, unsigned int index);
 
//获取指定位置数据
void * node_link_list_get_data_at_index2(node_link_list_t * list, unsigned int index);
 
/*
查找某个数据的位置,如果equal方法为空，比较地址，否则调用equal方法
如果不存在返回-1，如果存在，返回出现的第一个位置
*/
int node_link_list_find_data_index(node_link_list_t * list, void * data);
 
//创建迭代器
node_link_list_iterator_t * create_node_link_list_iterator(node_link_list_t * list);
 
//释放迭代器
void destroy_node_link_list_iterator(node_link_list_iterator_t * iterator);
 
//迭代器是否有下一个元素, 0：表示无下一个元素
int node_link_list_iterator_has_next(node_link_list_iterator_t * iterator);
 
//返回迭代器的下一个元素
void* node_link_list_iterator_next(node_link_list_iterator_t * iterator);
 
//删除对象,返回是否删除成功
int node_link_list_remove_data_object(node_link_list_t * list, void * data);
 
#ifdef __cplusplus
} /* extern "C" */
#endif
#endif // _node_link_listH

node_link_list.h.c

/*************************
*@File node_link_list.h.c
**************************/
#include <string.h>
#include <stdio.h>
#include <stdarg.h>
#include <stdlib.h>
#include "node_link_list.h"
 
#define THIS_FILE  "node_link_list.c"
 
 
//创建链表
node_link_list_t * create_node_link_list()
{
    node_link_list_t * list = NULL;
 
    list = (node_link_list_t *)malloc(sizeof(node_link_list_t));
    if (list != NULL)
    {
        list->count = 0;
        list->head = NULL;
        list->tail = NULL;
        list->equal = NULL;
    }
 
    return list;
}
 
 
//创建链表，带有相等参数，用于查找
node_link_list_t * create_search_link_list(int(*equal)(void * a, void * b))
{
    node_link_list_t * list = NULL;
 
    list = create_node_link_list();
    if (list != NULL)
    {
        list->equal = equal;
    }
 
    return list;
}
 
 
//释放链表
void destroy_node_link_list(node_link_list_t * list)
{
    link_list_data_node_t *node = NULL;
 
    if (list != NULL)
    {
        while (list->head != NULL)
        {
            node = list->head->next;
            free(list->head);
            list->head = node;
        }
 
        free(list);
        list = NULL;
    }
}
 
 
//释放链表的同时销毁数据节点，主要用于每个节点单独从分配内存后插入链表数据节点的情况
void destroy_node_link_list2(node_link_list_t * list, bool data_release)
{
    link_list_data_node_t *node = NULL;
    void *data = NULL;
 
    if (list != NULL)
    {
        while (list->head != NULL)
        {
            node = list->head->next;
 
            if (data_release)
            {
                data = (list->head)->data;
                if (data != NULL)
                {
                    free(data);
                    data = NULL;
                }
            }
 
            free(list->head);
            list->head = node;
        }
 
        free(list);
        list = NULL;
    }
}
 
 
void destroy_node_link_list3(node_link_list_t * list, bool data_release, void (*data_node_release)(void *data))
{
    link_list_data_node_t *node = NULL;
    void *data = NULL;
 
    if (list != NULL)
    {
        while (list->head != NULL)
        {
            node = list->head->next;
 
            if (data_release)
            {
                data = (list->head)->data;
                if (data != NULL)
                {
                    if (data_node_release != NULL)
                    {
                        data_node_release(data);
                        data = NULL;
                    }
                }
            }
 
            free(list->head);
            list->head = node;
        }
 
        free(list);
        list = NULL;
    }
}
 
 
int node_link_list_is_empty(node_link_list_t * list)
{
    if (list == NULL)
    {
       return 1;
    }
    else
    {
        return (list->count == 0);
    }
}
 
 
//插入在头部
void node_link_list_insert_at_head(node_link_list_t * list, void * data)
{
    if (list != NULL)
    {
        link_list_data_node_t * node = (link_list_data_node_t *)malloc(sizeof(link_list_data_node_t));
        if (node != NULL)
        {   
            node->data = data;
            node->next = NULL;
        
            if (list->count > 0)
            {
                node->next = list->head;
                list->head = node;
                //printf("[%s:%d]\n", __FUNCTION__, __LINE__);
            }
            else // 第一个节点
            {
                list->head = node;
                list->tail = node;
                //printf("[%s:%d]\n", __FUNCTION__, __LINE__);
            }
 
            (list->count)++;
        }
    }
}
 
 
//插入在尾部
void node_link_list_insert_at_tail(node_link_list_t * list, void * data)
{
    if (list != NULL)
    {
        link_list_data_node_t * node = (link_list_data_node_t *)malloc(sizeof(link_list_data_node_t));
        if (node != NULL)
        {
            node->data = data;
            node->next = NULL;
            if (list->count > 0)
            {
                list->tail->next = node;
                list->tail = node;
            }
            else
            {
                list->head = node;
                list->tail = node;  
            }
 
            (list->count)++;
        }
    }
}
 
 
//指定位置插入
void node_link_list_insert_at_index(node_link_list_t * list, void * data, unsigned int index)
{
    if (list != NULL)
    {
        if (index == 0)
        {
            node_link_list_insert_at_head(list, data);
            return;
        }
 
        if (index == list->count)
        {
            node_link_list_insert_at_tail(list, data);
            return;
        }
 
        link_list_data_node_t * node = (link_list_data_node_t *)malloc(sizeof(link_list_data_node_t));
        if (node != NULL)
        {
            node->data = data;
            node->next = NULL;
        
            link_list_data_node_t *tmp = list->head;
            unsigned int i = 0;
 
            for (i = 0; i < (index - 1); i++)
            {
                tmp = tmp->next;
            }
 
            node->next = tmp->next;
            tmp->next = node;
        
            (list->count)++;
        }
    }
}
 
 
//删除头部
void* node_link_list_remove_at_head(node_link_list_t * list)
{
    void *data = NULL;
 
    if (list != NULL)
    {
        link_list_data_node_t * tmp = list->head;
        if (tmp != NULL)
        {
            list->head = tmp->next;
            data = tmp->data;
            free(tmp);
 
            (list->count)--;
            if (list->count == 0)
            {
                list->tail = NULL;
            }
        }       
    }
 
    return data;
}
 
 
//删除尾部
void * node_link_list_remove_at_tail(node_link_list_t * list)
{
    void * data = NULL;
 
    if (list != NULL)
    {
        if (list->count == 1)
        {
            return node_link_list_remove_at_head(list);
        }
 
        link_list_data_node_t * tmp = list->head;
        if (tmp != NULL)
        {
            while (tmp->next != list->tail)
            {
                tmp = tmp->next;
            }
        }
 
        if (list-> tail != NULL)
        {
            data = list->tail->data;
            free(list->tail);
 
            tmp->next = NULL;
            list->tail = tmp;
 
            (list->count)--;
        }
    }
 
    return data;
}
 
 
 
//删除
void* node_link_list_remove_at_index(node_link_list_t * list, unsigned int index)
{
    void *data = NULL;
 
    if (list != NULL)
    {
        if (index == 0)
        {
            return node_link_list_remove_at_head(list);
        }
 
        if (index == list->count - 1)
        {
            return node_link_list_remove_at_tail(list);
        }
    
        link_list_data_node_t * p = list->head;
        unsigned int i = 0;
 
        for (i = 0; i < (index - 1); i++)
        {
            p = p->next;
        }
 
        link_list_data_node_t * tmp = p->next;
        if (tmp != NULL)
        {
            p->next = p->next->next;
            data = tmp->data;
            free(tmp);
            
            (list->count)--;
        }
    }
 
    return data;
}
 
 
// 获取链表长度
unsigned int node_link_list_get_size(node_link_list_t * list)
{
    if (list != NULL)
    {
        return list->count;
    }
 
    return 0;
}
 
 
//打印
void node_link_list_print(node_link_list_t * list, void(* print)(void * data))
{
    if (list != NULL)
    {
        link_list_data_node_t * node = list->head;
        while (node != NULL)
        {
            if (print != NULL)
            {
                 (*print)(node->data);
            }   
            node = node->next;
        }
    }
}
 
 
//取得第一个数据
void* node_link_list_get_data_at_head(node_link_list_t * list)
{
    if (list != NULL)
    {
        return list->head->data;
    }
 
    return NULL;
}
 
//取得最后一个数据
void* node_link_list_get_data_at_tail(node_link_list_t * list)
{
    if (list != NULL)
    {
        return list->tail->data;
    }
 
    return NULL;
}
 
 
//获取指定位置数据
void * node_link_list_get_data_at_index(node_link_list_t * list, unsigned int index)
{    
    if (list != NULL)
    { 
        if (index == list->count - 1)
        {
            return node_link_list_get_data_at_tail(list);
        }
        else if (index == 0)
        {
            return node_link_list_get_data_at_head(list);
        } 
 
        link_list_data_node_t * node = list->head;
        unsigned int i = 0;
        
        for (i = 0; i < index; i++)
        {
            node = node->next;
        }
 
        if(node != NULL)
        {
            return node->data;
        }
    }
 
    return NULL;
}
 
//获取指定位置数据
void * node_link_list_get_data_at_index2(node_link_list_t * list, unsigned int index)
{    
    if (list != NULL)
    {
        if(list->count <= index)
        {
            return NULL;
        }
 
        link_list_data_node_t * node = list->head;
        unsigned int i = 0;
        
        for (i = 0; i < index; i++)
        {
            node = node->next;
        }
 
        return node->data;
    }
 
    return NULL;
}
 
 
/*
查找某个数据的位置,如果equal方法为空，比较地址，否则调用equal方法
如果不存在返回-1，如果存在，返回出现的第一个位置
*/
int node_link_list_find_data_index(node_link_list_t * list, void * data)
{
    int pos = 0;
 
    if (list != NULL)
    {
        link_list_data_node_t * node = list->head;
        if (list->equal != NULL)
        {
            while (node != NULL)
            {
                if (node->data == data || (*(list->equal))(node->data, data))
                {
                    return pos;
                }
 
                pos++;
                node = node->next;
            }
        }
        else 
        {
            while (node != NULL)
            {
                if (node->data == data)
                {
                    return pos;
                }
                
                pos++;
                node = node->next;
            }
        }
    }
 
    return -1;
}
 
 
//创建迭代器
node_link_list_iterator_t * create_node_link_list_iterator(node_link_list_t * list)
{
    if (list != NULL)
    {
        node_link_list_iterator_t * iter = (node_link_list_iterator_t *)malloc(sizeof(node_link_list_iterator_t));
        if (iter != NULL)
        {
            iter->node = list->head;
            iter->all_size = list->count;
            iter->count = 0;
 
            return iter;
        }
    }
 
    return NULL;
}
 
 
//释放迭代器
void destroy_node_link_list_iterator(node_link_list_iterator_t * iterator)
{
    if (iterator != NULL)
    {
        free(iterator);
    }
}
 
 
 
//迭代器是否有下一个元素，0：表示无下一个元素
int node_link_list_iterator_has_next(node_link_list_iterator_t * iterator)
{
    if (iterator != NULL)
    {
        return (iterator->count < iterator->all_size);
    }
 
    return 0;
}
 
 
//返回迭代器的下一个元素
void* node_link_list_iterator_next(node_link_list_iterator_t * iterator)
{
    void *data = NULL;
    if (iterator != NULL)
    {
        data = iterator->node->data;
        iterator->node = iterator->node->next;
        (iterator->count)++;  
    }
 
    return data;
}
 
 
//删除对象,返回是否删除成功
int node_link_list_remove_data_object(node_link_list_t * list, void * data)
{
    int ret = 0;
 
    if (list != NULL)
    {
        node_link_list_iterator_t * iter = create_node_link_list_iterator(list);
        if (iter != NULL)
        {
             while (node_link_list_iterator_has_next(iter))
            {
                void* tmp = node_link_list_iterator_next(iter);
                if (data == tmp || 
                   (list->equal != NULL && (*(list->equal))(tmp, data)))
                {
                    ret = 1;
                    break;
                }
            }
 
            if (ret != 0)
            {
                node_link_list_remove_at_index(list, (iter->count - 1));
            }
        }
    }
 
    return ret;
}
 
 
#if defined(TEST) && (TEST==1)
typedef struct my_node
{
    int i;
    char c;
}my_node_t;
 
 
void print(void* p)
{
    my_node_t* data = (my_node_t *)p;
    if (data != NULL)
    {
        printf("data[%d]=%c ", data->i, data->c);
    }
}
 
 
int main(int argc, char *argv[])
{
    const int count =10;
 
    //创建并初始化数据
    my_node_t * data= (my_node_t *)malloc(sizeof(my_node_t) * count);
    if (data == NULL)
    {
        return 0;
    }
 
    //创建链表
    node_link_list_t * list= create_node_link_list();
    if (list == NULL)
    {
        goto END;
    }
 
    int i = 0;
    for (i = 0; i < count; i++)
    {
        data[i].i=i;
        data[i].c=(char)('A'+ i);
        node_link_list_insert_at_tail(list, &data[i]);
    }
    
    node_link_list_print(list, print);
    printf("\n");
 
    //测试三种插入方法
    node_link_list_insert_at_head(list, &data[0]); // 'A'
    node_link_list_insert_at_index(list, &data[1], 1); // 'B'
     node_link_list_insert_at_tail(list, &data[2]); // 'C'
 
    node_link_list_print(list, print);
    printf("\n");
 
    //测试查找
    int index = node_link_list_find_data_index(list, &data[2]);
    printf("index = %d\n", index);
    index = node_link_list_find_data_index(list, &data[4]);
    printf("index = %d\n", index);
  
    //测试使用迭代器输出
    node_link_list_iterator_t * iter = create_node_link_list_iterator(list);
    while(node_link_list_iterator_has_next(iter))
    {
        my_node_t * pp = (my_node_t *)node_link_list_iterator_next(iter);
        if (pp != NULL)
        {
            printf("data[%d]=%c ", pp->i, pp->c);
        }
    }
 
    printf("\n");
 
    node_link_list_remove_at_index(list, 0);
    node_link_list_remove_at_index(list, 1);
    node_link_list_print(list, print);
    printf("\n");
 
END:
    //释放迭代器
    destroy_node_link_list_iterator(iter);
 
    //释放链表
    destroy_node_link_list(list);
 
    //释放数据
    if (data != NULL)
    {
        free(data);
        data = NULL;
    }
 
    return 0;
}
#endif

在代码的头文件中定义一个测试宏，就能启用测试模式

#define TEST 1

如何使用

引入头文件

#include "node_link_list.h"

创建数据节点

//定义节点
typedef struct my_node
{
    int i;
    char c;
}my_node_t;

创建链表

//创建并初始化数据
    my_node_t * data= (my_node_t *)malloc(sizeof(my_node_t) * count);
    if (data == NULL)
    {
        return 0;
    }
 
    //创建链表
    node_link_list_t * list= create_node_link_list();
    if (list == NULL)
    {
        goto END;
    }

完整代码

#include "node_link_list.h"
#include "stdio.h"
//定义节点
typedef struct my_node
{
    int i;
    char c;
}my_node_t;
 
//打印代码
void print(void* p)
{
    my_node_t* data = (my_node_t *)p;
    if (data != NULL)
    {
        printf("data[%d]=%c ", data->i, data->c);
    }
}
 
//主函数
int main(int argc, char *argv[])
{
    const int count =10;
 
    //创建并初始化数据
    my_node_t * data= (my_node_t *)malloc(sizeof(my_node_t) * count);
    if (data == NULL)
    {
        return 0;
    }
 
    //创建链表
    node_link_list_t * list= create_node_link_list();
    if (list == NULL)
    {
        goto END;
    }
 
    int i = 0;
    for (i = 0; i < count; i++)
    {
        data[i].i=i;
        data[i].c=(char)('A'+ i);
        node_link_list_insert_at_tail(list, &data[i]);
    }
    
    node_link_list_print(list, print);
    printf("\n");
 
    //测试三种插入方法
    node_link_list_insert_at_head(list, &data[0]); // 'A'
    node_link_list_insert_at_index(list, &data[1], 1); // 'B'
     node_link_list_insert_at_tail(list, &data[2]); // 'C'
 
    node_link_list_print(list, print);
    printf("\n");
 
    //测试查找
    int index = node_link_list_find_data_index(list, &data[2]);
    printf("index = %d\n", index);
    index = node_link_list_find_data_index(list, &data[4]);
    printf("index = %d\n", index);
  
    //测试使用迭代器输出
    node_link_list_iterator_t * iter = create_node_link_list_iterator(list);
    while(node_link_list_iterator_has_next(iter))
    {
        my_node_t * pp = (my_node_t *)node_link_list_iterator_next(iter);
        if (pp != NULL)
        {
            printf("data[%d]=%c ", pp->i, pp->c);
        }
    }
 
    printf("\n");
 
    node_link_list_remove_at_index(list, 0);
    node_link_list_remove_at_index(list, 1);
    node_link_list_print(list, print);
    printf("\n");
 
END:
    //释放迭代器
    destroy_node_link_list_iterator(iter);
 
    //释放链表
    destroy_node_link_list(list);
 
    //释放数据
    if (data != NULL)
    {
        free(data);
        data = NULL;
    }
 
    return 0;
}