Java实现动态数组【数据结构与算法】

1、数组

类型固定、长度固定

连续的内存空间

顺序存储、随机读取

查询快、新增删除慢。 最好初始化的时候就指定数组大小。这样就可以避免一定的数组扩容出现的内存消耗。

import java.util.Arrays;
import java.util.Iterator;

/**
 * @author Administrator
 * @date 2022-09-11 16:56
 * 实现一个数组
 */
public class MyArray implements Iterable {

    private Object[] elementData;   // Object存放数据

    public MyArray(int capacity)    // 构造方法 初始化容量大小
    {
        // 指定长度 初始化数组 new 出一块空间
        elementData = new Object[capacity];
    }

    /**
     * 直接添加新元素
     * @param element
     * @return
     */
    public boolean add (E element)
    {
        int size = elementData.length;  // 获取当前数组大小
        int newCapacity = size+1;   // 扩容+1
        // 此处发生性能消耗，新增数据时，需要扩容，整体数据需要复制迁移，实际上arraylist是1.5扩容！
        elementData = Arrays.copyOf(elementData,newCapacity); // 把旧的空间复制一份到新的空间并+1
        elementData[size]=element;
        return true;
    }

    /**
     * set 方法 根据索引位置新增元素
     * @param index
     * @param element
     * @return
     */
    public E set (int index ,E element)
    {
        E oldValue = (E) elementData[index];    // 获取旧位置的元素值
        elementData[index] = element;           // 新值覆盖旧值
        return oldValue;          // 返回旧值

    }
    public E get (int index)
    {
        return (E) elementData[index]; // 返回对应索引位置的值
    }

    @Override
    public Iterator iterator(){
        return new MyIterator();
    }

    class MyIterator implements Iterator{
        int index = 0;
        @Override
        public boolean hasNext() {
            return index != elementData.length;
        }

        @Override
        public E next() {
            return (E) elementData[index++];    // 返回下一个元素值并+1
        }

        @Override
        public void remove() {
            //
        }
    }

    public static void main(String[] args) {
        MyArray myArray= new MyArray(10);   // 初始化一个容量为10的数组
        myArray.set(0,"q");
        myArray.set(2,"w");
        myArray.add("新增");
        Iterator iterator = myArray.iterator();     // 使用迭代器
        while (iterator.hasNext()){
            System.out.println(iterator.next());
        }
    }
}

1.1、关于arraylist初始容量和扩容

ArrayList 新增元素的方法有两种，一种是直接将元素加到数组的末尾，另外一种是添加元素到任意位置。

arraylist默认构造器，在不指定大小的时候默认容量为 10。

在超出容量之后，每次扩容为当前容量大小的1.5倍+1。

1.2、关于迭代器

集合的顶层接口 Collection继承 Iterable接口。在 Iterable接口中有一个 Iterator方法，它返回一个 Itertator对象。

public interface Iterable {
    /**
     * Returns an iterator over elements of type {@code T}.

     *
     * @return an Iterator.

     */
    Iterator iterator();
}

public interface Iterator {
    boolean hasNext();

    E next();

    default void remove() {
        throw new UnsupportedOperationException("remove");
    }
}

迭代器遍历中 调用集合revome()方法触发异常 java.util.ConcurrentModificationException 集合中并发修改的异常.

因为迭代器只负责遍历，它使用的仍然是集合本身的数据，在List集合实现的时候 数组的长度size会因为remove发生变化的，同时元素的索引值也会因为remove( )方法的调用而发生变化。那么在遍历的时候的remove就需要对这个点进行复刻，而且如果在迭代器里使用了List原生的remove方法，那么就会引起数值不同步的问题。

在 ArrayList集合的 iterator()方法中，是通过返回 Itr对象来获得迭代器的。 Itr是 ArrayList的一个内部类，它实现了 Iterator接口， 代码如下：

   private class Itr implements Iterator {
        int cursor;       // index of next element to return
        int lastRet = -1; // index of last element returned; -1 if no such
        int expectedModCount = modCount;

        Itr() {}

        public boolean hasNext() {
            return cursor != size;
        }

        @SuppressWarnings("unchecked")
        public E next() {
            checkForComodification();
            int i = cursor;
            if (i >= size)
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            cursor = i + 1;
            return (E) elementData[lastRet = i];
        }

        public void remove() {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();

            try {
                ArrayList.this.remove(lastRet);
                cursor = lastRet;
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

注意以下的三个属性：

cursor 索引下标，表示下一个可以访问的元素的索引，默认值为 0 lastRet 索引下标，表示上一个元素的索引，默认值为
-1

expectedModCount 对集合修改的次数，初始值为
0

我们知道： List的add和remove调用会增加modCount的值。也就是这两个操作会被计入对集合的修改次数。

在迭代器的源码中，有一个方法是用来判断 modCount 和 expectModCount 的值是否相等的，其中modCount的值来自List，expectModCount 是迭代器内定义的变量。那为什么要这么设计呢？

因为arraylist是线程不安全的。

结合iterrator的next方法，我们可以看到， 如果没有这个校验， 某个线程删除了list的一个元素，此时next方法不知道size变更了，依然去取数组里的数据，会导致数据为null或ArrayIndexOutOfBoundsException异常等问题。

ConcurrentModificationException发生在Iterator( )和next( )方法实现中，每次调用都会检查容器的结构是否发生变化，目的是为了避免共享资源而引发的潜在问题。
观察HashMap和ArrayList底层Iterator#next(), 可以看到fast-fail只会增加或者删除（非Iterator#remove()）抛出异常；改变容器中元素的内容不存在这个问题（主要是modCount没发生变化）。
在单线程中使用迭代器，对非线程安全的容器，但是只能用Iterator和remove；否则会抛出异常。
在多线程中使用迭代器，可以使用线程安全的容器来避免异常。
使用普通的for循环遍历，效率虽然比较低下，但是不存在ConcurrentModificationException异常问题，用的也比较少。

所以说如果在使用迭代器的时候，用到了List自带的remove方法，那么modCount改变了，但是迭代器内定义的变量expectedCount却没有改变，这样就会被抛出异常。

综上：我们在使用迭代器的时候，不要混用List本身的remove方法。

Iterator接口有四个方法，hasNext、next、remove和forEachRemaining
其中forEachRemaining是java1.8新增的
这个方法是针对集合中剩余元素的操作
剩余的含义是没有被iterator.next()遍历过的元素

1.3、为什么迭代器在调用remove之前要先调用next

当使用Iterator迭代访问Collection集合元素时，Collection集合里的元素不能被改变， 只有通过Iterator的remove()方法删除上一次next()方法返回的集合元素才可以；否则会引发java.util.ConcurrentModificationException异常。

查看next方法的源码可以看到 return (E) elementData[lastRet = i];这样一行代码，这行代码表示next方法在让数组下标cursor向后移动一位的同时，还会把lastRet的值变成当前返回的元素下标，这样remove方法就可以根据这个下标完成对元素的删除。

Original: https://www.cnblogs.com/rainbow-1/p/16690478.html
Author: 靠谱杨
Title: Java实现动态数组【数据结构与算法】