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;
}

总结

        单向链表的主要优势在于：动态性和灵活性。相较于数组，单向链表允许更高效的插入和删除操作，尤其是在中间位置进行这些操作时。比如：在一个已排序的列表中添加新元素，单向链表只需要调整几个指针的位置即可完成，而数组则可能需要移动大量元素来腾出空间。另外，单向链表可以很容易地扩展到任意大小，因为它不需要预先分配固定大小的内存块。