数据结构——双向链表的查询、插入、删除、释放（十四）

一、查询链表

1、下标查询

代码：

struct Node* GetNodeByIndex(struct Node* stHead, int iCount, int iIndex)//下标查询
{
    //参数合法性检测
    if (NULL == stHead || iCount <= 0 || iIndex < 0 || iIndex >= iCount)
        return NULL;
    //循环遍历链表
    struct Node* pTemp = stHead->pNext;
    for (int i = 0; i < iIndex; i++)
        pTemp = pTemp->pNext;
    return pTemp;
}

实现链表节点按索引查询功能，输入链表头节点、链表长度和目标索引，返回对应节点指针。

步骤：

参数合法性检测

• 头节点指针非空检测
• 链表长度需为正数
• 下标不超过范围，取值范围为0 ≤ iIndex ≤ iCount

循环遍历链表

2、数据查询

代码：

struct Node* GetNodeByData(struct Node* stHead, int iData)//数据查询
{
    //参数合法性检测
    if (NULL == stHead || stHead == stHead->pNext)
        return NULL;
    //循环查找
    struct Node* pTemp = stHead->pNext;
    while (pTemp != stHead)
    {
        if (pTemp->iData == iData)
            return pTemp;
        pTemp = pTemp->pNext;
    }
    return NULL;
}

实现查找包含特定数据的节点。函数接收链表头节点指针stHead和目标数据iData，返回匹配的节点指针或NULL。

步骤：

参数合法性检测

• 检查链表头指针是否为空
• 检查链表是否只有头节点（循环链表中头节点的pNext指向自身时为空链表）

循环查找

• 从第一个有效节点开始遍历（跳过头节点）
• 循环条件pTemp != stHead确保遍历完整链表
• 发现匹配数据立即返回当前节点指针
• 如果循环结束没有发现匹配数据，则返回NULL

二、插入节点

1、指定下标位置插入节点

代码：

void InsertByIndex(struct Node* stHead, int* iCount, int iIndex, int iData)//指定下标位置插入节点
{
    //参数合法性检测
    if (NULL == stHead || *iCount <= 0 || iIndex < 0 || iIndex > *iCount)
        return ;
    //尾添加
    if(iIndex == *iCount)
        AddToEnd(stHead, iCount, iData);
    else
    {
        //找位置
        struct Node* pTemp = GetNodeByIndex(stHead, *iCount, iIndex);
        if (NULL == pTemp)
            return;
        //创建节点
        
        struct Node* pT = (struct Node*)malloc(sizeof(struct Node));
        if (NULL == pT)
            return;
        //节点赋值
        pT->iData = iData;
        pT->pNext = NULL;
        pT->pPre = NULL;
        //接入
        //先连
        pT->pPre = pTemp->pPre;
        pT->pNext = pTemp;
        //后断
        pTemp->pPre->pNext = pT;
        pTemp->pPre = pT;
        //节点个数++
        *iCount += 1;
    }
}

实现在双向链表中指定下标位置插入新节点的功能。函数接受链表头节点指针、节点数量指针、插入位置下标和插入数据作为参数。

步骤：

参数合法性检查

• 链表头节点指针是否为NULL
• 当前节点数量是否小于等于0
• 插入位置下标是否合法（不小于0且不超过当前节点数量）

尾节点插入处理

当插入位置等于当前节点数量时，直接调用AddToEnd函数在链表尾部添加新节点。

非尾节点插入逻辑

调用：

InsertByIndex(&stHead, &iCount, 6, 66);
InsertByIndex(&stHead, &iCount, 0, 0);
InsertByIndex(&stHead, &iCount, 3, 33);

2、指定数据位置插入节点

代码：

void InsertByData(struct Node* stHead, int* iCount, int iValue, int iData)//在指定的数据前面增加一个节点
{
    //参数合法性检测
    if (NULL == stHead || *iCount <= 0)
        return;
    //找节点
    struct Node* pTemp = GetNodeByData(stHead, iValue);
    if (NULL == pTemp)
        return;
    //找到了，创建节点
    struct Node* pT = (struct Node*)malloc(sizeof(struct Node));
    if (NULL == pT)
        return;
    pT->iData = iData;
    pT->pNext = NULL;
    pT->pPre = NULL;
    //接入
    //先连
    pT->pNext = pTemp;
    pT->pPre = pTemp->pPre;
    //后断
    pTemp->pPre->pNext = pT;
    pTemp->pPre = pT;
    //节点个数++
    *iCount += 1;
}

实现在双向链表中指定数据节点前插入新节点的功能。通过传入链表头节点指针、节点计数器指针、目标数据值和新节点数据值完成操作。

步骤：

参数合法性检查 

检查链表头指针是否为空或节点计数是否小于等于0，非法参数直接返回不执行操作。

查找目标节点 

调用GetNodeByData函数查找包含iValue的节点，未找到则直接返回。

创建新节点 

动态分配内存创建新节点，初始化数据域和指针域。内存分配失败时直接返回。

节点接入处理 

1和2顺序可反，3和4必须先3再4.

计数更新 

通过指针修改外部节点计数器，增加1

调用：

InsertByData(&stHead, &iCount, 1, 11);
InsertByData(&stHead, &iCount, 4, 44);
InsertByData(&stHead, &iCount, 6, 66);

三、删除节点

1、删除指定下标节点

代码：

void DaleteByIndex(struct Node* stHead, int* iCount, int iIndex)//删除指定下标节点
{
    //参数合法性检测
    if (NULL == stHead || *iCount <= 0 || iIndex < 0 || iIndex >= *iCount)
        return;
    //找节点
    struct Node* pTemp = GetNodeByIndex(stHead, *iCount, iIndex);
    if (NULL == pTemp)
        return;
    //删除
    pTemp->pPre->pNext = pTemp->pNext;
    pTemp->pNext->pPre = pTemp->pPre;
    free(pTemp);
    //数量–
    *iCount -= 1;
}

删除双向链表中指定下标的节点，包含参数检查、节点查找、节点删除和计数器更新四个主要部分。

步骤：

参数合法性检测

• 链表头节点指针是否为NULL

• 链表节点计数是否小于等于0

• 目标下标是否在有效范围内(0 ≤ iIndex < *iCount) 任一条件不满足时函数直接返回，不执行后续操作。

节点查找

调用GetNodeByIndex函数获取目标下标对应的节点指针。如果返回NULL指针，函数直接返回。

节点删除操作

计数器更新

成功删除节点后，通过指针修改外部维护的节点计数器值(*iCount -= 1)。

调用：

DaleteByIndex(&stHead, &iCount, 5);
DaleteByIndex(&stHead, &iCount, 3);
DaleteByIndex(&stHead, &iCount, 0);

2、删除指定一段下标节点

代码：

void DaleteBySomeIndex(struct Node* stHead, int* iCount, int iIndex1 , int iIndex2)//删除指定一段下标节点
{
    int iI1 = 0, iI2 = 0;
    if(iIndex1 <= iIndex2)
    {
        iI1 = iIndex1;
        iI2 = iIndex2;
    }
    else
    {
        iI1 = iIndex2;
        iI2 = iIndex1;
    }
    for (int i = iI1; i <= iI2; i++)
    {
        DaleteByIndex(stHead, iCount, iI1);//删除一个 下标随着变化
    }
}

删除链表中指定下标范围内的节点。函数接收链表头指针 stHead、节点计数器 iCount、起始下标 iIndex1 和结束下标 iIndex2 作为参数。

步骤：

确定起始和结束下标的顺序

定义iI1 、iI12，判断 iIndex1、iIndex2的大小，确保iI1 为较小的下标，iI2 为较大的下标。

循环删除

通过循环调用 DaleteByIndex 函数删除指定下标范围内的节点。

调用：

DaleteBySomeIndex(&stHead, &iCount, 1, 3);

3、删除所有指定数据节点

代码：

void DaleteByData(struct Node* stHead, int* iCount, int iData)//删除所有指定数据节点
{
    //参数合法性检测
    if (NULL == stHead || *iCount <= 0)
        return;
    while(1)
    {
        //找节点
        struct Node* pTemp = GetNodeByData(stHead, iData);
        if (NULL == pTemp)
            return;
        //删除
        pTemp->pPre->pNext = pTemp->pNext;
        pTemp->pNext->pPre = pTemp->pPre;
        free(pTemp);
        //数量–
        *iCount -= 1;
    }
}

删除双向链表中所有数据值等于指定值的节点。函数接收链表头节点指针、节点计数器指针以及要删除的目标数据值作为参数。

步骤：

参数合法性检测

• 链表头节点指针是否为NULL

• 链表节点计数是否小于等于0

循环删除节点

• 通过GetNodeByData函数查找目标数据节点，未找到则退出循环。
•  目标节点的前驱节点的后续指针指向目标节点的后续节点pTemp->pPre->pNext = pTemp->pNext
• 目标节点的后续节点的前驱指针指向目标节点的前驱节点pTemp->pNext->pPre = pTemp->pPre
• 释放目标节点free(pTemp)
• 进入下一个循环

调用：

DaleteByData(&stHead, &iCount, 1);

四、释放链表

void DeleteList(struct Node* stHead, int* iCount)//释放链表
{
    //参数合法性检测
    if (NULL == stHead || stHead->pNext == stHead)
        return;
    //释放
    struct Node* pTemp = stHead->pNext;
    while (pTemp != stHead)
    {
        //记录
        struct Node* pT = pTemp;
        //往下走
        pTemp = pTemp->pNext;
        //释放记录
        free(pT);
    }
    //数据清零
    *iCount = 0;
    stHead->pNext = stHead;
    stHead->pPre = stHead;
}

通过临时指针pT保存待释放节点，确保释放后仍能继续遍历。

释放完节点后，重置计数器和头节点指针。