单向循环链表
单向循环链表只需要在之前的单向链表基础之上进行修改，这里只需要修改添加和删除就可以了。
单向循环链表 – add(int index, E element)
添加需要考虑往第0位置上添加结点的特殊情况
单向循环链表 – remove(int index)
单向循环链表不仅需要考虑删除第0位置的结点，还需要考虑如果只有一个结点的特殊情况。
单向循环链表 – 只有1个节点
单向循环链表 – 只有1个节点
双向循环链表
双向循环链表 – add(int index, E element)
双向循环链表 – remove(int index)
双向循环链表在删除时还需要考虑如果只有一个结点的情况。
双向循环链表 – 只有1个节点
双向循环链表 – 只有1个节点
约瑟夫问题（Josephus Problem）
约瑟夫问题
约瑟夫问题（Josephus Problem）：例如有八个人，这八个人排成一个圈，每个人都有一个序号，从第1个开始数，数到第三个，那么第三个就拿出去枪毙，循环下去，最后谁能活下来。
这个问题可以使用之前介绍的循环链表就可以很好的解决，但是我们还可以把之前介绍的循环链表发挥最大威力
如何发挥循环链表的最大威力？
可以考虑增设1个成员变量、3个方法
- current:用于只想某一个结点
- void reset():让 current 指向结点first
- E next():让 current 往后走一步，也就是 current = current.next
- E remove():删除 current 指向的结点，删除成功后让 current 指向下一个结点。
我们这里直接采用之前的双向循环链表来实现，单向循环链表暂时不实现(双向的实现了，那么单向的也就会实现了)。
在双向循环链表中新增current成员属性
实现reset()
public void reset() {
current = first;
}
实现next()
public E next() {
if(current == null) return null;
current = current.next;
return current.element;
}
实现remove()
我们可以使用indexOf(E element)和remove(int index)方法来实现本本方法
public E remove() {
if(current == null) return null;
return remove(indexOf(current.element));
}
但是这个做法觉得太笨了，那么我们是否可以新增一个remove(Node<E> node)方法该多好。
private E remove(Node<E> node) {
if(size == 1) {
first = null;
last = null;
}else {
Node<E> prev = node.prev;
Node<E> next = node.next;
prev.next = next;
next.prev = prev;
if(node == first) {//index == 0 删除0位置的结点
first = next;
}
if(node == last) {//index == size - 1 删除最后一个结点
last = prev;
}
}
size--;
return node.element;
}
实现了remove(Node<E> node)方法，那么之前的remove(int index)方法就可以简单实现
public E remove(int index) {
rangeCheck(index);//如果链表中没有数据
return remove(findNode(index));
}
最后实现remove()方法：
public E remove() {
if(current == null) return null;
Node<E> next = current.next;
E element = remove(current);
if(size == 0) {
current = null;
}else {
current = next;// current 指向下一个结点
}
return element;
}
这里还要考虑链表中只有一个结点的特殊情况。
现在实现上面的约瑟夫问题（Josephus Problem）
输出结果：
静态链表(了解)
- 前面所学的链表，是依赖于指针(引用)实现的，有的编程语言是没有指针的，比如早期的BASIC、FORTRAN语言
- 没有指针的情况下，如何实现链表？
- 可以通过数组来模拟链表，成为静态链表
- 数组的每个元素存放2个数据：值、下个元素的索引
- 数组0位置存放的是头结点信息
思考：如果数组的每个元素只能存放1个数据呢？
那就使用2个数组，1个数组存放索引关系，1个数组存放值
