数据结构-2.单向链表的实现

节点结构体设计

struct LinkNode
{
	// 数据域
	void* data;
	// 指针域
	struct LinkNode * next;
};

• data：一个 void* 类型的指针，指向节点存储的数据。使用 void* 是为了链表能够存储不同类型的数据。
• next：一个指向下一个 LinkNode 结构体的指针，形成链表的链接。

链表结构体设计

struct LList
{
	//头节点
	struct LinkNode pHeader;
	//链表长度
	int m_size;
};

• pHeader：链表的头节点。虽然 pHeader 本身也是 LinkNode 类型，但它可以作为链表的起始节点，其 next 指针指向第一个实际的数据节点。
• m_size：一个整数，表示链表中节点的数量。

初始化链表

LinkList init_LinkList()
{
	struct LList* myList = malloc(sizeof(struct LList));
	
	if (myList == NULL)
	{
		return NULL;
	}

	myList->pHeader.data = NULL;
	myList->pHeader.next = NULL;
	myList->m_size = 0;

	return myList;
}

• 使用 malloc 分配 struct LList 的内存。
• 初始化头节点的 data 指针为 NULL，next 指针也为 NULL。
• 设置链表长度 m_size 为 0。

插入链表

void insert_LinkList(LinkList list, int pos, void* data)
{
	if (list == NULL) 
	{
		return;
	}
	if (data == NULL)
	{
		return;
	}
	// 将list还原成struct LList数据类型
	struct LList * myList = 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;
	}
	//创建新节点
	struct LinkNode* newNode = malloc(sizeof(struct LinkNode));
	newNode->data = data;
	newNode->next = NULL;

	//建立节点关系

	newNode->next = pCurrent->next;
	pCurrent->next = newNode;

	//更新链表长度
	myList->m_size++;
}

• 检查 list 和 data 是否为空，若为空则返回。
• 如果位置 pos 无效（负数或超出链表当前大小），将位置设置为链表末尾。
• 通过遍历找到插入位置的前驱节点 pCurrent。
• 创建新节点并插入链表中。
• 更新链表长度 m_size。

遍历链表

void foreach_linkList(LinkList list,void(*myForeach)(void *))
{
	if (list == NULL)
	{
		return;
	}

	struct LList* mylist = list;

	struct LinkNode* pCurrent = mylist->pHeader.next;
	for (int i = 0; i < mylist->m_size; i++)
	{
		myForeach(pCurrent->data);
		pCurrent = pCurrent->next;
	}
}

• 检查 list 是否为空，若为空则返回。
• 使用 pCurrent 遍历链表，从头节点的下一个节点开始。
• 对每个节点的数据调用 myForeach，然后移动到下一个节点。