循环链表的实现

  • A+

循环链表与普通的链表差不多

不同的是普通链表的最后一个结点的next为null

而循环链表的最后一个结点的next为链表的头结点

这样子就将链表头尾相连了

形成一个环


这里同样的抽象一个类为数据结点

声明一个记录链表长度的变量

不同的是这里直接声明一个用于保存链表最后结点的引用

为什么不是头结点呢

因为循环只要用最后结点就可以轻松找到头结点了啊


这里是循环链表的构造函数

循环链表的空链表表示方式就是

最后结点为头结点,并且next指向自身

这里就是初始化链表为这么一种情况

①新建一个结点为头结点

②使它当做为最后一个结点

③并使它的下一个结点next赋值为自身


在尾部添加元素

其实这里没什么好说的了

①新建一个新的结点

②赋值数据,赋值下一个结点为原最后结点的下一个结点(头结点)

③指定当前最后结点的下一结点为新加结点

④指定最后结点为新加结点

⑤链表的长度+1


在链表的头部添加结点

①通过已知的最后结点获取到头结点

②新建结点,赋值数据,指定下一个节点为头结点的下一个结点

③指定头结点的下一个节点为新加结点

④注意,如果是空链表时,新加的结点就是尾结点,这时候尾结点就改变了,要对尾结点的引用修改为新加结点

⑤链表长度+1


这个方法已经说过很多次了

不在乎这一次了^_^

①第一步当然是判断一下结点索引的合法性啦,要不然都要到火星去了

②通过尾结点得到头结点来做尾结点的判断

③声明一个计数器i初始化为对应结点node的位置

④通过遍历找到index==i位置的结点node

⑤最后当然就是返回这个结点了(注意这里0为头结点)


这个就不说了

排除头结点的特殊情况

直接获取到指定位置的结点取出数据就好


在指定位置插入新结点

可以去看看普通链表的图解

①先获取要插入结点的前一个结点

②判断结点和被插入结点是否存在,

这里preNode.next == this._last.next表示preNode是

链表中的最后一个结点

则可以证明被插入的结点就不存在了

③排除了意外,就新建结点,赋值数据,指定next下一个结点为被插节点

④指定被插结点的上一个结点的下一个结点为新建结点

(插入操作是不会修改尾结点的,因为被插元素要存在,而且被插结点永远在后面)

⑤链表的长度+1


这里同样的可以去看普通链表的图解

原理是一样的

我就不多说了

这里需要注意的就是要删除最后一个元素了

if(deleteNode == this._last)

如果将最后的结点删除了

那么最后结点的引用就要修改为被删结点(当前尾结点)的上一个结点


通过某个结点遍历整个链表

循环链表就是有这么一个功能

他可以用任意一个结点就可以遍历整个链表了

这里需要注意的就是特殊的头结点

它是没有数据的,所以要排除这个头结点

其他的从这个结点遍历到这个结点的前一个就好啦


测试

 

结果

循环链表的实现


链接两条链表

很明显的思路就是主链表的尾与添加链表的第一结点相连

添加链表的尾结点与主链表的头结点相连

这样又组成一条新的链表

①获取到主链表的头结点

②获取添加链表的第一个结点

③尾一相连,赋值给主链表尾结点的下一节点为添加链表的第一个结点

④尾头相连,赋值给添加链表尾结点的下一个结点为主链表的头结点

⑤链表的长度增加对应的长度

⑥设置主链表的尾结点添加链表的尾结点

测试

结果

循环链表的实现

  • 我的微信
  • 扫一扫加我微信
  • weinxin
  • 微信我的
  • 我微信扫一扫加
  • weinxin

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: