轻松掌握C语言双链表编程：从零到高手，实用示例全解析！-每日运维

一、介绍

一、双链表简介

什么是双链表？

双链表，也称作“双向链表”或“双重链表”，它由节点构成，每个节点既包含数据（或值），又包含两个指针，一个指向前一个节点，另一个指向后一个节点。

双链表的应用场景是什么？

双链表常用于需要频繁插入和删除节点的场景。
例如文本编辑器中的撤销和恢复功能、图形界面框架、浏览器历史记录、数据库管理系统等。

双链表的优点是什么？

双向查找更便捷，快速访问前一个或后一个节点。
支持双向遍历使得在某个节点附近进行操作更加方便，如在文本编辑器中移动光标。

双链表的缺点是什么？

每个节点包含两个指针，内存消耗增加。
操作复杂度相对较高。

双链表如何改进？

为了降低内存消耗，可以考虑使用单链表，并在每个节点中存储指向前一个节点的指针。这种方法被称为“前向单链表”或“反向单链表”。
对于频繁操作的场景，采用平衡二叉树或哈希表等数据结果，可以提高插入和删除的效率。

双链表的实现难度如何？

双链表的基本实现相对较简单，但在处理复杂的操作时，需要谨慎处理指针的连接和断开。在面对涉及多个节点的复杂操作时，复杂的边界情况和内存管理会很让人头疼。

第三、四、五部分附赠1000行代码（自定义头文件、实现代码，以及调试主文件）

二、构建双链表的数据结构

节点的定义

双链表的核心思想是通过一个节点，既能访问到上一个节点（前驱），也能访问下一个节点（后继）。

为了定义一个双链表节点，通常遵循以下结构：

struct Node 
{
    // 可以根据需求添加多个元素
    elementType element1;
    elementType element2;
    // ...
    elementType elementn;
    
    struct Node *prev; // 指向前一个节点
    struct Node *next; // 指向下一个节点
};

在上述代码中，elementType 可以是任何数据类型，根据节点需要存储的数据而定。你可以自行修改并扩展节点的成员。

在本文中，我们采用如下的节点定义，以便于示例和代码的理解：

typedef struct linkedListNode linkedList;
typedef linkedList Node;
typedef int elementType;

struct linkedListNode
{
    elementType value;  // 存储节点的值
    linkedList *next;   // 指向下一个节点
    linkedList *prev;   // 指向前一个节点
};

这种节点定义旨在清晰地表达了节点的基本结构，包括值以及与前一个和后一个节点的关系。
需要注意的是，代码中使用了 typedef 来重新定义 linkedList 和 Node，这使得代码更易于阅读和理解，因为我们可以使用短一些的名称。

节点的创建

在这个节点创建函数中，我们接收两个参数：值和后继指针（next）。新创建的节点将使用传递的值来填充元素域（value），并使用传递的指针来指定后继指针域（next）。

与我之前在《掌握C语言单链表编程：从零到高手，实用示例全解析！》中实现的节点创建函数不同，这次我们接受了新参数 next。这种设计允许在执行插入、删除等链表操作时更容易隐藏细节。

同时，因为没有接收 prev（前驱指针），这避免了过度封装。如果将节点的前驱指针也封装在函数中，将对这个函数的灵活性产生不利影响。

// 创建一个新节点并返回其指针
Node *createNode(elementType value, Node *next)
{
    Node *node = (Node *)malloc(sizeof(Node));
    if (node == NULL)
    {
        // 处理内存分配失败（例如，打印错误消息）
        printf("错误：在 createNode 中内存分配失败。n");
        exit(1); // 或返回 NULL 或执行其他错误处理
    }
    node->value = value; // 设置节点的值
    node->next = next;   // 设置节点的下一个节点指针
    node->prev = NULL;   // 设置节点的前一个节点指针为 NULL，因为它是链表的第一个节点
    return node;         // 返回新节点的指针
}

查找

1. 根据位置查找

遍历链表进行查找，同时需要注意边界情况。

// 根据节点位置查找链表中的节点
Node *findNodeByLocation(linkedList *head, int location)
{
    while (--location)
    {
        if (!head)
        {
            return head; // 如果位置超出链表长度，返回NULL
        }
        head = head->next; // 移动到下一个节点
    }
    return head; // 返回找到的节点
}

时间复杂度： O(N)O(N)O(N)
空间复杂度： O(1)O(1)O(1)

2. 根据值查找

遍历链表查找匹配的值，找到匹配的节点后返回，找不到就返回 NULL。

// 根据节点值查找链表中的节点
Node *findNodeByValue(linkedList *head, elementType value)
{
    Node *node = head;
    while (node)
    {
        if (node->value == value)
        {
            return node; // 返回找到的节点
        }
        node = node->next; // 移动到下一个节点
    }
    return NULL; // 如果未找到匹配的节点，则返回NULL
}

时间复杂度： O(N)O(N)O(N)
空间复杂度： O(1)O(1)O(1)

3. 检查链表中是否存在特定的值

调用 findNodeByValue 函数并进行逻辑判断即可。

// 检查链表中是否存在特定的值
bool containsValueInLinkedList(linkedList *head, elementType value)
{
    return findNodeByValue(head, value) != NULL; // 如果找到匹配的节点，返回true，否则返回false
}

时间复杂度： O(N)O(N)O(N)
空间复杂度： O(1)O(1)O(1)

插入

双链表的插入操作本质上与单链表的插入差异不大，只是需要多注意前驱指针（在本文中为 prev）。

1. 插入头部

通常来说，需要接收两个参数：链表头节点（如果不是全局变量）和值。
首先创建一个节点，使这个节点的 next 指针指向当前的头节点（如果存在），然后更新头指针以指向新建的节点即可。

1.1 不带返回值

// 在链表头部插入节点
void insertNodeAtHead(linkedList **head, elementType value)
{
    Node *newNode = createNode(value, *head); // 创建新节点
    if (*head)
    {
        (*head)->prev = newNode; // 更新原头节点的前一个节点指针
    }
    *head = newNode; // 更新链表的头节点指针
}

时间复杂度： O(1)O(1)O(1)
空间复杂度： O(1)O(1)O(1)

1.2 带返回值

// 在链表头部插入节点，并返回新的头节点
Node *insertNodeAtHead(linkedList **head, elementType value)
{
    Node *newNode = createNode(value, *head); // 创建新节点
    if (*head)
    {
        (*head)->prev = newNode; // 更新原头节点的前一个节点指针
    }
    *head = newNode; // 更新链表的头节点指针
    return *head; // 返回新的头节点
}

时间复杂度： O(1)O(1)O(1)
空间复杂度： O(1)O(1)O(1)

2. 插入尾部

遍历链表直到尾节点，同时创建新节点（newNode）。使当前的尾节点的 next 指针指向新建的节点，而 newNode 的 prev 指针指向尾节点。需要特别注意处理空链表和仅包含一个节点的链表情况。

2.1 不带返回值

// 在链表尾部插入节点
void insertNodeAtTail(linkedList **head, elementType value)
{
    Node *newNode = createNode(value, NULL); // 创建新节点
    Node *currentNode = *head;

    if (!currentNode)
    {
        *head = newNode; // 如果链表为空，将新节点设置为头节点
    }
    else
    {
        while (currentNode->next)
        {
            currentNode = currentNode->next; // 移动到下一个节点，直到找到最后一个节点
        }
        currentNode->next = newNode; // 更新最后一个节点的下一个节点指针
        newNode->prev = currentNode; // 更新新节点的前一个节点指针
    }
}

时间复杂度： O(N)O(N)O(N)
空间复杂度： O(1)O(1)O(1)

2.2 带返回值

// 在链表尾部插入节点，并返回新的尾节点
Node *insertNodeAtTail(linkedList **head, elementType value)
{
    Node *newNode = createNode(value, NULL); // 创建新节点
    Node *currentNode = *head;

    if (!currentNode)
    {
        *head = newNode; // 如果链表为空，将新节点设置为头节点
    }
    else
    {
        while (currentNode->next)
        {
            currentNode = currentNode->next; // 移动到下一个节点，直到找到最后一个节点
        }
        currentNode->next = newNode; // 更新最后一个节点的下一个节点指针
        newNode->prev = currentNode; // 更新新节点的前一个节点指针
    }
    return newNode; // 返回新的尾节点
}

时间复杂度： O(N)O(N)O(N)
空间复杂度： O(1)O(1)O(1)

3. 一般插入

执行插入操作时需要指定位置，因此我们假定链表的头节点位置为0。
这样，我们可以明确定位链表中每个节点的位置。
当要在指定位置（假设为 location）插入节点时，我们必须确保它是合法的，即

1≤location≤(1+numberOfNodesIn(list))1 leq text{location} leq (1 + text{numberOfNodesIn}(text{list}))1≤location≤(1+numberOfNodesIn(list))

如果 locationlocationlocation 不合法，需要进行异常处理。
在假定 locationlocationlocation 合法的前提下，我们找到位置 (location−1)(location-1)(location−1) 和 (location+1)(location+1)(location+1) 对应的节点（前驱节点 prevNode 和后继节点 nextNode）。
此外，需要创建新节点（newNode）。
接下来，只需合理更新 prevNode、nextNode 和 newNode 的 prev 和 next 指针即可。

3.1 不带返回值

// 在链表的指定位置插入节点
void insertNodeAtLocation(linkedList **head, elementType value, int location)
{
    if (location next); // 创建新节点
            if (prevNode->next)
            {
                prevNode->next->prev = newNode; // 更新下一个节点的前一个节点指针
            }
            prevNode->next = newNode; // 更新前一个节点的下一个节点指针
            newNode->prev = prevNode; // 更新新节点的前一个节点指针
        }
        else
        {
            printf("错误：insertNodeAtLocation(...int location)：位置太大n");
        }
    }
}

时间复杂度： O(N)O(N)O(N)
空间复杂度： O(1)O(1)O(1)

3.2 带返回值

// 在链表的指定位置插入节点，并返回新的头节点
Node *insertNodeAtLocation(linkedList **head, elementType value, int location)
{
    if (location next); // 创建新节点
            if (prevNode->next)
            {
                prevNode->next->prev = newNode; // 更新下一个节点的前一个节点指针
            }
            prevNode->next = newNode; // 更新前一个节点的下一个节点指针
            newNode->prev = prevNode; // 更新新节点的前一个节点指针
            return *head; // 返回新的头节点
        }
        else
        {
            printf("错误：insertNodeAtLocation(...int location)：位置太大n");
            return *head;
        }
    }
}

时间复杂度： O(N)O(N)O(N)
空间复杂度： O(1)O(1)O(1)

删除

1. 删除头部

需要考虑两种情况。

空链表，无需执行删头操作。

非空链表:

标记当前头节点
更新头节点
如果更新头头节点仍然存在，prev指针指向空。
释放原头节点的内存

1.1 不带返回值

// 删除链表头部的节点
void deleteNodeAtHead(linkedList **head)
{
    if (*head)
    {
        Node *node = *head;
        *head = (*head)->next; // 更新链表的头指针为下一个节点
        if (*head)
        {
            (*head)->prev = NULL; // 如果新的头节点存在，更新其前一个节点指针为NULL
        }
        free(node); // 释放原头节点的内存
    }
    else
    {
        printf("错误：deleteNodeAtHead(linkedList **head)：链表为空，无法执行删除头节点。n");
    }
}

时间复杂度： O(1)O(1)O(1)
空间复杂度： O(1)O(1)O(1)

1.2 带返回值

// 删除链表头部的节点，并返回新的头节点
Node *deleteNodeAtHead(linkedList **head)
{
    if (*head)
    {
        Node *node = *head;
        *head = (*head)->next; // 更新链表的头指针为下一个节点
        if (*head)
        {
            (*head)->prev = NULL; // 如果新的头节点存在，更新其前一个节点指针为NULL
        }
        free(node); // 释放原头节点的内存
        return *head; // 返回新的头节点
    }
    else
    {
        printf("错误：deleteNodeAtHead(linkedList **head)：链表为空，无法执行删除头节点。n");
        return NULL;
    }
}

时间复杂度： O(1)O(1)O(1)
空间复杂度： O(1)O(1)O(1)

2. 删除尾部

空链表不执行操作

非空链表：

标记尾节点（通过遍历链表）
通过prev指针判断是否原链表为单节点
如果单节点，更新链表头指针为NULL
否则，断开尾节点与其前驱节点的联系
释放尾节点内存

2.1 不带返回值

// 删除链表尾部的节点
void deleteNodeAtTail(linkedList **head)
{
    if (*head)
    {
        Node *tailNode = *head;
        while (tailNode->next)
        {
            tailNode = tailNode->next; // 移动到下一个节点，直到找到最后一个节点
        }
        if (tailNode->prev)
        {
            tailNode->prev->next = NULL; // 更新倒数第二个节点的下一个节点指针为NULL
        }
        else
        {
            *head = NULL; // 如果链表中只有一个节点，更新链表头指针为NULL
        }
        free(tailNode); // 释放尾节点的内存
    }
}

时间复杂度： O(N)O(N)O(N)
空间复杂度： O(1)O(1)O(1)

2.2 带返回值

// 删除链表尾部的节点，并返回新的尾节点
Node *deleteNodeAtTail(linkedList **head)
{
    if (*head)
    {
        Node *tailNode = *head;
        while (tailNode->next)
        {
            tailNode = tailNode->next; // 移动到下一个节点，直到找到最后一个节点
        }
        if (tailNode->prev)
        {
            tailNode->prev->next = NULL; // 更新倒数第二个节点的下一个节点指针为NULL
        }
        else
        {
            *head = NULL; // 如果链表中只有一个节点，更新链表头指针为NULL
        }
        free(tailNode); // 释放尾节点的内存
        return *head; // 返回新的尾节点
    }
    else
    {
        printf("错误：deleteNodeAtTail(linkedList **head)：链表为空，无法执行删除尾节点。n");
        return NULL;
    }
}

时间复杂度： O(N)O(N)O(N)
空间复杂度： O(1)O(1)O(1)

3. 一般删除

首先确保locationlocationlocation合法即

1≤location≤numberOfNodesIn(list)1 leq text{location} leq text{numberOfNodesIn}(text{list})1≤location≤numberOfNodesIn(list)

标记locationlocationlocation处的节点（如有）,不妨记为currentNode。另记currentNode的前驱节点和后继节点为prevNdoe和nextNode.

只需断开currentNode和prevNode、nextNode的联系，另将prevNode和nextNode直接关联即可，并释放currentNode的内存即可。

特殊的，对于
location=1location=1location=1或location=numberOfNodesIn(list)location=numberOfNodesIn(list)location=numberOfNodesIn(list)
即头节点或尾节点，需要做特殊处理，不妨借鉴前文所提到的deleteNodeAtHead和deleteNodeAtTail函数。

3.1 不带返回值

// 从链表的指定位置删除节点
void deleteNodeAtLocation(linkedList **head, int location)
{
    if (location prev->next = currentNode->next; // 更新前一个节点的下一个节点指针
            if (currentNode->next)
            {
                currentNode->next->prev = currentNode->prev; // 更新下一个节点的前一个节点指针
            }
            free(currentNode); // 释放当前节点的内存
        }
        else
        {
            printf("错误：deleteNodeAtLocation(...int location)：位置太大。n");
        }
    }
}

时间复杂度： O(N)O(N)O(N)
空间复杂度： O(1)O(1)O(1)

3.2 带返回值

// 从链表的指定位置删除节点，并返回新的头节点
Node *deleteNodeAtLocation(linkedList **head, int location)
{
    if (location prev->next = currentNode->next; // 更新前一个节点的下一个节点指针
            if (currentNode->next)
            {
                currentNode->next->prev = currentNode->prev; // 更新下一个节点的前一个节点指针
            }
            free(currentNode); // 释放当前节点的内存
            return *head; // 返回新的头节点
        }
        else
        {
            printf("错误：deleteNodeAtLocation(...int location)：位置太大。n");
            return *head;
        }
    }
}

时间复杂度： O(N)O(N)O(N)
空间复杂度： O(1)O(1)O(1)

修改值

此处我们希望通过locationlocationlocation来修改指定位置的节点（如有）的值。
我们仍然要确保locationlocationlocation合法即

1≤location≤numberOfNodesIn(list)1 leq text{location} leq text{numberOfNodesIn}(text{list})1≤location≤numberOfNodesIn(list)

// 修改链表中某个节点的值
void modifyNodeValue(linkedList **head, int location, elementType newValue)
{
    Node *node = findNodeByLocation(*head, location);
    if (node)
    {
        node->value = newValue; // 修改节点的值
    }
}

时间复杂度： O(N)O(N)O(N)
空间复杂度： O(1)O(1)O(1)

遍历

遍历是链表中最基本的操作，在前文中多个函数中都多次出现。

不同的是，根据 DRY 原则，为了提高函数的灵活性，我们使 traverseLinkedList 函数允许接收 void 类型的函数指针。

这种方式提高了函数的通用性和可重用性，允许我们在不更改 traverseLinkedList 函数的情况下，根据需要执行不同的操作。这种设计方式常用于编写更具扩展性的代码。

DRY (Don’t repeat yourself)，是敏捷开发的核心设计原则之一。

这个函数指针允许我们传递一个自定义的操作（函数）作为参数给 traverseLinkedList。

这样，我们可以定义任何操作，将其应用到链表的每个节点上，而不必修改 traverseLinkedList 函数本身。

相信看到这里，聪明的你会发现前文中出现的插入、查找、删除等操作都可以在主文件中写个函数，应用到这个 traverseLinkedList 函数来实现，似乎违背了 DRY 原则，但是我们不能过度的追求灵活性。

在自定义头文件中实现需求量大的操作如插入、删除等，可以减少程序的 bug 量，让别人或以后的自己的程序更鲁棒！

traverseLinkedList 函数如下：

// 遍历链表并执行操作
void traverseLinkedList(linkedList *head, void (*operation)(Node *))
{
    while (head)
    {
        operation(head);   // 执行传入的操作函数
        head = head->next; // 移动到下一个节点
    }
}

时间复杂度： O(N)O(N)O(N)
空间复杂度： O(1)O(1)O(1)

如果你想要遍历链表并打印每个节点的值，创建一个打印函数，将其传递给 traverseLinkedList，它将在遍历链表时对每个节点调用这个函数来执行打印操作。

打印函数见下面：

void print(linkedList *node)
{
    if (node)
    {
        int value = node->value;
        if (!node->next && !node->prev)
        {
            printf("null  null", value);
        }
        else if (!node->prev)
        {
            printf("null  nulln", value);
        }
    }
}

在主函数主应用

traverseLinkedList(list, print);

运行结果大抵如下：

翻转

双链表的翻转明显要比单链表的翻转要复杂一些。在递归和迭代两种方法中，需要考虑的细节较多。建议不必急于迅速掌握，而应当深刻理解这些代码的原理。

1. 递归实现

// 递归方式反转链表
Node *reverseLinkedListRecursively(linkedList *head)
{
    if (!head || !head->next)
    {
        return head; // 如果链表为空或只有一个节点，直接返回
    }
    
    Node *newHead = reverseLinkedListRecursively(head->next); // 递归反转后续链表

    // 更新节点指针
    head->next->prev = head->next->next;
    head->next->next = head;

    // 如果是头节点，更新前一个节点的指针
    if (!head->prev)
    {
        head->prev = head->next;
        head->next = NULL; // 将头节点的下一个节点指针设为NULL
    }

    return newHead; // 返回反转后的链表
}

时间复杂度： O(N)O(N)O(N)
空间复杂度： O(1)O(1)O(1)

2. 迭代实现

// 迭代方式反转链表
Node *reverseLinkedListIteratively(linkedList *head)
{
    Node *prevNode = NULL;
    Node *currentNode = head;
    Node *nextNode;

    while (currentNode)
    {
        nextNode = currentNode->next; // 保存下一个节点的指针
        currentNode->next = prevNode;  // 反转节点指针

        // 更新前一个节点和当前节点
        prevNode = currentNode;
        currentNode = nextNode;
    }

    return prevNode; // 返回反转后的链表
}

时间复杂度： O(N)O(N)O(N)
空间复杂度： O(1)O(1)O(1)

九清空链表

清空链表无论是双链表还是单链表，实现的逻辑大都一般无二。
如果你对递归有浅显的理解，相信不难理解下面的代码。
如果读者感兴趣，不妨试着用迭代实现。

// 清空链表并释放内存
void clearLinkedList(linkedList **head)
{
    if (!(*head))
    {
        return; // 如果链表为空，直接返回
    }
    clearLinkedList(&(*head)->next); // 递归清空下一个节点
    *head = NULL;                    // 更新当前节点为NULL
    free(*head);                     // 释放当前节点的内存
}

时间复杂度： O(N)O(N)O(N)
空间复杂度： O(1)O(1)O(1)

检查是否是合理的双向链表

根据双链表的定义实现即可，不难。
下面是迭代实现的一个实例。
如果读者感兴趣，不妨试着再用递归实现下。

// 检查双向链表是否有效
bool isDoublyLinkedListValid(linkedList *head)
{
    if (!head)
    {
        return true; // 空链表被认为是有效的
    }

    linkedList *current = head;
    linkedList *prev = NULL;

    while (current)
    {
        if (current->prev != prev)
        {
            return false; // 前一个节点指针不正确
        }

        prev = current;
        current = current->next;
    }

    // 确保最后一个节点的下一个节点指针是NULL
    return (prev->next == NULL);
}

时间复杂度： O(N)O(N)O(N)
空间复杂度： O(1)O(1)O(1)

三、函数接口（注释详细）

// D:A_Shun_Exclusivelife_ofuniversitycode_collectionCVSCODEincludeDataStructuremy_double_basic_linklist.h
#pragma once

#include 
#include 
#include 

typedef struct linkedListNode linkedList;
typedef linkedList Node;
typedef int elementType;

struct linkedListNode
{
    elementType value;
    linkedList *next;
    linkedList *prev;
};

// 创造节点
Node *createNode(elementType value, Node *next);

// 根据节点值查找链表中的节点
Node *findNodeByValue(linkedList *head, elementType value);

// 根据节点位置查找链表中的节点
Node *findNodeByLocation(linkedList *head, int location);

// 检查链表中是否存在特定的值
bool containsValueInLinkedList(linkedList *head, elementType value);

// 获取链表的长度
int getLengthOfLinkedList(linkedList *head);

// 在链表的指定位置插入节点
void insertNodeAtLocation(linkedList **head, elementType value, int location);

// 在链表头部插入节点
void insertNodeAtHead(linkedList **head, elementType value);

// 在链表尾部插入节点
void insertNodeAtTail(linkedList **head, elementType value);

// 从链表的指定位置删除节点
void deleteNodeAtLocation(linkedList **head, int location);

// 删除链表头部的节点
void deleteNodeAtHead(linkedList **head);

// 删除链表尾部的节点
void deleteNodeAtTail(linkedList **head);

// 修改链表中某个节点的值
void modifyNodeValue(linkedList **head, int location, elementType newValue);

// 遍历链表并执行操作
void traverseLinkedList(linkedList *head, void (*operation)(Node *));

// 反转链表，递归实现
Node *reverseLinkedList(linkedList *head);

// 清空链表并释放内存
void clearLinkedList(linkedList **head);

// 检查是否合理双链表
bool isDoublyLinkedListValid(linkedList *head);

四、函数实现（注释详细）

//D:A_Shun_Exclusivelife_ofuniversitycode_collectionCVSCODEincludeDataStructuremy_double_basic_linklist.c

#include "my_double_basic_linklist.h"

// 创建一个新节点并返回其指针
Node *createNode(elementType value, Node *next)
{
    Node *node = (Node *)malloc(sizeof(Node));
    if (node == NULL)
    {
        // 处理内存分配失败（例如，打印错误消息）
        printf("错误：在 createNode 中内存分配失败。n");
        exit(1); // 或返回 NULL 或执行其他错误处理
    }
    node->value = value; // 设置节点的值
    node->next = next;   // 设置节点的下一个节点指针
    node->prev = NULL;   // 设置节点的前一个节点指针为NULL，因为它是链表的第一个节点
    return node;         // 返回新节点的指针
}

// 根据节点值查找链表中的节点
Node *findNodeByValue(linkedList *head, elementType value)
{
    Node *node = head;
    while (node)
    {
        if (node->value == value)
        {
            return node; // 返回找到的节点
        }
        node = node->next; // 移动到下一个节点
    }
    return NULL; // 如果未找到匹配的节点，则返回NULL
}

// 根据节点位置查找链表中的节点
Node *findNodeByLocation(linkedList *head, int location)
{
    while (--location)
    {
        if (!head)
        {
            return head; // 如果位置超出链表长度，返回NULL
        }
        head = head->next; // 移动到下一个节点
    }
    return head; // 返回找到的节点
}

// 检查链表中是否存在特定的值
bool containsValueInLinkedList(linkedList *head, elementType value)
{
    return findNodeByValue(head, value) != NULL; // 如果找到匹配的节点，返回true，否则返回false
}

// 获取链表的长度
int getLengthOfLinkedList(linkedList *head)
{
    int length = 0;
    while (head)
    {
        head = head->next; // 移动到下一个节点
        length++;          // 增加长度计数
    }
    return length; // 返回链表的长度
}

// 在链表的指定位置插入节点
void insertNodeAtLocation(linkedList **head, elementType value, int location)
{
    if (location next); // 创建新节点
            if (prevNode->next)
            {
                prevNode->next->prev = newNode; // 更新下一个节点的前一个节点指针
            }
            prevNode->next = newNode; // 更新前一个节点的下一个节点指针
            newNode->prev = prevNode; // 更新新节点的前一个节点指针
        }
        else
        {
            printf("错误：insertNodeAtLocation(...int location)：位置太大n");
        }
    }
}

// 在链表头部插入节点
void insertNodeAtHead(linkedList **head, elementType value)
{
    Node *newNode = createNode(value, *head); // 创建新节点
    if (*head)
    {
        (*head)->prev = newNode; // 更新原头节点的前一个节点指针
    }
    *head = newNode; // 更新链表的头节点指针
}

// 在链表尾部插入节点
void insertNodeAtTail(linkedList **head, elementType value)
{
    Node *newNode = createNode(value, NULL); // 创建新节点
    Node *currentNode = *head;

    if (!currentNode)
    {
        *head = newNode; // 如果链表为空，将新节点设置为头节点
    }
    else
    {
        while (currentNode->next)
        {
            currentNode = currentNode->next; // 移动到下一个节点，直到找到最后一个节点
        }
        currentNode->next = newNode; // 更新最后一个节点的下一个节点指针
        newNode->prev = currentNode; // 更新新节点的前一个节点指针
    }
}

// 从链表的指定位置删除节点
void deleteNodeAtLocation(linkedList **head, int location)
{
    if (location prev->next = currentNode->next; // 更新前一个节点的下一个节点指针
            if (currentNode->next)
            {
                currentNode->next->prev = currentNode->prev; // 更新下一个节点的前一个节点指针
            }
            free(currentNode); // 释放当前节点的内存
        }
        else
        {
            printf("错误：deleteNodeAtLocation(...int location)：位置太大。n");
        }
    }
}

// 删除链表头部的节点
void deleteNodeAtHead(linkedList **head)
{
    if (*head)
    {
        Node *node = *head;
        *head = (*head)->next; // 更新链表的头指针为下一个节点
        if (*head)
        {
            (*head)->prev = NULL; // 如果新的头节点存在，更新其前一个节点指针为NULL
        }
        free(node); // 释放原头节点的内存
    }
    else
    {
        printf("错误：deleteNodeAtHead(linkedList **head)：链表为空，无法执行删除头节点。n");
    }
}

// 删除链表尾部的节点
void deleteNodeAtTail(linkedList **head)
{
    if (*head)
    {
        Node *tailNode = *head;
        while (tailNode->next)
        {
            tailNode = tailNode->next; // 移动到下一个节点，直到找到最后一个节点
        }
        if (tailNode->prev)
        {
            tailNode->prev->next = NULL; // 更新倒数第二个节点的下一个节点指针为NULL
        }
        else
        {
            *head = NULL; // 如果链表中只有一个节点，更新链表头指针为NULL
        }
        free(tailNode); // 释放尾节点的内存
    }
}

// 修改链表中某个节点的值
void modifyNodeValue(linkedList **head, int location, elementType newValue)
{
    Node *node = findNodeByLocation(*head, location);
    if (node)
    {
        node->value = newValue; // 修改节点的值
    }
}

// 遍历链表并执行操作
void traverseLinkedList(linkedList *head, void (*operation)(Node *))
{
    while (head)
    {
        operation(head);   // 执行传入的操作函数
        head = head->next; // 移动到下一个节点
    }
}

// 反转链表，递归实现
Node *reverseLinkedList(linkedList *head)
{
    if (!head || !head->next)
    {
        return head; // 如果链表为空或只有一个节点，直接返回
    }
    Node *node = reverseLinkedList(head->next); // 递归反转后续链表

    head->next->prev = head->next->next; // 更新下一个节点的前一个节点指针
    head->next->next = head;             // 更新下一个节点的下一个节点指针
    if (!head->prev)
    {
        head->prev = head->next; // 如果是头节点，更新前一个节点的指针
        head->next = NULL;       // 将头节点的下一个节点指针设为NULL
    }
    return node; // 返回反转后的链表
}

// 清空链表并释放内存
void clearLinkedList(linkedList **head)
{
    if (!(*head))
    {
        return; // 如果链表为空，直接返回
    }
    clearLinkedList(&(*head)->next); // 递归清空下一个节点
    *head = NULL;                    // 更新当前节点为NULL
    free(*head);                     // 释放当前节点的内存
}

// 检查双向链表是否有效
bool isDoublyLinkedListValid(linkedList *head)
{
    if (!head)
    {
        return true; // 空链表被认为是有效的
    }

    linkedList *current = head;
    linkedList *prev = NULL;

    while (current)
    {
        if (current->prev != prev)
        {
            return false; // 前一个节点指针不正确
        }

        prev = current;
        current = current->next;
    }

    // 确保最后一个节点的下一个节点指针是NULL
    return (prev->next == NULL);
}

五、主文件（贼拉详细）

//D :A_Shun_Exclusivelife_ofuniversitycode_collectionCVSCODEMy_CodeCtestTenT_10_first.c
#include

#include "DataStructure/my_double_basic_linklist.h"
// ANSI_COLOR_RED 是一个宏定义，用于设置控制台文本颜色为红色

#define ANSI_COLOR_RED "x1b[31m"
// ANSI_COLOR_RESET 是一个宏定义，用于重置控制台文本颜色为默认值

#define ANSI_COLOR_RESET "x1b[0m"
    void

    print(linkedList *node)

{

    if (node)

    {

        int value = node->value;

        if (!node->next && !node->prev)

        {

            printf("nullnull", value);

        }

        else if (!node->prev)

        {

            printf("nullnulln", value);

        }

    }

}
// Function to generate a random integer between min and max

int randomInt(int min, int max)

{

    return min + rand() % (max - min + 1);

}
// Function to print a menu for user selection

void printMenu()

{

    printf("n╭────────────────────────────╮n");

    printf("│ Linked List Test Menu     │n");

    printf("╰────────────────────────────╯n");

    printf("1. 插入节点至链表头部n");

    printf("2. 插入节点至链表尾部n");

    printf("3. 插入节点至指定位置n");

    printf("4. 删除链表头部的节点n");

    printf("5. 删除链表尾部的节点n");

    printf("6. 删除指定位置的节点n");

    printf("7. 修改节点的值n");

    printf("8. 根据值查找节点n");

    printf("9. 根据位置查找节点n");

    printf("10. 检查值是否存在n");

    printf("11. 获取链表长度n");

    printf("12. 反转链表n");

    printf("13. 清空链表n");

    printf("14. 查看链表n");

    printf("15. 随机测试n");

    printf("0. 退出n");

    printf("请选择操作: _ bb");

}
// 插入节点至链表头部

void insertNodeAtHead_case(linkedList **head)

{

    int N;

    printf("正在执行插头操作...n");
    do

    {

        printf("执行此操作的次数 (正整数): ");

        scanf("%d", &N);
        if (N

轻松掌握C语言双链表编程：从零到高手，实用示例全解析！

一、介绍

一、双链表简介

二、构建双链表的数据结构

节点的定义

节点的创建

查找

1. 根据位置查找

2. 根据值查找

3. 检查链表中是否存在特定的值

插入

1. 插入头部

1.1 不带返回值

1.2 带返回值

2. 插入尾部

2.1 不带返回值

2.2 带返回值

3. 一般插入

3.1 不带返回值

3.2 带返回值

删除

1. 删除头部

1.1 不带返回值

1.2 带返回值

2. 删除尾部

2.1 不带返回值

2.2 带返回值

3. 一般删除

3.1 不带返回值

3.2 带返回值

修改值

遍历

翻转

1. 递归实现

2. 迭代实现

九 清空链表

检查是否是合理的双向链表

三、函数接口（注释详细）

四、函数实现（注释详细）

五、主文件（贼拉详细）

相关文章

发布评论 取消回复

法医

百度搜索：蓝易云 – JDK1.8在LINUX下安装教程

万字长文 | MatrixOne 的 MySQL 协议实现

一个简单小工具obtool，助你成为Oceanbase高级专家

九清空链表

发布评论取消回复