跟Java集合学数据结构之 ArrayList

链表是很常见的一种数据结构。通常有两种实现方式：一种是使用数组，一种使用指针。数组涉及数据移动和扩容问题，但随机查找方便；指针插入删除方便，但随机查找不方便

下面学习java的ArrayList，链表的数组实现，仿照精简版
常见方法：add、get、remove、size、isEmpty等，简单起见就不抽取父类了

ArrayList每次扩容50% (newCapacity + (newCapacity >> 1))，右移1位相当于除2

public class MyArrayList<T> implements Iterable<T> {

    /** 默认容量 */
    private static final int DEFAULT_CAPACITY = 20;
    
    /** size */
    private int size;
    
    /** data */
    private transient Object[] data;
    
    /** empty array */
    private static final Object[] EMPTY_ELEMENTDATA = {};
    
    public MyArrayList() {
        data = new Object[DEFAULT_CAPACITY];
    }
    
    public MyArrayList(int capacity) {
        if (capacity >= 0) {
            data = new Object[capacity];
        } else {
            data = new Object[DEFAULT_CAPACITY];
        }
    }
    
    public void add(T element) {
        // 确认容量是否足够，不够则扩容
        ensureCapacity(size + 1);
        data[size++] = element;
    }
    
    public void add(int index, T element) {
        // 检查范围
        checkRange(index);
        
        // 确认容量是否足够，不够则扩容       
        ensureCapacity(size + 1);
        
        System.arraycopy(data, index, data, index + 1, size - index);
        data[index] = element;
        size++;
    }
    
    public T get(int index) {
        if (index >= size) {
            throw new IndexOutOfBoundsException();
        }
        return elementData(index);
    }
    
    public T remove(int index) {
        // 检查范围
        checkRange(index);
        // 获取元素
        T t = elementData(index);
        
        // 移动元素
        int numMoved = size - index - 1;
        if (numMoved > 0) {
            System.arraycopy(data, index + 1, data, index, numMoved);
        }
        
        // 清空元素内容
        data[--size] = null;
        
        return t;
    }
    
    void checkRange(int index) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException();
        }
    }
    
    public int size() {
        return this.size;
    }
    
    public boolean isEmpty() {
        return size() == 0;
    }
    
    @SuppressWarnings("unchecked")
    T elementData(int index) {
        return (T) data[index];
    }
    
    private void ensureCapacity(int newCapacity) {
        if (newCapacity < size) {
            return;
        }
        
        // 扩容，每次扩容50% 
        int newSize = newCapacity + (newCapacity >> 1);
        data = Arrays.copyOf(data, newSize);
    }
    
    /**
     * 释放多余的空间，刚发现有这么个功能....
     */
    public void trimToSize() {
        if (size >= data.length) {
            return;
        }
        data = (size == 0) ? EMPTY_ELEMENTDATA : Arrays.copyOf(data, size);
    }
    
    @Override
    public Iterator<T> iterator() {
        return new ArrayListIterator();
    }
    
    /**
     * 实现迭代接口，可以使用迭代器遍历List
     */
    private class ArrayListIterator implements Iterator<T> {

        private int currentIndex;
        
        @Override
        public boolean hasNext() {
            return currentIndex < size();
        }

        @Override
        public T next() {
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            
            return elementData(currentIndex++);
        }
        
//      // 暂不实现遍历时删除的操作
//      @Override
//      public void remove() {
//          MyArrayList.this.remove(--currentIndex);
//      }
    }
}

ArrayList里有两个好用的方法：

• System.arraycopy(data, index + 1, data, index, size - index - 1);
  数组中元素的移动或者两个数组之间元素的复制
• Arrays.copyOf(data, newSize); // 这个方法也是刚发现的。
  可以用来复制一个数组，从第一个元素开始，如果newSize>data的长度，则使用data的长度