通用链表

前言

我们之前写的链表在进行插入操作的时候，数据域中存储的数据我们都是在链表插入函数llist_insert中创建的，这肯定不符合常理。如果用这样一个链表写一个管理系统，每次用户想要插入数据还要自己打开源代码修改吗？

而且还有一个致命的地方，就是我们创建的节点数据域中数据的个数用户也无法进行更改，所以之前写的链表在一些情景下是无法使用的，所以我们需要创建一个通用性强的链表。

通用链表和普通链表

什么是通用性强的链表呢，通过上面问题的阐述，插入节点的数据应该是由用户创建。用户还可以随时增加或减少数据的类型和个数。

数据节点

以有头双向循环链表为例，我们的通用链表也要创建为双向循环的，因为我们要保证我们创建出的链表通用性要强（说的废话😂）。先来看看我们之前写的普通链表，是用LLIST作为链表的节点进行操作的

typedef struct llist_node
{
	int id;
	char name[NAMESIZE];
	int math;
	struct llist_node *prev;
	struct llist_node *next;
}LLIST;

其中存放了数据id、name、math 前继指针prev和后继指针next分别指向前后节点。其中的数据用户是无法更改的，所以我们需要将数据做一些操作，使用户能够随时新增需要的数据。

那如何实现数据能够由用户自定义创建呢，只有用户才能懂自己需要什么数据，什么时候需要这些数据。所以在通用性链表中，节点中的数据就需要由用户自己来搞定啦。所以我们在用户能看到的main函数中创建以下结构体。

#define NAMESIZE 20

struct stu//客户自己创建的数据结体
{
	int id;
	char name[NAMESIZE];
	int math;
	int age;
	int tel;
};

用户已经创建出自己需要的数据了，我们要创建的是一个双向的链表，前驱和后继指针*prev *next是必要的，连接了前后不同的节点，而用户创建的数据怎么和我们包含前驱和后继指针的数据节点结合起来呢，这里我们还是需要使用C语言里的万精油——指针。

我们需要创建一个指针指向用户创建的数据域，这样我们就可以拿到用户所创建的数据了，值得注意的是，因为我们无法得知用户创建的数据域的类型，这里的指针是void *的类型。

struct llist_node//数据节点的结构体
{
	void *data;//data指针指向数据域
	struct llist_node *prev;//prev指针指向前驱
	struct llist_node *next;//next指针指向后继
};

创建头节点

接着我们开始要创建头节点了，我们先看看普通链表创建头节点的llist_create

LLIST *llist_create(void)
{
	LLIST *handler = NULL;//handler指针指向开辟出的头节点

	handler = malloc(sizeof(LLIST));//开辟头节点的空间
	if(handler == NULL)//判断头节点空间是否开辟失败
		return NULL;//开辟失败,结束函数并且返回NULL
	handler->prev = handler->next = handler;
	//让头节点的prev指针和next指针都先指向自己(循环的结构)
	return handler;//返回头节点的地址
}

因为其中数据域和指针域都是放在一起的，所以我们开辟头节点的空间时，直接使用sizeof(LLIST)就可以开辟节点需要的空间。

但是看看上面我们通用链表里创建的数据节点的结构体，两个指针不用说这个void *的大小是什么呢？我们肯定是不知道的，我们得去问创建它的用户，让用户告诉我们他在数据域中创建了多大的数据。

所以我们创建头节点时，就需要用户传他创建的结构体大小了，既然这样头节点就是一个特殊的存在，因为它要把用户传过来的结构体大小size，也要像其他的节点一样有前驱和后继指针去完成链表基本操作。

所以我们需要给通用链表里的头节点专门新建一个结构体，存储用户创建的结构体大小size用来创建数据节点。

typedef struct llist_head//头节点的结构体
{
	int size;//保存客户创建的结构体的大小
	struct llist_node head;//头节点需要使用的指针
}LLIST;

这样当用户创建头节点时，就需要传他所创建的结构体大小size了，不过也简单一样用sizeof(stu)传过来就行。

到这里我们也只是完成准备工作，接下来，我们开始正式创建头节点了。还记得一般链表头节点是如何创建的吗？反正我不记得了，哈哈😝，先来回顾一下

LLIST *llist_create(void)
{
	LLIST *handler = NULL;//handler指针指向开辟出的头节点

	handler = malloc(sizeof(LLIST));//开辟头节点的空间
	if(handler == NULL)//判断头节点空间是否开辟失败
		return NULL;//开辟失败,结束函数并且返回NULL
	handler->prev = handler->next = handler;
	//让头节点的prev指针和next指针都先指向自己(循环的结构)
	return handler;//返回头节点的地址
}

通用链表的结构体和我们的普通链表差距还是比较大的，这里我们慢慢来分析：

跟着普通链表创建头节点思路，同样的我们也是需要有一个指针指向我们开辟出的头节点，先把返回的东西准备好。接着也是开辟头节点的空间，然后要有错误判断（完整的程序必要的环节）。

接下来就有区别了，我们对比结构体，通用链表里多了一个用户传过来的size，需要保存在头节点中留着创建其他节点时使用。而前驱和后继指针该如何操作呢？

在头节点的结构体里还有一个数据节点的结构体，里面存的就是我们要用的指针，那从结构体里面拿东西我们再熟悉不过了。handler->head.prev handler->head.next ，这样就搞定了，我们再把这两个指针指向头节点自己不就行了？🤔听着好像是这么回事，那是和普通链表一样直接指向handler吗？

再来看看我们头节点的结构体，头节点需要用到的指针是llist_node类型的结构体head，如果我们像普通链表一样直接指向handler指向的并不是头节点，而是头节点的结构体。

所以头节点的前驱和后继指针指向的应该是&handler->head最后我们创建头节点的函数就大体完成了：

LLIST *llist_create(int size)
{
	LLIST *handler = NULL;//指向头节点的指针

	handler = malloc(sizeof(LLIST));//为头节点开辟空间
	if(handler == NULL)//判断头节点是否创建失败
		return NULL;//头节点创建失败,结束函数并且返回NULL
	handler->size = size;//把客户结构体大小存储起来
	handler->head.prev = &handler->head;//前驱指针指向自己
	handler->head.next = &handler->head;//后继指针指向自己
	
	return handler;//把指向头节点的指针返回
}

这里为什么是&handler也好理解，handler定义的是一个指针，我们需要取结构体的数据，所以要加&（解释的好像不太好，努力理解一下吧🤓）

插入操作

主要的差别都在上面写出来了，后面增删改查的操作应该都是些细节上的问题，从这里开始我们就把两种链表的代码写在一起进行比较了。（有差别大的地方再细唠，因为我也忘了嘿嘿😏）

int llist_insert(LLIST *handler, const void *data, int mode)
{
    struct llist_node *p = &handler->head;//使用p指针代替handler操作
    struct llist_node *newnode = NULL;//newnode指针新创建的数据节点
    
    newnode = malloc(sizeof(struct llist_node));//开辟数据节点
    if(newnode == NULL)//判断是否开辟失败
        return -1;//数据节点开辟失败 结束函数 返回-1
    
    newnode->data = malloc(handler->size);//开辟数据空间
    if(newnode->data == NULL)//判断数据空间是否开辟失败
    {
        free(newnode);//释放数据节点空间
        return -2;//数据空间开辟失败 结束函数 返回-2
    }
    
    memcpy(newnode->data, data, handler->size);//拷贝数据
    
    switch(mode)
    {
            case: HEADINSERT : break;
            case: TAILINSERT : p = p->prev; break;
            default : free(newnode->data);//释放数据空间
            		  free(newnode);//释放数据节点空间
            		  return -3;//插入模式选择数百 结束函数 返回-3
    }
    newnode->next = p->next;
    newnode->prev = p;
    newnode->next->prev = newnode;
    newnode->prev->next = newnode;

    return 0;
}