单链表,循环链表的实现
循环链表如图所示,与单链表相比较,就是最后一个节点又赋值给了第一个节点,构成了一个环。
所以我们是先的思路也就只在单链表上增加:让最后一个节点指向第一个节点这一个功能。
在循环链表中没有最后一个节点的概念(闭合循环),也就没有了单链表中显示,最后追加节点等方法。
我们可以由易到难依次解决:
如果只有一个节点,那么它自身就是一个循环链表,自己指向自己。
如果要添加一个节点,有三步:
第一:设置首节点为添加节点的下一个节点
第二:把新节点添加到当前节点之后,作为当前节点的下一个节点
第三:把新节点的下一个节点赋值为首节点。
核心代码如下:
//插入一个节点,是插入到一个节点的后面
public void afterAdd(LoopNode node){
//取当前节点作为型节点的下一个节点
LoopNode nextNext = next;
//把新节点插入当前节点后面
this.next=node;
//把当前节点追加到新节点后面,完成循环
node.next=nextNext;
}
我们通过代码验证发现:
如果在第一步中只是简单的写成
//取当前节点作为型节点的下一个节点
LoopNode nextNext = this;
那么最后返回的不是首节点,而是上一个节点
问题出在:我们应该把next声明为全局变量,把当前节点赋给next,让next参与。
//下一个节点
LoopNode next = this;
然后把上述代码改为:
//插入一个节点,是插入到一个节点的后面
public void afterAdd(LoopNode node){
//取当前节点作为型节点的下一个节点
LoopNode nextNext = next;
//把新节点插入当前节点后面
this.next=node;
//把当前节点追加到新节点后面,完成循环
node.next=nextNext;
}
验证通过,构成循环,并且可以看出第五个节点自己构成循环链表