单向链表（C语言实现）

#include
#include
#include


//节点结构体
struct linkNode
{
	//数据域
	void * data;
	//指针域
	struct linkNode* next;
};

//链表结构体
struct LList 
{ 
	//头结点
	struct linkNode pHeader;

	//链表长度
	int m_Size;
};

//通过void* 隐藏结构体中属性，防止用户更改
typedef void* linkList;

//初始化链表
linkList init_linkList()
{
	//分配内存
	struct LList * mylist = (LList*)malloc(sizeof(struct LList));

	if (mylist == NULL) {
		return NULL;
	}

	//给头结点初始化
	//mylist->pHeader.data =(void*) -1;
	mylist->pHeader.next = NULL;
	mylist->m_Size = 0;

	return mylist;
}


//插入节点
void insert_linkList(linkList list, int pos, void* data)
{
	if (list == NULL) 
	{
		return;
	}
	if (data == NULL) 
	{
		return;
	}

	struct LList* mylist = (LList*)list;
	if (pos<0 || pos>mylist->m_Size) 
	{
		//无效位置
		pos = mylist->m_Size;
	}

	//创建临时节点 通过循环找到待插入位置的前驱节点位置
	struct linkNode* pCurrent = &mylist->pHeader;

	for (int i = 0; i < pos; i++) 
	{
		pCurrent = pCurrent->next;
	}

	//此时 pCurrent就是插入位置的前驱节点

	//创建新节点
	struct linkNode * newNode =(linkNode*) malloc(sizeof(struct linkNode));
	newNode->data = data;
	newNode->next = NULL;

	//建立节点之间的关系
	newNode->next = pCurrent->next;
	pCurrent->next = newNode;

	//更新链表长度
	mylist->m_Size++;

}

//遍历链表
void foreach_linkList(linkList list,void(*myPrint)(void*))
{
	if (list == NULL) 
	{
		return;
	}

	//还原链表真实结构体
	struct LList* mylist = (LList*)list;
	struct linkNode* pCurrent = mylist->pHeader.next;
	for (int i = 0; i < mylist->m_Size; i++)
	{
		myPrint(pCurrent->data);
		pCurrent = pCurrent->next;
	}
}

//删除链表节点，按位置删除
void removeByPos_linkList(linkList list, int pos)
{
	if (list == NULL)
	{
		return;
	}
	struct LList* mylist = (LList*)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);
	pDel = NULL;

	//更新链表长度
	mylist->m_Size--;
}

//删除链表节点，按值删除
void removeByValue_linkList(linkList list,void* data,int(myCompare(void*,void*))) 
{
	if (list == NULL)
	{
		return;
	}
	if (data == NULL)
	{
		return;
	}

	//将list还原真实链表结构体
	struct LList* mylist = (LList*)list;

	//创建两个辅助指针变量
	struct linkNode* pPrev = &mylist->pHeader;
	struct linkNode* pCurrent = mylist->pHeader.next;

	//遍历链表 找用户要删的数据
	for (int i = 0; i < mylist->m_Size; i++)
	{
		//if (data == pCurrent->data)
		if(myCompare(data,pCurrent->data))
		{
			//找到要删除的数据，开始删除
			//更改指针指向 
			pPrev->next=pCurrent->next;

			free(pCurrent);
			pCurrent = NULL;

			mylist->m_Size--;

			break;
		}

		//辅助指针向后移动
		pPrev = pCurrent;
		pCurrent = pCurrent->next;
	}

}

//返回链表长度
int size_linkList(linkList list)
{
	if (list == NULL)
	{
		return -1;
	 }

	//将list还原真实链表结构体
	struct LList* mylist = (LList*)list;

	return mylist->m_Size;

}

//清空链表
void clear_linkList(linkList list)
{
	if (list == NULL)
	{
		return;
	}

	//将list还原真实链表结构体
	struct LList* mylist = (LList*)list;

	struct linkNode* pCurrent = mylist->pHeader.next;

	for (int i = 0; i < mylist->m_Size; i++) 
	{
		//记录下一个节点的位置
		struct linkNode* pNext = pCurrent->next;
		free(pCurrent);
		pCurrent = pNext;
	}

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

//销毁链表
void destory_linkList(linkList list)
{
	if (list == NULL) 
	{
		return;
	}

	//先清空链表，再销毁头结点
	clear_linkList(list);

	free(list);


}

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

//回调函数打印
void printPerson(void* data)
{
	struct Person* person = (Person*)data;
	printf("姓名： %s 年龄：%dn", person->name, person->age);
}

//回调函数删除
int ComparePerson(void* data1, void* data2)
{
	struct Person* p1 = (Person*)data1;
	struct Person* p2 = (Person*)data2;

	return strcmp(p1->name,p2->name)==0&&p1->age==p2->age;
}

//测试链表
void test01() 
{
	//初始化链表
	linkList mylist = init_linkList();

	struct Person p1 = { "赵云",18 };
	struct Person p2 = { "张飞",19 };
	struct Person p3 = { "关羽",20 };
	struct Person p4 = { "刘备",19 };
	struct Person p5 = { "诸葛亮",22 };
	struct Person p6 = { "黄忠",17 };

	insert_linkList(mylist, 0, &p1);
	insert_linkList(mylist, 0, &p2);
	insert_linkList(mylist, 1, &p3);
	insert_linkList(mylist, -1, &p4);
	insert_linkList(mylist, 1, &p5);
	insert_linkList(mylist, 100, &p6);

	//遍历链表
	foreach_linkList(mylist, printPerson);
	printf("链表长度为：%dn", size_linkList(mylist));

	printf("------------------------------");
	printf("删除刘备之后的遍历结果：n");
	removeByPos_linkList(mylist, 4);
	foreach_linkList(mylist,printPerson);
	printf("链表长度为：%dn", size_linkList(mylist));

	printf("------------------------------");
	printf("删除关羽之后的遍历结果：n");
	struct Person p = { "关羽",20 };
	removeByValue_linkList(mylist, &p, ComparePerson);
	foreach_linkList(mylist, printPerson);
	printf("链表长度为：%dn", size_linkList(mylist));
	 
	//清空链表
	printf("------------------------------");
	printf("清空链表之后遍历结果：n");
	clear_linkList(mylist);
	foreach_linkList(mylist, printPerson);
	printf("链表长度为：%dn", size_linkList(mylist));

	//销毁链表
	destory_linkList(mylist);
	mylist = NULL;

}


int main() {

	test01();


	system("pause");
	return 0;
}

企业版本：

#include
#include
#include


//节点结构体设计
struct linkNode
{
	//只维护指针域
	struct linkNode* next;
};

struct LList 
{
	struct linkNode pHeader;	//头结点
	int m_Size;		//链表长度
};

typedef void* linkList;

//初始化链表
linkList init_linkList()
{
	struct LList * mylist = (LList*)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 = (LList*)list;

	if (pos<0 || pos>mylist->m_Size - 1)
	{
		pos = mylist->m_Size;
	}

	//取出用户数据的前4个空间
	struct linkNode* myNode = (linkNode*)data;

	//找到待插入位置的前驱节点
	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 (list == NULL) 
	{
		return;
	}

	struct LList* mylist = (LList*)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 = (LList*)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;
	}

	//记录待删除节点位置
	struct linkNode* pDel = pCurrent->next;

	//重新建立节点之间的关系
	pCurrent->next = pDel->next;

	//链表长度更新
	mylist->m_Size--;

}

//销毁链表
void destory_linkList(linkList list)
{
	if (list == NULL)
	{
		return;
	}

	free(list);
	list = NULL;
}

struct Person
{
	struct linkNode node;
	char name[64];
	int age;
};

void printPerson(void* data)
{
	struct Person* person = (Person*)data;
	printf("姓名：%s 年龄：%dn", person->name, person->age);
}

//测试链表
void test01()
{
	//初始化链表
	linkList mylist = init_linkList();

	//创建数据
	struct Person p1 = { NULL,"aaa",11 };
	struct Person p2 = { NULL,"bbb",22 };
	struct Person p3 = { NULL,"ccc",33 };
	struct Person p4 = { NULL,"ddd",44 };
	struct Person p5 = { NULL,"eee",55 };

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

	//遍历链表
	foreach_linkList(mylist, printPerson);

	//删除bbb的数据
	removeByPos_linkList(mylist, 1);
	printf("----------n");
	foreach_linkList(mylist, printPerson);

	//销毁链表
	destory_linkList(mylist);
	printf("----------n");
	foreach_linkList(mylist, printPerson);



}




int main()
{
	test01();

	system("pause");
	return EXIT_SUCCESS;
}