循环单链表需要注意的小问题

时间:2021-01-21 06:52:13

一: 将指针指向表尾

        一般情况下,当我们创建一个单链表时,通常会将指针指向表头。但当我们创建一个循环单链表而且需要对表头表尾频繁操作时,我们是否还会为它创建一个头指针呢?下面小编来分析一下: 

        定义头指针: 当我们查找表头时,时间复杂度为O(1),当我们查找表尾时,时间复杂度为O(n);

        定义尾指针: 当我们查找表头时,因为尾指针和头指针相连,我们只需查找尾指针的下一个节点,时间复杂度为: O(1),当我们查找头指针时,时间复杂度为: O(1);

        很显然,当我们需要对表头表尾频繁操作时,定义尾指针会完虐定义头指针。

二: 不要陷入死循环

        循环单链表没有明显的结束条件,当我们不注意时,很容易陷入死循环。此时,我们可以设置一个标记点作为循环的标记,当我们知道表长,我们也可以设置一个计数器来结束循环。