上一个blog写到 非循环单向链表java 实现。在此基础上开发循环单向链表,代码如下:
import java.util.List; public class CycleSingleLinkedList<E> extends AbstractSingleLinkedList<E> implements List<E> ,java.io.Serializable { private static final long serialVersionUID = -2856058002090891038L; private transient Entry<E> header = null; private transient int size ; // 指向最未端 private transient Entry<E> lastElement = null; @Override public SingleListIterator<E> singleListIterator() { return new SingleIterator(); } public CycleSingleLinkedList() { header = new Entry<E>(null, header); lastElement = header; size ++; } public E getLast() { return lastElement.element; } @Override public boolean remove(Object o) { boolean result = false; if (o == null) { for (Entry<E> beforElement = header,currentElement = beforElement.next; currentElement != header; beforElement = beforElement.next,currentElement = beforElement.next) { if (currentElement != null && currentElement.element == null) { beforElement.next = currentElement.next; result = true; if (currentElement.equals(lastElement)) { lastElement = beforElement; } size --; } } } else { for (Entry<E> beforElement = header,currentElement = beforElement.next; currentElement != header; beforElement = beforElement.next,currentElement = beforElement.next) { if (currentElement != null && o.equals(currentElement.element)) { beforElement.next = currentElement.next; result = true; if (currentElement.equals(lastElement)) { lastElement = beforElement; } size --; } } } return result; } @Override public E remove(int index) { if (index < 0 || index >= size) { throw new IndexOutOfBoundsException("Index: "+index+ ", Size: "+size); } Entry<E> e = header; Entry<E> before = header; for (int i = 0; i < index; i++) { before = before.next; } e = before.next; before.next = e.next; if (index == size() -1) { lastElement = before; } size --; return e.element; } @Override public void add(int index,E element) { if (index < 0 || index >= size) { throw new IndexOutOfBoundsException("Index: "+index+ ", Size: "+size); } Entry<E> e = header; Entry<E> before = header; for (int i = 0; i < index; i++) { before = before.next; } e = before.next; before.next = new Entry<E>(element, e); size ++; } @Override public boolean add(E e) { lastElement.next = new Entry<E>(e, header); lastElement = lastElement.next; size ++; return true; } @Override public E get(int index) { return entry(index).element; } private Entry<E> entry(int index) { if (index < 0 || index >= size) { throw new IndexOutOfBoundsException("Index: "+index+ ", Size: "+size); } Entry<E> e = header; for (int i = 0; i <= index; i++) { e = e.next; } return e; } @Override public int size() { return size - 1; } private static class Entry<E> { E element; Entry<E> next; public Entry(E element, Entry<E> next) { this.element = element; this.next = next; } } private class SingleIterator implements SingleListIterator<E> { // 最后访问的结点 private Entry<E> lastReturned = header.next; // 中间访问的结点 private Entry<E> beforeElement = header; // 最前访问的结点 private Entry<E> previousElement = beforeElement; @Override public boolean hasNext() { // 非循环单链表最后是null return lastReturned != header; } @Override public E next() { previousElement = beforeElement; beforeElement = lastReturned; E e = lastReturned.element; lastReturned = lastReturned.next; return e; } @Override public void remove() { previousElement.next = lastReturned; // 删除的是中间的结点,删除完后,中间的结点指向最前结点 beforeElement = previousElement; size --; } @Override public void set(E e) { beforeElement.element = e; } @Override public void add(E e) { // 若前后结点与中单结点相等,是在执行删除后,接着执行add操作 if (previousElement == beforeElement) { previousElement.next = beforeElement = new Entry<E>(e, lastReturned); } else { previousElement.next = new Entry<E>(e, beforeElement); } size ++; } } }
与非循环单身链表相比,有三处做了修改:1)链表初始化时,2)迭代器判断是否有下一个结点,3)删除结点。其他逻辑不变。
相关推荐
NULL 博文链接:https://bo-hai.iteye.com/blog/1997061
循环链表 实现约瑟夫环 java 自己写的 测试通过 有注释
类似约瑟夫环问题。有一群人组成一个圈。从头开始按照顺时针方向从1开始依次报数。报到到9的人就离开圈子。其左手边的人接着从1开始报数。依此进行,直到剩最后一个人为止。
这个循环链表是基于引用的,现实的算法比较简单,但是可以作为参考之用。
单向循环链表源码,包括List的接口定义的源码,实现了List接口的方法。
数据结构-链表 JAVA语言实现,包含单向链表、双向链表、循环链表的遍历、删除和插入 详细介绍:http://blog.csdn.net/z740852294/article/details/77369439
Amazon 面试题,如何用O(N)实现在链表中找出 是否出现循环(Loop),算法也可以用在其他语言(C,C++等)
里面有注释,很详细。 对于数据结构基础不是很好地朋友来说,有很大的帮助。
python单向循环链表
单向链表 双向链表 循环链表 静态链表 栈(Stack) 队列(Queue) 双端队列(Deque) 循环队列 哈希表(HashTable) 树形数据结构 二叉树(BinaryTree)、二叉搜索树(BinarySearchTree、BST) 平衡二叉搜索树...
通过本课程的学习,学员可以掌握以下技术点:线性结构与顺序表、单向链表、循环链表、栈的基本概念、链式堆栈、中缀表达式、队列、链式队列、串、MyString、Brute-Force算法、MySet类实现、矩阵类、递归算法、哈夫曼...
链表该项目提供了单向、双向和循环链表的示例
【链表List】单向链表 SingleLinkedList、双向链表 LinkedList 实现源码 【循环链表CircleList】单向循环链表、双向循环链表以及约瑟夫环问题 【队列Queue】队列 Queue、双端队列 DeQueue、循环队列 CircleQueue、...
通过本课程的学习,学员可以掌握以下技术点:线性结构与顺序表、单向链表、循环链表、栈的基本概念、链式堆栈、中缀表达式、队列、链式队列、串、MyString、Brute-Force算法、MySet类实现、矩阵类、递归算法、哈夫曼...
A、顺序表 B、单链表 C、双链表 D、单循环链表 C 2.设在栈中,由顶向下已存放元素c、b、a,在第4个元素d入栈之前,栈中元素可以出栈, 试问d入栈前后,不可能的出栈序列是____。 A、d c b a B、c b d a C、c a d b...
单链表代码虽然不太难但是逻辑思维较强。 首先对单链表的结构进行介绍,单链表是由很多个节点一个接一个串接起来的,每个节点包含两部分,数据部分和地址部分,我们这里讲的是无头的单链表,所以没有头节点,每个...
用Java实现数据结构和算法 动态数组实现 帕斯卡三角形的实现(锯齿状数组) 打印所有素数直到给定 n。 定理:假设所有数字都是素数,直到被证明为假。 单链表 标准单向链表:push/pop front、insert(i)、remove(i)、...
使用纯Java语言写出来的数据结构,包含数据结构有 单向链表,双向链表,单向循环链表,双向循环链表,二叉树,队列,栈等, 关于实现的种类有分多种类型,包含有链表或者数组,二叉树里面包含有常见的二叉查找树,...
1、Java实现单链表,支持增删改查。 2、单向链表反转 3、单向链表是否有环 4、合并两个有序链表 5、删除链表倒数第 n 个结点 6、求单向链表的中间结点 二、栈 1、Java实现顺序栈、链式栈 三、队列 1、顺序队列、链式...