六、单向循环链表&双向循环链表

单向循环链表

单向循环链表只需要在之前的单向链表基础之上进行修改，这里只需要修改添加和删除就可以了。

单向循环链表 – add(int index, E element)

添加需要考虑往第0位置上添加结点的特殊情况

单向循环链表 – remove(int index)

单向循环链表不仅需要考虑删除第0位置的结点，还需要考虑如果只有一个结点的特殊情况。

单向循环链表 – 只有1个节点

双向循环链表

双向循环链表 – add(int index, E element)

双向循环链表 – remove(int index)

双向循环链表在删除时还需要考虑如果只有一个结点的情况。

双向循环链表 – 只有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;
}

这里还要考虑链表中只有一个结点的特殊情况。