C语言 -- 链表（企业级，侵入式链表）

目录

节点结构体的实现

初始化链表

插入链表

遍历链表

删除节点、销毁链表

用户test

侵入式链表，内核链表

普通单链表和侵入式单链表的区别在于：

• 普通的单链表的结点指针域指向的是下一个结点的内存首地址；
• 侵入式单链表的结点指针域指向的是下一个结点的指针域成员变量的内存首地址。

节点结构体的实现

节点结构体只维护指针域，用户需预留4个字节空间，供我们帮助连接数据。

//节点结构体
struct LinkNode
{
	//只维护指针域
	struct LinkNode* next;
};
//链表结构体
struct LList
{
	struct LinkNode pHeader; //头结点
	int m_size;  //链表长度
};
//暴露给用户的
typedef void* LinkList;

初始化链表

//初始化链表
LinkList init_LinkList()
{
	struct LList* mylist = malloc(sizeof(struct LList));
	if (mylist == NULL)
		return NULL;

	mylist->m_size = 0;
	mylist->pHeader.next = NULL;

	return mylist;
}

插入链表

//插入链表
void insert_LinkList(LinkList list, int pos, void* data)
{
	if (list == NULL)
		return;
	if (data == NULL)
		return;
	
	struct LList* mylist = list;
	if (pos<0 || pos>mylist->m_size - 1)
		pos = mylist->m_size;

	//取出用户数据的前四个字节空间
	struct LinkNode* myNode = data; //把void*类型的data转为一个指针，即4个字节大小

	//找到待插入位置的前驱节点
	struct LinkNode* pCurrent = &mylist->pHeader;

	for (int i = 0; i < pos; i++)
	{
		pCurrent = pCurrent->next;
	}
	//更新指针指向
	myNode->next = pCurrent->next;
	pCurrent->next = myNode;
	mylist->m_size++;
}

遍历链表

//遍历链表
void foreach_LinkList(LinkList list, void(*myPrint)(void*))
{
	if (NULL == list)
		return;
	struct LList* mylist = list;
	struct LinkNode* pCurrent = mylist->pHeader.next;  //指向第一个有真实数据的节点

	for (int i = 0; i < mylist->m_size; i++)
	{
		//pCurrent就是用户数据的首地址
		myPrint(pCurrent);
		pCurrent = pCurrent->next;
	}
}

删除节点、销毁链表

//删除链表节点之按位置删除
void removeByPos_LinkList(LinkList list, int pos)
{
	if (list == NULL)
		return;
	struct LList* mylist = list;
	if (pos<0 || pos>mylist->m_size - 1)
		return; //无效位置直接返回
	//找到待删除位置的前驱节点的位置
	struct LinkNode* pCurrent = &mylist->pHeader;
	for (int i = 0; i < pos; i++)
	{
		pCurrent = pCurrent->next;
	}
	//PCurrent就是待删除节点的前驱节点
	//利用一个指针记录待删除节点
	struct LinkNode* pDel = pCurrent->next;
	//更改指针的指向
	pCurrent->next = pDel->next;
	
	//free(pDel); //数据本身是用户开辟的，由用户自己管理释放
	mylist->m_size--;
}

//清空链表
// 用户的数据不需要我们来释放，只需要把头结点指向空即可
void clear_LinkList(LinkList list)
{
	if (list == NULL)
		return;
	struct LList* mylist = list;

	mylist->pHeader.next = NULL;
	mylist->m_size = 0;
}

//销毁链表
void destory_LinkList(LinkList list)
{
	if (list == NULL)
		return;

	free(list);
	list = NULL;
}

用户test

//给用户提供接口获取链表长度
int size_LinkList(LinkList list)
{
	if (list == NULL)
		return -1;
	struct LList* mylist = list;
	return mylist->m_size;
}


struct Person
{
	struct LinkNode node; //占用用户数据的前四个字节
	char name[32];
	int age;
};
//回调函数打印
void printPerson(void* data)
{
	struct Person* person = data;
	printf("Name:%s, Age:%d\n", person->name, person->age);
}


void test03()
{
	//初始化链表
	LinkList mylist = init_LinkList();
	//创建数据
	struct Person p1 = { NULL,"aaa",12 };
	struct Person p2 = { NULL,"bbb",13 };
	struct Person p3 = { NULL,"ccc",14 };
	struct Person p4 = { NULL,"ddd",15 };

	//插入数据
	insert_LinkList(mylist, 0, &p1);
	insert_LinkList(mylist, 0, &p2);
	insert_LinkList(mylist, 1, &p3);
	insert_LinkList(mylist, -1, &p4);

	foreach_LinkList(mylist,printPerson);
	printf("--------------------\n");
	removeByPos_LinkList(mylist,1);
	foreach_LinkList(mylist, printPerson);
	printf("--------------------\n");
	printf("链表长度 = %d\n",size_LinkList(mylist));
	clear_LinkList(mylist);
	printf("链表长度 = %d\n", size_LinkList(mylist));
}