Java数据结构-线性表之循环链表

循环链表的定义:将单链表的尾节点的空指针改为指向头结点的指针,这样的单链表就变成单循环链表了,也叫循环链表。

下面摘抄了《大话数据结构》中的一段分析。如下图:
Java数据结构-线性表之循环链表

解释:
循环链表里面的头结点和单链表里面的头结点是一样的,都是为了操作统一和方便而设定的,不是必须节点。

这里为了方便操作还会进行一种改变,就是去掉循环链表的头指针,而增加一个指向循环链表尾部节点的尾指针。
这样相对来说可以通过O(1)时间访问到尾节点了,同时在进行循环链表合并操作时更加方便了。

举一个在《大话数据结构》里面的例子,如下图

Java数据结构-线性表之循环链表

通过上述例子可以看出去掉头结点而增加尾节点的方法确实对于某些操作而言是较好的改进。 

相关推荐