前段时间我使用 C 语言实现了双向带头循环链表。这个数据结构在逻辑上比单链表稍微复杂一些但理解之后操作的规律性其实很强。整个实现基于结构体定义的结点。每个结点包含三部分存储的元素、指向前一个结点的指针以及指向后一个结点的指针。正是这两个指针让链表具备了双向遍历的能力。为了简化插入和删除操作我引入了一个头结点哨兵结点它不存储任何有效数据主要作用是作为链表的“锚点”——通过它既能快速访问链表头部也能直达链表尾部。初始化头结点时我创建了一个新结点将其 prev 和 next 指针都指向它自己形成一个空链表的初始状态。为了方便地生成新结点我封装了一个 BuyNode 函数。该函数内部通过 malloc 分配内存并将新结点的前后指针都初始化为指向它自身然后返回该结点的指针。每次插入数据时我都会先调用这个函数获取新结点再进行链接操作。在尾插时新结点的 prev 应指向当前尾结点即头结点的 prevnext 指向头结点然后让头结点的 prev 指向新结点原尾结点的 next 也指向新结点这样就完成了尾部插入。头插的逻辑类似新结点的 prev 指向头结点next 指向原第一个结点接着让原第一个结点的 prev 指向新结点最后更新头结点的 next 指向新结点即可。尾删操作需要释放尾结点空间。具体步骤是将尾结点的前驱结点的 next 指向头结点同时将头结点的 prev 指向该前驱结点最后释放尾结点并将其置为 NULL防止野指针。头删的操作与尾删类似只是操作对象换成了头结点后的第一个有效结点调整其前后结点的指向然后释放当前头结点并置空。以下是我具体的代码实现
前段时间我使用 C 语言实现了双向带头循环链表。这个数据结构在逻辑上比单链表稍微复杂一些但理解之后操作的规律性其实很强。整个实现基于结构体定义的结点。每个结点包含三部分存储的元素、指向前一个结点的指针以及指向后一个结点的指针。正是这两个指针让链表具备了双向遍历的能力。为了简化插入和删除操作我引入了一个头结点哨兵结点它不存储任何有效数据主要作用是作为链表的“锚点”——通过它既能快速访问链表头部也能直达链表尾部。初始化头结点时我创建了一个新结点将其 prev 和 next 指针都指向它自己形成一个空链表的初始状态。为了方便地生成新结点我封装了一个 BuyNode 函数。该函数内部通过 malloc 分配内存并将新结点的前后指针都初始化为指向它自身然后返回该结点的指针。每次插入数据时我都会先调用这个函数获取新结点再进行链接操作。在尾插时新结点的 prev 应指向当前尾结点即头结点的 prevnext 指向头结点然后让头结点的 prev 指向新结点原尾结点的 next 也指向新结点这样就完成了尾部插入。头插的逻辑类似新结点的 prev 指向头结点next 指向原第一个结点接着让原第一个结点的 prev 指向新结点最后更新头结点的 next 指向新结点即可。尾删操作需要释放尾结点空间。具体步骤是将尾结点的前驱结点的 next 指向头结点同时将头结点的 prev 指向该前驱结点最后释放尾结点并将其置为 NULL防止野指针。头删的操作与尾删类似只是操作对象换成了头结点后的第一个有效结点调整其前后结点的指向然后释放当前头结点并置空。以下是我具体的代码实现
