week06_day06_自己实现ArrayList_2

关于Iterator中的remove方法：

为什么删除倒数第二个元素不会报并发修改异常？

看一下成果，自己设计的ArrayList：
MyIterator接口：

package com.cskaoyan.list;

/**
 * @author shihao
 * @create 2020-05-16 8:09
 */

import java.util.Iterator;

//MyIterator模仿的是listIterator
//MyIterator
public interface MyIterator<E> extends Iterator<E> {
    boolean hasNext();

    boolean hasPrevious();

    E next();

    E previous();

    int nextIndex();

    int previousIndex();

    void add(E e);

    void remove();

    void set(E e);
}

MyList接口：

package com.cskaoyan.list;

/**
 * @author shihao
 * @create 2020-05-15 17:28
 */

//想让MyArrayList和LinkedList也可以实现自己的foreach循环，
// 就得让MyList实现接口Iterable，表示有迭代的能力
public interface MyList<E> extends Iterable<E> {

    boolean add(E e);

    void add(int index, E e);

    void clear();

    boolean contains(Object obj);

    E get(int index);

    int indexOf(Object obj);

    boolean isEmpty();

    //MyIterator模仿的是listIterator
    //应当实现一个迭代器，对MyList进行遍历
    MyIterator iterator();

    MyIterator iterator(int index);

    int lastIndexOf(Object obj);

    E remove(int index);

    boolean remove(Object obj);

    E set(int index, E e);

    int size();
}

MyArrayList：

package com.cskaoyan.list;

import com.cskaoyan.exception.ArrayOverflowException;

import java.util.*;

/**
 * @author shihao
 * @create 2020-05-15 17:28
 */
//想让MyArrayList也可以实现自己的foreach循环，就得让MyList实现接口Iterable
public class MyArrayList<E> implements MyList<E> {

    //elements默认的大小
    private static final int DEFAULT_CAPACITY = 10;
    //elements的最大容量
    private static final int MAX_CAPACITY = Integer.MAX_VALUE - 8;

    //属性
    //不能直接创建泛型数组，泛型擦除之后，其实数组里面的元素是Object类型
    private Object[] elements;
    private int size;

    //为了防止并发修改异常
    private int modCount;    //统计集合结构被修改的次数


    //构造方法
    public MyArrayList() {
        this.elements = new Object[DEFAULT_CAPACITY];
    }

    public MyArrayList(int initialCapacity) {
        //及早失败原则
        if (initialCapacity <= 0 || initialCapacity > MAX_CAPACITY) {
            throw new IllegalArgumentException("initialCapacity = " + initialCapacity);
        }
        elements = new Object[initialCapacity];
    }


    //方法

    /**
     * 在线性表最后添加元素
     *
     * @param e 待添加的元素
     * @return 如果添加成功返回true
     * 如果添加失败就抛出异常
     */
    @Override
    public boolean add(E e) {
        add(size, e);
        return true;
    }

    /**
     * 在线性表中指定位置添加元素
     *
     * @param index 索引
     * @param e     待添加的元素
     */
    @Override
    public void add(int index, E e) {
        checkIndexForAdd(index);

        //判断是否需要扩容
        if (size == elements.length) {
            int minCapacity = size + 1;
            //通过calculateCapacity的计算，一定可以得到一个新的大于minCapacity的容量
            int newCapacity = calculateCapacity(minCapacity);
            //将容量扩充到newCapacity
            grow(newCapacity);
        }

        //添加元素
        for (int i = size; i > index; i--) {
            elements[i] = elements[i - 1];
        }
        elements[index] = e;

        size++;
        //集合结构改变了
        modCount++;
    }

    private void grow(int newCapacity) {
        //数组大小是不可变的，应当新建一个更大的数组，将原数组的元素传递给它
        Object[] newArr = new Object[newCapacity];
        for (int i = 0; i < size; i++) {
            newArr[i] = elements[i];
        }

        //elements指向新数组
        elements = newArr;
    }

    private int calculateCapacity(int minCapacity) {
        //minCapacity<0表示的情况可能是，两个很大的list进行合并，发生了栈溢出
        if (minCapacity > MAX_CAPACITY || minCapacity < 0) {
            throw new ArrayOverflowException("minCapacity = " + minCapacity);
        }

        //执行到这步说明一定能够容纳minCapacity个元素
        int newCapacity = elements.length + elements.length >> 1;
        if (newCapacity > MAX_CAPACITY || newCapacity < 0) {
            newCapacity = MAX_CAPACITY;
        }

        //返回minCapacity和newCapacity的最大值
        //因为使用addAll方法添加一个集合时，minCapacity可能大于newCapacity
        //最终的返回值应当>=minCapacity
        return Math.max(newCapacity, minCapacity);
    }

    private void checkIndexForAdd(int index) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("index=" + index + ", size=" + size);
        }
    }

    /**
     * 清空所有元素
     */
    @Override
    public void clear() {
        for (int i = 0; i < size; i++) {
            elements[i] = null;
        }
        //直接size = 0; 会存在什么问题？ 内存泄漏，elements中的元素（引用类型）可能已经
        //变成垃圾了，但是在elements中还存有这些引用，所以GC是不会把他们判断成垃圾的
        size = 0;
        modCount++;
    }

    /**
     * 判断集合中是否存在与集合中指定对象相等的元素
     *
     * @param obj 指定对象
     * @return 如果集合中有与指定对象相等的元素，返回true，否则返回false。
     */
    @Override
    public boolean contains(Object obj) {
        return indexOf(obj) != -1;
    }

    /**
     * 获取指定索引位置的元素
     *
     * @param index 索引
     * @return 指定索引位置的元素
     */
    @Override
    @SuppressWarnings("unchecked")
    public E get(int index) {
        checkIndex(index);
        return (E) elements[index];
    }

    private void checkIndex(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("index = " + index + ", size = " + size);
        }
    }

    /**
     * 获取集合中第一个与指定对象相等元素的索引
     *
     * @param obj 指定对象
     * @return 第一个与指定对象相等元素的索引，如果不存在这样的元素，返回-1
     */
    @Override
    public int indexOf(Object obj) {
        //如果我obj == null，在null上调用equals方法会抛出空指针异常，
        //判断null和elements[i]是否相等得用null == elements[i]
        //所以得判断if (obj == null)
        if (obj == null) {
            for (int i = 0; i < size; i++) {
                if (obj == elements[i]) {
                    return i;
                }
            }
        } else {
            for (int i = 0; i < size; i++) {
                //不用重写equals方法，哪种类对象调用equals方法，就在此类中重写equals方法
                //比如说，elements里面存储的是String类型的对象，就在String中重写equals方法
                //不能写成elements[i].equals(obj)，elements[i]可能为null，这样调用会抛出空指针异常
                if (obj.equals(elements[i])) {
                    return i;
                }
            }
        }
        return -1;
    }

    /**
     * 判断集合是否为空
     *
     * @return 如果集合为空返回true，否则返回false
     */
    @Override
    public boolean isEmpty() {
        return size == 0;
    }


    /**
     * 获取集合中最后一个与指定对象相等的元素的索引
     *
     * @param obj 指定对象
     * @return 最后一个与指定对象相等的元素的索引，如果不存在，返回-1
     */
    @Override
    public int lastIndexOf(Object obj) {
        if (obj == null) {
            for (int i = size - 1; i >= 0; i--) {
                if (elements[i] == obj) {
                    return i;
                }
            }
        } else {
            for (int i = size - 1; i >= 0; i--) {
                if (obj.equals(elements[i])) {
                    return i;
                }
            }
        }

        return -1;
    }

    /**
     * 删除指定索引位置的元素
     *
     * @param index 索引
     * @return 被删除的元素
     */
    @Override
    @SuppressWarnings("unchecked")
    public E remove(int index) {
        checkIndex(index);
        E removeValue = (E) elements[index];
        for (int i = index; i < size - 1; i++) {
            elements[i] = elements[i + 1];
        }
        //最后一个元素没有真正的移除掉，可能会导致内存泄漏，应当将其置为null
        elements[size - 1] = null;
        size--;
        modCount++;
        return removeValue;
    }

    /**
     * 删除第一个与指定对象相等的元素
     *
     * @param obj 指定对象
     * @return 如果删除成功返回true，失败返回false
     */
    @Override
    public boolean remove(Object obj) {
        int index = indexOf(obj);
        if (index == -1) {
            return false;
        }
        remove(index);
        return true;
    }

    /**
     * 替换指定索引位置的元素
     *
     * @param index 索引
     * @param e     新值
     * @return 该索引位置原来的值
     */
    @Override
    @SuppressWarnings("unchecked")
    public E set(int index, E e) {
        checkIndex(index);
        E oldValue = (E) elements[index];
        elements[index] = e;
        //只是替换元素的值，并没有修改集合的结构，不需要modCount++
        return oldValue;
    }

    /**
     * 获取线性表中的元素个数
     *
     * @return 元素个数
     */
    @Override
    public int size() {
        return size;
    }

    /**
     * 获取迭代器，默认下一个元素的索引值为0
     *
     * @return 迭代器
     */
    //迭代器是以成员位置内部类的形式存在的
    @Override
    public MyIterator<E> iterator() {
        //只需创建一个迭代器，将他返回就可以了
        return new Itr();
    }

    /**
     * 获取迭代器，指定下一个元素的索引值为index
     *
     * @param index 下一个元素的索引值
     * @return 迭代器
     */
    @Override
    public MyIterator<E> iterator(int index) {
        checkIndexForAdd(index);
        return new Itr(index);
    }

    //迭代器的重点就是创建成员位置内部类Itr
    private class Itr implements MyIterator<E> {
        //属性
        int cursor;
        //可以在最后通过判断excModCount == modCount来判断是否发生并发修改异常
        //为什么可以访问modCount？ 因为内部类可以访问外部类的成员
        int excModCount = modCount;  //期望被修改的次数
        //仅仅知道光标位置，不知道是正向遍历还是逆向遍历，无法返回最近遍历到的元素的索引
        int lastRet = -1;  //最近返回元素的索引
        //-1表示最近没有返回元素，或者是最近返回的元素是失效的
        //构造方法


        public Itr() {
        }

        public Itr(int index) {
            this.cursor = index;
        }

        //方法

        /**
         * 判断光标后面是否还有元素
         *
         * @return 如果光标后面还有元素返回true，否则返回false
         */
        @Override
        public boolean hasNext() {
            return cursor != size;
        }

        /**
         * 判断光标前面是否还有元素
         *
         * @return 如果光标前面还有元素返回true，否则返回false
         */
        @Override
        public boolean hasPrevious() {
            return cursor != 0;
        }

        /**
         * 将光标往后移动一个位置，并把被光标越过的元素返回
         *
         * @return 被光标越过的元素
         */
        @Override
        @SuppressWarnings("unchecked")
        public E next() {
            //首先要检查迭代器是否还有效，是否发生了并发修改异常
            checkConModException();
            //后面没有元素了你还想往后移就抛出异常
            if (!hasNext()) {
                throw new NoSuchElementException();
            }

            //移动光标
/*            E retValue = (E) elements[cursor];
            lastRet = cursor;
            cursor++;
            return retValue;*/

            lastRet = cursor;
            return (E) elements[cursor++];
        }

        private void checkConModException() {
            if (excModCount != modCount) {
                throw new ConcurrentModificationException();
            }
        }

        /**
         * 将光标往前移动一个位置，并把被光标越过的元素返回
         *
         * @return 被光标越过的元素
         */
        @Override
        @SuppressWarnings("unchecked")
        public E previous() {
            //判断迭代器是否有效
            checkConModException();
            if (!hasPrevious()) {
                throw new NoSuchElementException();
            }
            //移动光标
/*            E retValue = (E) elements[cursor - 1];
            lastRet = cursor - 1;
            cursor--;
            return retValue;*/

            lastRet = --cursor;
            return (E) elements[cursor];
        }

        /**
         * 获取光标后面元素的索引
         *
         * @return 光标后面元素的索引
         */
        @Override
        public int nextIndex() {
            return cursor;
        }

        /**
         * 获取光标前面元素的索引
         *
         * @return 光标前面元素的索引
         */
        @Override
        public int previousIndex() {
            return cursor - 1;
        }


        /**
         * 在光标后面添加元素
         *
         * @param e 待添加的元素
         */
        @Override
        public void add(E e) {
            //判断迭代器是否有效
            checkConModException();
            MyArrayList.this.add(cursor, e);
            excModCount = modCount;
            //最近返回的元素是失效的
            lastRet = -1;
            cursor++;
        }

        @Override
        public void remove() {
            checkConModException();
            //没有最近返回的元素或者最近返回的元素失效就抛出非法状态异常
            if (lastRet == -1) {
                throw new IllegalStateException();
            }

            //删除最近返回的元素
            MyArrayList.this.remove(lastRet);
            //更改迭代器的属性
            excModCount = modCount;
            cursor = lastRet;
            lastRet = -1;
        }

        /**
         * 用新值e替换最近返回的元素
         *
         * @param e 新值
         */
        @Override
        public void set(E e) {
            checkConModException();
            if (lastRet == -1) {
                throw new IllegalStateException();
            }

            elements[lastRet] = e;
            //索引为lastRet的elements的值已经修改了，lastRet指向的已经不是原来的值了，
            //而是指向修改后的值。也就是说最近返回的元素应当失效，将lastRet置为-1
            lastRet=-1;
            //但是cursor是不需要改变的
            //而且modCount也不需要改变，因为没有修改集合的结构。
        }
    }

    @Override
    public String toString() {
        //[a, b, c]
        StringBuilder sb = new StringBuilder("[");
        for (int i = 0; i < size; i++) {
            //if (i != 0) sb.append(", ");
            //if (i != size - 1) sb.append(", ")
            //以上两者都不用，进行判断和-1操作会使性能降低
            sb.append(elements[i]).append(", ");
        }

        //size = 0 说明就没有进行上述循环，不需要删除sb末尾的", "
        if (size != 0) {
            sb.delete(sb.length() - 2, sb.length());
        }

        return sb.append("]").toString();
    }

    //测试代码
    public static void main(String[] args) {

        //测试toString方法、add方法、size方法
        MyList<String> list = new MyArrayList<>();
//        System.out.println(list);
        list.add("hello");
        list.add("world");
        list.add("java");
//        System.out.println(list);
//        System.out.println(list.size());

        //测试自动扩容
//        for (int i = 0; i < 30; i++) {
//            list.add(" i");
//        }
//        System.out.println(list.size());

        //测试void add(int index, E e)
//        list.add(0,null);
//        list.add(2,null);
//        list.add(-1,"hao");
//        System.out.println(list);

        //测试boolean isEmpty()、void clear()
//        System.out.println(list.size());
//        System.out.println(list.isEmpty());
//        list.clear();
//        System.out.println(list.isEmpty());
//        System.out.println(list);
//        System.out.println(list.size());

        // 测试boolean contains(Object obj)
//        System.out.println(list.contains("hello"));
//        System.out.println(list.contains("helloKitty"));
//        System.out.println(list.contains(null));
//        list.add(null);
//        System.out.println(list.contains(null));

        // 测试int indexOf(Object obj)
//        list.add("hello");
//        System.out.println(list.indexOf("hello")); // 0
//        System.out.println(list.indexOf(null));  // -1
//        list.add(null);
//        list.add(1, null);
//        System.out.println(list.indexOf(null)); // 1

        // 测试int lastIndexOf(Object obj)
        /*list.add("hello");
        System.out.println(list.lastIndexOf("hello")); // 3
        System.out.println(list.lastIndexOf(null)); // -1
        list.add(null);
        list.add(1, null);
        System.out.println(list.lastIndexOf(null)); // 5*/

        // 测试E get(int index)
//        String s = list.get(1);
//        System.out.println(s);
        // System.out.println(list.get(-1));
        // System.out.println(list.get(list.size()));


        //测试E remove(int index)
        //System.out.println(list.remove(1));
        //System.out.println(list.remove(-1));
        //System.out.println(list.remove(list.size()));
        //System.out.println(list);

        // 测试boolean remove(Object obj)
        // list.add("hello");
        // System.out.println(list.remove("hello"));
        // System.out.println(list.remove(null));
        /*list.add(null);
        list.add(0, null);
        System.out.println(list);
        System.out.println(list.remove(null));
        System.out.println(list);*/


        // 测试E set(int index, E e)
        // System.out.println(list.set(1, "WORLD"));
        // System.out.println(list.set(-1, "WORLD"));
        // System.out.println(list.set(list.size(), "WORLD"));
        // System.out.println(list);

        //*****************************************************************//
        //------------------------Iterator---------------------------------//
        //*****************************************************************//


        // 测试boolean hasNext(), boolean hasPrevious()
        // MyIterator<String> it = list.iterator();
        // MyIterator<String> it = list.iterator(list.size());
        // MyIterator<String> it = list.iterator(1);
        // System.out.println(it.hasPrevious());
        // System.out.println(it.hasNext());

        // 测试E next()
        /*MyIterator<String> it = list.iterator();
        System.out.println(it.next());
        System.out.println(it.next());
        System.out.println(it.next());*/
        // System.out.println(it.next()); NoSuchElementException

        // 测试E previous()
        /*MyIterator<String> it = list.iterator(list.size());
        System.out.println(it.previous());
        System.out.println(it.previous());
        System.out.println(it.previous());*/
        // System.out.println(it.previous()); NoSuchElementException

        // 测试int nextIndex(), int previousIndex()
        /*MyIterator<String> it = list.iterator();
        System.out.println(it.previousIndex()); //-1
        System.out.println(it.nextIndex()); // 0
        it.next();
        System.out.println(it.previousIndex()); // 0
        System.out.println(it.nextIndex());*/ // 1

        /*MyIterator<String> it = list.iterator(list.size());
        System.out.println(it.previousIndex()); // 2
        System.out.println(it.nextIndex()); // 3
        it.previous();
        System.out.println(it.previousIndex()); //1
        System.out.println(it.nextIndex()); // 2*/

        //测试 void add(E e)
        /*MyIterator<String> it = list.iterator();
        it.next();
        it.add("wuhan");
        it.add("beijing");
        System.out.println(list);*/

        //测试 void add(E e)的并发修改异常
        /*for(MyIterator<String> it = list.iterator(); it.hasNext(); ) {
            String s = it.next();
            if ("hello".equals(s)) {
                int index = it.nextIndex();
                list.add(index, "wuhan");
            }
        }
        System.out.println(list);*/

        // 测试void remove()
        /*MyIterator<String> it = list.iterator();
        // it.remove(); // IllegalStateException
        it.next();
        it.remove();
        System.out.println(list);
        // it.remove(); IllegalStateException*/

        /*MyIterator<String> it = list.iterator(list.size());
        // it.remove();
        it.previous();
        it.remove();
        System.out.println(list);
        // it.remove();*/

        // 测试ConcurrentModificationException
        /*for(MyIterator<String> it = list.iterator(); it.hasNext(); ) {
            String s = it.next();
            if ("hello".equals(s)) {
                int index = it.previousIndex();
                list.remove(index);
            }
        }
        System.out.println(list);*/


        // void set(E e)
/*        MyIterator<String> it = list.iterator();
        // it.set("HELLO");
        it.next();
        it.set("HELLO");
        System.out.println(list);
        // it.set("hello");
        //调用set后cursor并没有前移或后移
        System.out.println(it.nextIndex());*/

        //set方法并没有修改集合的结构，所以不会报并发修改异常
/*        for(MyIterator<String> it = list.iterator(); it.hasNext(); ) {
            String s = it.next();
            if ("hello".equals(s)) {
                int index = it.previousIndex();
                list.set(index, "HELLO");
            }
        }
        System.out.println(list);*/

        //会发现我们删除"world"和"java"时不会报并发修改异常的错
        //即：在MyIterator中调用MyArrayList的remove方法删除倒数第二个元素和倒数第一个元素时，
        // 不会报并发修改异常
        /*for(MyIterator<String> it = list.iterator(); it.hasNext(); ) {
            String s = it.next();
            if ("java".equals(s)) {
                int index = it.previousIndex();
                list.remove(index);
            }
        }
        System.out.println(list);*/

//        ArrayList<String> list = new ArrayList<>();
//        list.add("hello");
//        list.add("world");
//        list.add("java");
//
          //不光我们自己写的Iterator会出现这种问题，jdk中的Iterator也会出现类似问题
          //即：在迭代器中调用ArrayList的remove方法删除倒数第二个元素时，不会报并发修改异常
//        for(ListIterator<String> it = list.listIterator(); it.hasNext(); ) {
//            String s = it.next();
//            if ("java".equals(s)) {
//                int index = it.previousIndex();
//                list.remove(index);
//            }
//        }
//        System.out.println(list);

    }

}