双链表详解：初始化与插入操作

"5.双链表的简介.md" 在数据结构中，链表是一种重要的线性数据结构，其中的数据元素不是在物理位置上相邻，而是通过指针连接。双链表是链表的一种变体，它在每个节点中不仅包含指向下一个节点的指针，还包含一个指向前一个节点的指针，这使得双向操作变得可能。 ### 单链表与双链表的比较 #### 单链表 单链表每个节点只包含一个指针，通常称为`next`指针，用于指向序列中的下一个节点。由于只有一个方向的链接，单链表的插入和删除操作相对简单，但其主要缺点是无法直接从前一个节点访问当前节点，只能从头节点开始按顺序查找，这在需要反向遍历或随机访问时效率较低。 #### 双链表 双链表的每个节点包含两个指针，一个`next`指针指向下一个节点，另一个`prior`指针指向前一个节点。这种设计使得双链表在进行插入和删除操作时更加灵活，因为可以从前后两个方向进行。然而，双链表的存储空间需求比单链表高，因为每个节点需要额外存储一个指针，所以其存储密度较低。 ### 双链表的初始化 在C语言中，我们可以定义一个结构体来表示双链表的节点，如`DNode`，包括数据域`data`以及前驱`prior`和后继`next`两个指针。`DLinkList`是一个指向`DNode`类型的指针，通常用作链表的头指针。初始化双链表通常包括分配一个头结点并设置其`prior`和`next`指针为`NULL`。 ```c typedef struct DNode{ ElemType data; // 数据域 struct DNode* prior, *next; // 前驱和后继指针 } DNode, *DLinkList; // 初始化双链表 bool InitDLinkList(DLinkList& L){ L = (DNode*)malloc(sizeof(DNode)); // 分配一个头结点 if(L == NULL) // 内存不足，分配失败 return false; L->prior = NULL; // 头结点的prior永远指向NULL L->next = NULL; // 头结点之后暂时还没有结点 return true; } // 判断双链表是否为空（带头结点） bool Empty(DLinkList L){ if(L->next == NULL) return true; else return false; } ``` ### 双链表的插入操作 插入新节点到双链表中通常有两种情况： 1. 在指定节点`p`之后插入节点`s`。首先，更新`s`的`next`和`prior`指针，然后更新`p`的`next`指针和`p->next`的`prior`指针。 2. 需要注意的是，如果`p`是链表的最后一个节点，`p->next`为空，直接插入会导致空指针错误，因此在插入之前需要检查这种情况。 ```c // ① 在p结点之后插入s结点（考虑了p是尾结点的情况） bool InsertNextDNode(DNode* p, DNode* s){ if(p == NULL || s == NULL) // 非法参数 return false; if(p->next == NULL){ // 如果p是尾结点 p->next = s; s->prior = p; s->next = NULL; } else { s->next = p->next; s->prior = p; p->next->prior = s; p->next = s; } return true; } ``` ### 双链表的其他操作 除了插入，双链表还支持其他常见的操作，如删除节点、反向遍历、查找特定节点等。删除操作与插入类似，需要同时更新被删除节点及其前后节点的指针。反向遍历只需从尾节点开始向前移动即可。查找特定节点可以通过正向或反向遍历实现，具体取决于查找效率的需求。 双链表是一种灵活的数据结构，提供了对链表的双向访问能力，但需要更多的存储空间。在需要频繁进行反向操作或对性能要求较高的场景下，双链表是一个很好的选择。