链表的实现方式 – C 语言（二）

第二种链表的实现方式利用了 C99 中可伸缩数组成员这个特性，该特性使得我们在进行链表内存管理时，减少内存的申请和释次数。

第一种实现方式，我们在创建结点时如下图所示：

结点内存需要 malloc 一次，数据占用的内存也需要 malloc 一次。那么，当该结点销毁时，就需要 free 两次才能将结点彻底删除。利用 c99 的课伸缩数组成员特性，我们就可以如下图的方式来创建结点：

我们可以将结点内存和数据内存只通过一次 malloc 完成申请，销毁结点时也只需要 free 一次。

下面为头文件代码，注意使用可伸缩数组成员时，该成员一个 struct 中只能有一个，并且只能作为 struct 的最有一个成员，另外，包含可伸缩数组成员的 struct 也只能作为其他 struct 的最后一个成员。

#pragma once


struct link_node
{
	// 结点指针
	struct link_node* next;
	// 数据指针
	char data[];
	
};


struct __linklist
{
	struct link_node* rear;
	int ele_size;
	int length;
	struct link_node header;
};

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

函数实现代码：

#include "link_list2.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) + my_list->ele_size);
	if (NULL == new_node)
	{
		return;
	}
	new_node->next = NULL;

	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;
	}

	free(node);
}