链表——从0实现一个单向循环链表 & 并且实现约瑟夫问题

目录 一、什么是约瑟夫问题(Josephus Problem)? 二、从0手写一个单向循环链表 三、实现约瑟夫问题 一、什么是约瑟夫问题(Josephus Problem)?

• 百度百科-约瑟夫问题
• 以下图为例, 箭头从1开始循环数数, 具体数到几自己规定, 下图为例从1数到3, 然后3淘汰, 将箭头指向被淘汰数的下一个, 然后继续数, 淘汰6, 以此类推…

上图淘汰顺序为: 3 6 1 5 2 8 4 7

二、从0手写一个单向循环链表

• 该实现直接使用单向循环链表的内容, 建议从链表开始看; 下面代码为单向循环链表的具体实现

1、自定义List接口实现

package com.zy;

/**
 * Description: 定义动态数组和链表的公共接口
 *
 * @author guizy
 * @date 2020/3/19 21:50
 */
public interface List {

    /**
     * 找不到元素返回-1
     */
    // 默认就是 public static final修饰
    int ELEMENT_NOT_FOUNT = -1;

    /**
     * 清除所有元素
     */
    void clear();

    /**
     * 元素的数量
     *
     * @return
     */
    int size();

    /**
     * 是否为空
     *
     * @return
     */
    boolean inEmpty();

    /**
     * 是否包含某个元素
     *
     * @param element
     * @return
     */
    boolean contains(E element);

    /**
     * 添加元素到尾部
     *
     * @param element
     */
    void add(E element);

    /**
     * 获取index位置的元素
     *
     * @param index
     * @return
     */
    E get(int index);

    /**
     * 设置index位置的元素
     *
     * @param index
     * @param element
     * @return 原来的元素
     */
    E set(int index, E element);

    /**
     * 在index位置插入一个元素
     *
     * @param index
     * @param element
     */
    void add(int index, E element);


    /**
     * 删除index位置的元素
     *
     * @param index
     * @return 被删除的元素
     */
    E remove(int index);

    /**
     * 删除传入的元素
     *
     * @param element
     */
    void remove(E element);

    /**
     * 查看元素的索引
     *
     * @param element
     * @return
     */
    int indexOf(E element);
}

2、自定义AbstractList实现上面的List

package com.zy;

/**
 * Description: 该类不对外公开,只是为了抽取一些公共的代码
 *
 * @author guizy
 * @date 2020/3/19 22:13
 */
/*
        抽象类是不能被实例化的，所以没有要求实现所有的方法。但是没写出的方法还是隐式的存在的。
    当你在定义一个非abstract类继承那个类的话，就一定要全部实现了。
 */
public abstract class AbstractList implements List {

    /**
     * 元素的数量
     */
    protected int size;

    /**
     * 元素的数量
     *
     * @return
     */
    public int size() {
        return size;
    }

    /**
     * 是否为空
     *
     * @return
     */
    public boolean inEmpty() {
        return size == 0;
    }

    /**
     * 是否包含某个元素
     *
     * @param element
     * @return
     */
    public boolean contains(E element) {
        // 如果element元素可以找到
        return indexOf(element) != ELEMENT_NOT_FOUNT;
    }

    /**
     * 添加元素到尾部
     *
     * @param element
     */
    public void add(E element) {
        // elements[size++] = element;
        // 传入数组数量(相当于在最后插入元素)
        add(size, element);
    }

    /**
     * 封装数组越界异常
     *
     * @param index
     */
    protected void indexOutOfBounds(int index) {
        throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
    }

    /**
     * 检查get,remove传入的index是否有效
     *
     * @param index
     */
    protected void rangeCheck(int index) {
        if (index = size) {
            indexOutOfBounds(index);
        }
    }

    /**
     * 根据index插入元素时,判断index是否有效
     *
     * @param index
     */
    protected void rangeCheckForAdd(int index) {
        if (index  size) {
            indexOutOfBounds(index);
        }
    }
}

3、SingleCircleLinkedList继承AbstractList

package com.zy.single;

import com.zy.AbstractList;

/**
 * Description: 单向循环链表实现
 *
 * @author guizy
 * @date 2020/3/19 21:22
 */
public class SingleCircleLinkedList extends AbstractList {

    /*
        单向循环链表, 相对于单链表; 我们只需要更高 add、remove方法即可!
     */

    /**
     * 指向第一个结点
     */
    protected Node first;


    /**
     * 结点类;为链表的内部类
     *
     * @param 
     */
    protected static class Node {

        //存储元素的信息
        E element;

        //指向下一个结点
        Node next;

        // 结点构造器
        public Node(E element, Node next) {
            this.element = element;
            this.next = next;
        }

        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            sb.append(element).append("_").append(next.element);
            return sb.toString();
        }
    }

    @Override
    public void clear() {
        size = 0;
        first = null;
    }

    @Override
    public E get(int index) {
        // 通过node方法找到结点,通过结点的element来获取元素
        return node(index).element;
    }

    @Override
    public E set(int index, E element) {
        // 获取index处的结点
        Node node = node(index);
        E oldElement = node.element;
        node.element = element;
        // 返回的是没覆盖之前的结点元素信息
        return oldElement;
    }

    @Override
    public void add(int index, E element) {
        rangeCheckForAdd(index);

        // 当index传0的时候,就会报异常,此时要特殊处理
        if (index == 0) {
            Node newFirst = new Node(element, first);

            // 拿到最后一个结点; 判断只有一个结点的情况
            Node last = (size == 0) ? newFirst : node(size - 1);
            // 最后一个结点的next指向头结点
            last.next = newFirst;
            first = newFirst;

        } else {
            // 在index处插入元素,首先要找到它前面的结点
            Node preNode = node(index - 1);
            // 让前面的结点的next指向新创建的结点,新创建的结点指向index处的结点即可
            // 此时index处的结点,就是它前面的结点的next,就是指向index处的结点
            Node newNode = new Node(element, preNode.next);
            // 前面的结点的next再指向新的结点
            preNode.next = newNode;
        }
        size++;
    }

    @Override
    /**
     * 返回的是被删除元素的element
     */
    public E remove(int index) {
        // 假如被删除的结点为第一个结点
        Node node = first;
        if (index == 0) {
            if (size == 1) { // 链表中只有一个元素的时候
                first = null;
            } else {
                Node last = node(size - 1);
                // first已经指向了第一个结点,如果要删除第一个结点,此时要将first指向第一个结点的next结点
                first = first.next;
                last.next = first; // 最后一个结点指向新的第一个结点
            }
        } else {
            Node preNode = node(index - 1);
            node = preNode.next; // 这个node就是当前被删除的结点
            //preNode.next = preNode.next.next;
            preNode.next = node.next;
        }
        size--;
        return node.element;
    }

    @Override
    public void remove(E element) {
        remove(indexOf(element));
    }

    @Override
    /**
     * element是保存在node里的,传入element,返回该结点的索引
     */
    public int indexOf(E element) {
        Node node = first;
        if (element == null) {
            // 因为element都在node中,所以通过next来遍历node
            for (int i = 0; i