双向链表与双向循环链表详解

"这篇资料详细介绍了双向链表和双向循环链表的概念、结构以及相关算法实现，重点关注在C语言中的数据结构表示。" 双向链表是一种线性数据结构，其特点是每个节点不仅包含数据，还包含两个指针，分别指向当前节点的前驱节点和后继节点。这种设计使得在链表中进行前向和后向遍历成为可能。节点的典型结构如下： ```c typedef struct DuLNode{ ElemType data; DuLNode* prior, *next; } DuLNode, *DuLinkList; ``` 这里的`ElemType`代表节点数据的类型，`DuLNode`是定义的结构体，包含数据域`data`和两个指针域`prior`和`next`，分别用于链接前后节点。`DuLinkList`是结构体指针，通常用于表示整个链表。 双向链表可以分为两类：非循环双向链表和双向循环链表。本章主要讨论的是带头结点的双向循环链表，它的特点是链表的最后一个节点的`next`指针指向链表的第一个节点，形成一个环状结构，而第一个节点的`prior`指针则指向最后一个节点，形成双向循环。 在双向循环链表中，一些基本操作如求链表长度和插入新节点可以高效地实现。例如，求链表长度的算法与单循环链表类似： ```c int ListLength(DuLinkList L) { int i = 0; DuLinkList p = L->next; // p 指向第一个结点 while (p != L) { // p 没到表头 i++; p = p->next; } return i; } ``` 在双向循环链表中插入节点，首先要找到插入位置的前一个节点`p`，然后创建新节点`s`，并执行以下步骤来完成插入操作： 1. 将新节点`s`的`next`域指向节点`p`的后继节点（`s->next = p->next`）。 2. 如果`p`不是最后一个节点，更新`p`的后继节点的`prior`指针，使其指向`s`（`p->next->prior = s`）。 3. 更新`p`的`next`指针，使其指向`s`（`p->next = s`）。 4. 最后，设置新节点`s`的`prior`指针指向`p`（`s->prior = p`）。 这样的操作确保了链表的循环性不会被破坏，并且节点的前后连接正确。 双向循环链表的优势在于它可以提供更灵活的遍历方式，允许从任一方向开始遍历，对于需要频繁进行正向和反向遍历的操作，它比单链表更具效率。然而，由于每个节点需要额外的两个指针，空间效率相对较低。在实际应用中，应根据具体需求权衡选择合适的数据结构。