当前位置：首页 > 行业动态 > 正文

C数据结构之双链表详细示例分析

定义节点结构体，“ c，typedef struct Node {， int data;， struct Node* prev;， struct Node* next;，} Node;，` 初始化头节点，` c，Node* initList() {， Node* head = (Node*)malloc(sizeof(Node));， head->data = 0;， head->prev = NULL;， head->next = NULL;， return head;，}，` 插入节点到头部，` c，void insertHead(Node* head, int value) {， Node* newNode = (Node*)malloc(sizeof(Node));， newNode->data = value;， newNode->prev = NULL;， newNode->next = head;， if (head != NULL) {， head->prev = newNode;， }， head = newNode;，}，` 删除指定节点，` c，void deleteNode(Node* head, Node* node) {， if (node == NULL) return;， if (node->prev != NULL) {， node->prev->next = node->next;， } else {， head = node->next;， }， if (node->next != NULL) {， node->next->prev = node->prev;， }， free(node);，}，` 遍历双链表，` c，void traverse(Node* head) {， Node* current = head;， while (current != NULL) {， printf("%d ", current->data);， current = current->next;， }， printf("，");，}，` 示例使用，` c，int main() {， Node* head = initList();， insertHead(head, 1);， insertHead(head, 2);， insertHead(head, 3);， traverse(head); // 输出: 3 2 1 ， deleteNode(head, head->next); // 删除值为2的节点， traverse(head); // 输出: 3 1 ， return 0;，}，“

C 数据结构之双链表详细示例分析

在数据结构的学习中，双链表是一种非常重要的线性数据结构，它相较于单链表，在节点结构上增加了指向前驱节点的指针，这使得双链表在插入、删除等操作上具有更高的灵活性和效率，下面将通过详细的代码示例和分析，深入探讨 C 语言中双链表的实现与应用。

一、双链表节点结构定义

我们需要定义双链表的节点结构体，一个典型的双链表节点包含三个部分：数据域、指向前驱节点的指针（prev）和指向后继节点的指针（next），以下是在 C 语言中的节点结构定义示例：

typedef struct DLinkNode {
    int data;                // 数据域，存储节点的数据
    struct DLinkNode *prev;  // 指向前驱节点的指针
    struct DLinkNode *next;  // 指向后继节点的指针
} DLinkNode, *DLinkList;     // 定义节点类型和链表类型

在这个结构体中，data用于存储节点的实际数据，prev和next则分别用于连接前驱和后继节点，从而实现双向的链接关系。

二、双链表基本操作函数

（一）初始化双链表

初始化操作是创建一个空的双链表，即头节点的next和prev都指向自己，表示链表中暂时没有其他节点。

void InitDLinkList(DLinkList *L) {
    *L = (DLinkNode *)malloc(sizeof(DLinkNode));  // 为头节点分配内存空间
    if (*L == NULL) {
        printf("Memory allocation failed!
");
        exit(1);
    }
    (*L)->data = 0;  // 头节点数据域可根据实际情况设定，这里设为 0
    (*L)->prev = *L;
    (*L)->next = *L;
}

（二）插入节点

在双链表中插入节点可以分为在头部插入、在尾部插入和在指定位置插入等情况，这里以在头部插入为例进行说明。

void InsertHead(DLinkList L, int e) {
    DLinkNode *s = (DLinkNode *)malloc(sizeof(DLinkNode));  // 创建新节点
    if (s == NULL) {
        printf("Memory allocation failed!
");
        exit(1);
    }
    s->data = e;  // 设置新节点的数据
    s->next = L->next;  // 新节点的后继指向原头节点的后继
    s->prev = L;         // 新节点的前驱指向头节点
    L->next->prev = s;   // 原头节点的后继的前驱指向新节点
    L->next = s;         // 头节点的后继指向新节点
}

在这个过程中，我们首先为新节点分配内存并设置其数据，然后调整新节点与原有节点之间的指针关系，使其正确地插入到链表头部，插入操作完成后，链表的结构会相应地发生变化，新节点成为新的头节点的后继节点，而原头节点的后继节点的前驱指针也更新为新节点。

（三）删除节点

同样，删除节点也可以根据不同的需求在头部、尾部或指定位置进行删除，以下以删除指定值为e的节点为例：

int DeleteElem(DLinkList L, int e) {
    DLinkNode *p = L->next;  // 从头节点的后继开始遍历链表
    while (p != L && p->data != e) {
        p = p->next;
    }
    if (p == L) {
        return 0;  // 未找到值为 e 的节点
    }
    p->prev->next = p->next;  // 前驱节点的后继指向后继节点
    p->next->prev = p->prev;  // 后继节点的前驱指向前驱节点
    free(p);  // 释放被删除节点的内存空间
    return 1;  // 删除成功
}

在删除操作中，我们先遍历链表找到值为e的节点p，如果找到了，就调整其前驱和后继节点的指针，跳过该节点，然后释放节点的内存空间，如果遍历完整个链表都没有找到，则返回删除失败的标志。

三、示例程序

下面是一个完整的示例程序，展示了如何使用上述定义和操作函数来创建和操作一个双链表：

#include <stdio.h>
#include <stdlib.h>
typedef struct DLinkNode {
    int data;
    struct DLinkNode *prev;
    struct DLinkNode *next;
} DLinkNode, *DLinkList;
void InitDLinkList(DLinkList *L) {
    *L = (DLinkNode *)malloc(sizeof(DLinkNode));
    if (*L == NULL) {
        printf("Memory allocation failed!
");
        exit(1);
    }
    (*L)->data = 0;
    (*L)->prev = *L;
    (*L)->next = *L;
}
void InsertHead(DLinkList L, int e) {
    DLinkNode *s = (DLinkNode *)malloc(sizeof(DLinkNode));
    if (s == NULL) {
        printf("Memory allocation failed!
");
        exit(1);
    }
    s->data = e;
    s->next = L->next;
    s->prev = L;
    L->next->prev = s;
    L->next = s;
}
int DeleteElem(DLinkList L, int e) {
    DLinkNode *p = L->next;
    while (p != L && p->data != e) {
        p = p->next;
    }
    if (p == L) {
        return 0;
    }
    p->prev->next = p->next;
    p->next->prev = p->prev;
    free(p);
    return 1;
}
void PrintDLinkList(DLinkList L) {
    DLinkNode *p = L->next;
    while (p != L) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("
");
}
int main() {
    DLinkList L;
    InitDLinkList(&L);
    InsertHead(L, 1);
    InsertHead(L, 2);
    InsertHead(L, 3);
    PrintDLinkList(L);  // 输出：3 2 1
    DeleteElem(L, 2);
    PrintDLinkList(L);  // 输出：3 1
    return 0;
}

在这个示例程序中，我们首先初始化了一个空的双链表L，然后使用InsertHead函数在链表头部依次插入了元素 1、2、3，接着打印链表，可以看到元素按照插入的顺序排列，然后我们删除了值为 2 的节点，再次打印链表时，发现链表中只剩下了元素 3 和 1。

四、性能分析与应用场景

（一）性能分析

时间复杂度：在双链表中，插入和删除操作的时间复杂度平均为 O(1)，因为不需要像单链表那样遍历链表来找到插入或删除的位置，查找操作的时间复杂度为 O(n)，最坏情况下需要遍历整个链表才能找到目标元素，总体而言，双链表在插入和删除操作上具有较高的效率，但在查找操作上相对单链表没有明显优势。

空间复杂度：由于每个节点需要额外的指针来存储前驱和后继信息，所以双链表的空间复杂度相对较高，每个节点占用的内存空间比单链表多一些，这种额外的空间开销换来了操作上的便利性和高效性。

（二）应用场景

数据缓存：在一些操作系统或应用程序中，经常需要对数据进行缓存以提高访问速度，双链表可以方便地实现数据的插入和删除操作，例如在实现 LRU（最近最少使用）缓存算法时，可以使用双链表来维护缓存数据的访问顺序，快速地将最近访问的数据移动到链表头部，而将最久未访问的数据移动到链表尾部并最终删除。

图的邻接表表示：在图的数据结构中，可以使用双链表来实现图的邻接表表示，每个顶点对应一个链表，链表中的节点表示与该顶点相邻的其他顶点，通过双链表可以方便地遍历顶点的邻接顶点，进行图的遍历、搜索等操作。

任务调度系统：在一些实时系统中，任务调度是一个关键的功能，双链表可以用来维护任务队列，根据任务的优先级或其他属性将任务插入到合适的位置，并且能够快速地从队列中取出任务进行处理，保证系统的高效运行。

五、归纳

C 语言中的双链表是一种重要的数据结构，它具有双向链接的特点，使得插入、删除等操作更加灵活和高效，通过合理地定义节点结构和实现各种操作函数，我们可以方便地使用双链表来解决实际问题，在实际应用中，需要根据具体的需求和场景选择合适的数据结构，充分发挥双链表的优势，提高程序的性能和效率，在使用双链表时也需要注意内存管理等问题，避免出现内存泄漏等错误，希望本文对您理解和掌握 C 语言数据结构中的双链表有所帮助。

操作 时间复杂度 空间复杂度 备注
初始化 O(1) O(1) 为头节点分配内存
插入（头部） O(1) O(1) 创建新节点并调整指针
删除（指定值） O(n) O(1) 遍历查找并调整指针
查找（指定值） O(n) O(1) 遍历链表查找元素
打印 O(n) O(1) 遍历输出节点数据
插入（尾部） O(1) O(1) 同头部插入类似
删除（头部） O(1) O(1) 直接调整头节点指针
插入（指定位置） O(n) O(1) 先遍历找到位置再插入
删除（指定位置） O(n) O(1) 先遍历找到位置再删除
获取长度 O(n) O(1) 遍历统计节点个数
反转链表 O(n) O(1) 调整每个节点的前驱和后继指针
合并链表 O(1) O(1) 将两个链表的头尾相连
拆分链表 O(n) O(1) 根据条件遍历拆分节点
判断是否为空 O(1) O(1) 检查头节点指针
获取头节点数据 O(1) O(1) 直接访问头节点数据成员
双链表 数据结构 示例分析
本站发布或转载的文章及图片均来自网络，其原创性以及文中表达的观点和判断不代表本站，有问题联系侵删！
本文链接：http://www.xixizhuji.com/fuzhu/150073.html
0

相关文章