数据结构的C/C++描述02.02:循环单链表 · 双向链表 木灵的炼金工作室

循环单链表

所谓循环单链表,就是将尾节点的next指针设置指向头节点的单链表。循环链表有着非常好的数据连续性,从任何一点开始都可以访问整个链表。为了维护这种连续性,我们一般不在循环链表中引入实际的头节点,仅仅使用虚拟的头指针,此时我们需要维护链表的长度,或维护遍历起始点的地址,从而使得遍历在合适的时间截止。但是,没有实际头节点的链表在插入或删除的编码上就需要格外小心。 当然,引入头节点也是一个不错的选择,那么我们需要维护这个头节点的地址,以便在遍历中忽略它。

由于循环单链表的实现与普通单链表的实现极为相似,故不再写例程。

双向链表

考虑不使用链表封装类时的单链表的删除操作:(由于直接操作指针的效率往往更高,所以我们在编码实践中很少使用封装类)
如果我们需要即刻删除目前指针所指的元素,单链表无法在O(1)时间内完成:因为删除操作需要找到它的前导元,而这个操作对于长度为n的链表需要O(n)的渐近时间复杂度。

因此我们可以很自然的想到,如果对于每一个节点,维护指向它前导元的指针,那么这一操作的渐近时间复杂度会降到O(1)。

双向链表节点的实现一般如下:

template<class T>
struct doubleChainNode {
    T val;
    doubleChainNode<T> *next, *pre;
}

双向链表常用的操作是删除节点和新增节点,这两者均须注意同一个要点:要保证操作过程中时时刻刻保持插入点/删除点的左右元素是可访问的。这可以通过维护指针来做到,也可以通过程序中对操作的谨慎控制达到。
在写这样的程序时,随时画图打草稿总是没错的。


Copyright AmachiInori 2017-2021. All Right Reserved.
Powered By Jekyll.
amachi.com.cn