C 实现链表的方式有多种，这篇文章我们将实现一种简单的单向链表。C 语言中由于没有模板技术，实现能够存储不同类型的数据就需要根据实际需求来设计链表。

一种方法是链表可以只存储用户数据的指针，另外一种则将用户数据拷贝到链表中。

如果链表只存储数据的指针，则用户数据的内存由用户自行管理。这是因为用户的数据可能分配在堆上，也可能在栈上。如果用户数据分配在堆上，则需要注意的是，如果用户不小心 delete 了数据，则链表内部存储的数据指针将会变成野指针（悬挂指针），这是一个非常危险的东东。如果用户数据分配到栈上，则要避免链表内部释放用户数据的行为。

当然，我们也可以存储数据本身，这一点实现也非常简单，只要在初始化链表时，告知链表数据类型大小，链表内部根据数据类型大小动态开辟空间，并将用户数据拷贝一份到链表节点中即可。这样，数据空间和链表空间就全部由链表内部管理，即使用户不小心删除原数据也不会影响链表。在这种情况下，对内存的申请和释放操作要额外注意，因为每个节点的创建将会包含 2 次的 malloc 操作，在销毁节点时，也要进行 2 次的 free 操作。

接下来，我们将实现第二种存储方式的链表，即：数据插入时，将用户数据拷贝一份到链表中。

1. 链表头文件

在头文件中，我们链表本身需要的数据。主要包含结点的定义 struct link_node 和链表定义 struct __linklist. 以及链表的操作函数，主要包括：初始化函数、元素添加函数、元素删除函数、链表遍历函数、链表销毁函数，以及一个结点删除函数，该函数为静态函数，用于链表内部，不允许外部访问。

#pragma once

struct link_node
{	
	// 数据指针
	void* data;
	// 结点指针
	struct link_node *next;
};

struct __linklist
{	
	// 头结点
	struct link_node header;
	// 尾指针
	struct link_node *rear;
	// 元素大小
	int ele_size;
	// 结点数量
	int length;
};

typedef void* linklist;

#ifdef __cpluplus
extern "C" {
#endif

	// 初始化链表
	linklist init_linklist(int);
	// 添加元素
	void push_linklist(linklist *, void *);
	// 删除元素
	void remove_linklist(linklist *, void *, int(*)(void *, void *));
	// 遍历元素
	void foreach_linklist(linklist *, void(*)(void *));
	// 销毁链表
	void destroy_linklist(linklist *);
	// 删除结点
	static void free_node(struct link_node *node);

#ifdef __cpluplus
	}
#endif

2. 链表实现文件

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


// 初始化链表
linklist init_linklist(int ele_size)
{
	struct __linklist *list = (struct __linklist *)malloc(sizeof(struct __linklist));
	if (NULL == list)
	{
		return NULL;
	}

	memset(list, 0, sizeof(struct __linklist));
	list->ele_size = ele_size;
	list->rear = &list->header;

	return list;
}

// 添加元素
void push_linklist(linklist *list, void *data)
{
	if (NULL == list || NULL == data)
	{
		return;
	}

	struct __linklist *my_list = (struct __linklist *)list;

	// 创建新的元素结点
	struct link_node *new_node = (struct link_node *)malloc(sizeof(struct link_node));
	if (NULL == new_node)
	{
		return;
	}
	new_node->next = NULL;
	new_node->data = malloc(my_list->ele_size);

	if (NULL == new_node->data)
	{
		return;
	}
	
	memcpy(new_node->data, data, my_list->ele_size);
	new_node->next = NULL;

	// 新的结点添加到链表中
	my_list->rear->next = new_node;
	my_list->rear = new_node;

	++my_list->length;
}

// 删除元素
void remove_linklist(linklist *list, void *data, int(*compare)(void *, void *))
{

	if (NULL == list || NULL == data || NULL == compare)
	{
		return;
	}

	struct __linklist *my_list = (struct __linklist*)list;
	struct link_node *p_prev = &my_list->header;
	struct link_node *p_current = p_prev->next;
	struct link_node *p_next = NULL;

	// 找到要删除的结点
	while (p_current != NULL)
	{
		if (0 == compare(p_current->data, data))
		{
			p_next = p_current->next;
			break;
		}

		p_prev = p_current;
		p_current = p_current->next;
	}

	// 删除结点
	if (NULL == p_current)
	{
		return;
	}

	free_node(p_current);

	// 重新建立结点关系
	p_prev->next = p_next;

	--my_list->length;

}

// 遍历元素
void foreach_linklist(linklist *list, void(*print)(void *))
{
	if (NULL == list || NULL == print)
	{
		return;
	}

	struct __linklist *my_list = (struct __linklist *)list;
	struct link_node *p_current = my_list->header.next;

	while (p_current != NULL)
	{
		print(p_current->data);
		p_current = p_current->next;
	}

	printf("------------------------\n");
}

// 销毁链表
void destroy_linklist(linklist *list) 
{
	if (NULL == list)
	{
		return;
	}

	struct __linklist *my_list = (struct __linklist *)list;
	struct link_node *p_current = my_list->header.next;
	struct link_node *p_next = NULL;

	// 释放结点内存
	while (p_current != NULL)
	{	
		// 缓存下一个结点
		p_next = p_current->next;

		// 删除当前结点
		free_node(p_current);
		
		p_current = p_next;
	}

	free(list);
	list = NULL;
}

static void free_node(struct link_node *node)
{
	if (NULL == node)
	{
		return;
	}

	if (node->data != NULL)
	{
		free(node->data);
		node->data = NULL;
	}

	free(node);
}

3. 链表测试代码

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

struct Person
{
	char name[32];
	int age;
};

void print_person(void *data)
{
	struct Person* person = (struct Person *)data;
	printf("Name: %s Age: %d\n", person->name, person->age);
}

int compare(void *data1, void *data2)
{
	struct Person* person1 = (struct Person*)data1;
	struct Person* person2 = (struct Person*)data2;

	if (0 == strcmp(person1->name, person2->name) && person1->age == person2->age)
	{
		return 0;
	}

	return 1;

}

void test()
{	
	// 初始化链表
	linklist *list = init_linklist(sizeof(struct Person));

	// 初始化数据
	struct Person p1 = { "张三", 18 };
	struct Person p2 = { "李四", 20 };
	struct Person p3 = { "王五", 19 };

	// 数据入链表
	push_linklist(list, &p1);
	push_linklist(list, &p2);
	push_linklist(list, &p3);
	foreach_linklist(list, print_person);

	// 删除元素
	remove_linklist(list, &p3, compare);
	foreach_linklist(list, print_person);

	// 销毁链表
	destroy_linklist(list);
}

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

程序执行结果：