首页 / 算法 / 数据结构与算法（四）-线性表之循环链表
数据结构与算法（四）-线性表之循环链表
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了数据结构与算法（四）-线性表之循环链表，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3213字，纯文字阅读大概需要5分钟。
内容图文
前言：前面几篇介绍了线性表的顺序和链式存储结构，其中链式存储结构为单向链表（即一个方向的有限长度、不循环的链表），对于单链表，由于每个节点只存储了向后的指针，到了尾部标识就停止了向后链的操作。也就是说只能向后走，如果走过了，就回不去了，还得重头开始遍历，所以就衍生出了循环链表
一、简介
- 若链表为空，则头结点的next结点还是指向其本身，即head.next=head；
- 尾节点的next指针指向head结点，即头尾相连；
- 判断是否遍历了完，直接判断next==head即可；
- 由单链表变化的循环也成为单向循环链表；
- 循环链表的特点是无须增加存储量，仅对表的链接方式稍作改变，即可使得表处理更加方便灵活；
二、单向循环链表的实现
public
class LoopChain<T> {
//尾结点直接引用private Node<T> tail;
//链长度private Integer size;
//初始化 LoopChain() {
tail = new Node<T>();
tail.setNext(tail);
}
public Node<T> remove(Integer index) throws Exception {
//获取该位置的上一个节点
Node<T> s = getNode(index - 1);
//获取该位置节点的下一个节点
Node<T> next = getNode(index).getNext();
//将本节点的next节点放在本节点的前一个节点的next节点位置 s.setNext(next.getNext());
return next;
}
publicvoid add(T t,Integer index) throws Exception {
//获取该位置的上一个节点
Node<T> s = getNode(index - 1);
//创建新节点
Node<T> p = new Node<>();
p.setObject(t);
//将本节点的next节点放入新节点的next节点 p.setNext(s.getNext());
//将新节点放入本节点的next节点位置 s.setNext(p);
}
public T get(Integer index) throws Exception {
return (T)getNode(index).getObject();
}
private Node<T> getNode(Integer index) throws Exception {
if (index > size || index < 0)
thrownew Exception("index outof length");
//取头节点
Node<T> p = tail.next;
for (int i = 0; i < index; i++)
p = p.getNext();
return p;
}
class Node<T> {
private Object object;
private Node next;
public Object getObject() {
return object;
}
publicvoid setObject(Object object) {
this.object = object;
}
public Node getNext() {
return next;
}
publicvoid setNext(Node next) {
this.next = next;
}
}
}
获取元素：
public T get(Integer index) throws Exception {
return (T)getNode(index).getObject();
}
private Node<T> getNode(Integer index) throws Exception {
if (index > size || index < 0)
thrownew Exception("index outof length");
//取头节点
Node<T> p = tail.next;
for (int i = 0; i < index; i++)
p = p.getNext();
return p;
}
插入元素：
public
void add(T t,Integer index) throws Exception {
//获取该位置的上一个节点
Node<T> s = getNode(index - 1);
//创建新节点
Node<T> p = new Node<>();
//将本节点的next节点放入新节点的next节点 p.setNext(s.getNext());
//将新节点放入本节点的next节点位置 s.setNext(p);
}
移除元素：
public Node<T> remove(Integer index) throws Exception {
//获取该位置的上一个节点
Node<T> s = getNode(index - 1);
//获取该位置节点的下一个节点
Node<T> next = getNode(index).getNext();
//将本节点的next节点放在本节点的前一个节点的next节点位置 s.setNext(next.getNext());
return next;
}
三、问题
本系列参考书籍：
《写给大家看的算法书》
《图灵程序设计丛书 算法 第4版》
原文：https://www.cnblogs.com/lfalex0831/p/9669279.html
内容总结
以上是互联网集市为您收集整理的数据结构与算法（四）-线性表之循环链表全部内容，希望文章能够帮你解决数据结构与算法（四）-线性表之循环链表所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。