C/C++数据结构之单向链表
概述
单向链表是由一系列节点组成的线性集合，每个节点包含两个部分：一部分是存储数据的元素，另一部分是指向下一个节点的指针。与前面介绍的数组不同，单向链表中的元素并不是连续存储在内存中的，而是通过指针相互连接起来。
公司内部的报销审批流程，与单向链表比较类似。员工提交报销申请后，会先后由组长、部门主管审批，最后由财务审核。这是一个典型的单向流程链，每个环节只关心“下一步该交给谁”，而不关心“上一步是谁处理的”。
声明与初始化
在C++中，我们可以通过定义一个结构体来创建单向链表的节点。每个节点通常包括两个成员：一个用于存储数据的数据域，另一个指向下一个节点的指针域。
在下面的示例代码中，Node结构体包含了两个成员：nData用于存放整型数据，pNext是一个指向Node类型的指针，用于链接下一个节点。
struct Node
{int nData; // 数据域struct Node* pNext; // 指针域，指向下一个节点
};单向链表的初始化通常涉及到创建一个新的节点，并将其设置为整个链表的头节点。如果想要创建一个包含初始值的单向链表，我们可以编写一个函数来帮助我们达成这一目标。在下面的示例代码中，我们创建了一个空的单向链表，并在其头部依次插入了三个元素。
void InsertAtBeginning(Node** pHead, int nData)
{Node *pNewNode = new Node();// 设置新节点的数据pNewNode->nData = nData;// 将新节点的pNext指向当前头节点pNewNode->pNext = (*pHead);// 更新头节点为新节点(*pHead) = pNewNode;
}// 初始化一个空链表
struct Node* pHead = NULL;// 依次在头部插入数据
InsertAtBeginning(&pHead, 3);
InsertAtBeginning(&pHead, 2);
InsertAtBeginning(&pHead, 1);基本操作
一旦初始化了单向链表，接下来最重要的任务就是如何有效地对其进行操作，主要包括：访问节点、修改节点、插入节点、删除节点。由于单向链表的非连续存储特性，对节点的操作方式与数组有所不同。
访问节点
访问单向链表中的特定节点，通常需要从头节点开始逐个遍历，直到找到目标节点。比如：要访问第N个节点，我们需要从头节点开始，沿着pNext指针前进N-1次。
在下面的示例函数中，我们接收单向链表的头指针和希望访问的位置作为参数，并返回指向目标节点的指针。如果位置无效或链表为空，则返回NULL。
Node* TraverseToNode(Node* pHead, int nPos)
{if (pHead == NULL || nPos < 0){return NULL;}Node* pNode = pHead;for (int i = 0; i < nPos && pNode != NULL; ++i){pNode = pNode->pNext;}return pNode;
}修改节点
修改单向链表中某个节点的内容相对直接，只需定位到目标节点后，直接更改其nData成员即可。
void ModifyNode(Node* pNode, int nData)
{if (pNode != NULL){pNode->nData = nData;}
}插入节点
除了在单向链表开头插入节点外，还可以在链表的末尾或者指定位置插入新的节点。对于在单向链表末尾插入节点的情况，我们需要先遍历到链表的最后一个节点，然后在其后面添加新节点。具体实现，可参考下面的示例代码。
void AppendNode(Node** pHead, int nData)
{Node *pNewNode = new Node();pNewNode->nData = nData;pNewNode->pNext = NULL;// 如果链表为空，直接将新节点设为头节点if(*pHead == NULL){*pHead = pNewNode;return;}Node* pLast = *pHead;while(pLast->pNext != NULL){pLast = pLast->pNext;}pLast->pNext = pNewNode;
}要在单向链表中间插入节点，首先需要找到插入点前的一个节点。然后，调整指针使其指向新节点，同时让新节点指向原链表中的后续节点。具体实现，可参考下面的示例代码。
void InsertAfter(Node* pNode, int nData)
{if(pNode == NULL){return;}Node* pNewNode = new Node();pNewNode->nData = nData;pNewNode->pNext = pNode->pNext;pNode->pNext = pNewNode;
}删除节点
要删除单向链表中的某个节点，首先要找到待删除节点的前一个节点。然后，将其pNext指针绕过目标节点直接指向目标节点之后的节点。具体实现，可参考下面的示例代码。
void DeleteNode(Node** pHead, int nKey)
{Node *pTemp = *pHead;if(pTemp != NULL && pTemp->nData == nKey){// 如果要删除的是头节点*pHead = pTemp->pNext;delete pTemp;return;}Node *pPrev = NULL;while(pTemp != NULL && pTemp->nData != nKey){pPrev = pTemp;pTemp = pTemp->pNext;}if (pTemp == NULL){// 键不存在于链表中return;}pPrev->pNext = pTemp->pNext;delete pTemp;
}总结
单向链表的主要优势在于：动态性和灵活性。相较于数组，单向链表允许更高效的插入和删除操作，尤其是在中间位置进行这些操作时。比如：在一个已排序的列表中添加新元素，单向链表只需要调整几个指针的位置即可完成，而数组则可能需要移动大量元素来腾出空间。另外，单向链表可以很容易地扩展到任意大小，因为它不需要预先分配固定大小的内存块。