模仿实现程序表 ArrayList

一、定义接口

无论是程序表还是链表，它们都是线性表，都须要进行增删改查操作。
所以首先，定义一个线性表接口 List，蕴含线性表的操作

/**
 * 线性表接口
 * 和存储构造无关（程序表，链表）*/
public interface List
{
    // 返回线性表的大小，即元素的个数
    public int size();

    // 返回线性表中序号为 i 的数据元素
    public Object get(int i);

    // 如果线性表为空，返回 true，否则返回 false
    public boolean isEmpty();

    // 判断线性表中是否蕴含数据元素 e
    public boolean contains(Object e);

    // 返回数据元素 e 在线性表中的序号
    public int indexOf(Object e);

    // 将数据元素 e 插入到线性表中 i 号地位
    public void add(int i, Object e);

    // 将数据元素 e 插入到线性表开端
    public void add(Object e);

    // 将数据元素 e 插入到元素 obj 之前
    public boolean addBefore(Object obj, Object e);

    // 将数据元素 e 插入到元素 obj 之后
    public boolean addAfter(Object obj, Object e);

    // 删除线性表中序号为 i 的元素，并返回之
    public Object remove(int i);

    // 删除线性表中第一个与 e 雷同的元素
    public boolean remove(Object e);

    // 替换线性表中序号为 i 的数据元素为 e，返回原数据元素
    public Object replace(int i, Object e);
}

二、创立程序表类 ArrayList 并实现接口 List

1、程序表底层采纳的是数组，长度能够动态变化

    private Object[] elementData; // 底层是一个数组，目前还没有确定长度
    private int size; // 不是数组调配了几个空间，而是数组中元素的个数 

2、编写构造方法指定数组初始长度

public ArrayList(int initalCapacity) {
        // 给数组调配指定数量的空间
        elementData = new Object[initalCapacity];
        // 指定程序表的元素个数，默认是 0
//        size = 0;
    }
public ArrayList() {
        // 没有指定长度，默认长度是 4
        this(4);
    }

以上代码写完，就能够创立程序表了，然而外面的操作方法还没有实现

3、实现 add 办法，将数据元素 e 插入到线性表中 i 号地位，代码如下

    public void add(int i, Object e) {
        //i 的地位要正确
        if (i<0 || i > size){throw new MyArrayIndexOutOfBoundsException("数组索引越界异样："+i);
        }
        // 数组元素个数等于数组长度时，须要扩容
        if(size == elementData.length){
            // 扩容办法
            grow();}
        // 后移 i 及其前面的元素，从最初一个元素开始
        for (int j = size; j > i ; j--) {elementData[j] = elementData[j-1];
        }
        // 给数组第 i 个地位赋值
        elementData[i] = e;
        // 数组元素个数 +1
        size++;
    }

首先判断索引是否正确，不正确就抛出一个自定义异样

public class MyArrayIndexOutOfBoundsException extends RuntimeException {public MyArrayIndexOutOfBoundsException() { }

    public MyArrayIndexOutOfBoundsException(String message) {super(message);
    }
}

而后当数组元素个数等于数组长度时，调用 grow() 办法进行扩容，grow() 办法有两种实现

    // 基本思路是这样
    private void grow(){
        // 创立一个新数组，长度是旧数组 2 倍
        Object[] newArr = new Object[elementData.length * 2];
        // 将旧数组数据拷贝到新数组
        for (int i = 0; i < size; i++) {newArr[i] = elementData[i];
        }
        // 让旧数组 指向 新数组
        elementData = newArr;
    }
    
    // 一步到位
    private void grow(){
        // 扩容 拷贝 赋值
        elementData = Arrays.copyOf(elementData, elementData.length * 2);
    }

最初实现增加操作：须要从数组尾部元素开始，将第 i 位及其之后的元素向后移一位，而后把 e 赋值给第 i 个地位的元素，最初数组元素个数 +1

4、把元素增加到线性表开端，是 add() 办法的非凡状况

    public void add(Object e) {this.add(size, e);
    }

5、get() 办法，返回线性表中序号为 i 的元素，即数组中下标为 i 的元素

    public Object get(int i) {if (i < 0 || i >= size) {//i < 0 或者 i >= size
            throw new MyArrayIndexOutOfBoundsException("数组索引越界异样：" + i);
        }
        return elementData[i];
    }

判断索引是否正确，谬误抛出自定义异样

6、remove(int i) 办法，删除线性表中序号为 i 的元素，并返回之

    public Object remove(int i) {if (i < 0 || i >= size) {throw new MyArrayIndexOutOfBoundsException("数组越界异样："+ i);
        }
        Object empt = elementData[i];
        for (int j = i; j < size; j++) {elementData[j] = elementData[j+1];
        }
        elementData[size-1] = null;
        size--;
        return empt;
    }

三、重写 toString() 办法

    public String toString() {if (size == 0){return "[]";
        }
        StringBuilder builder = new StringBuilder("[");
        for (int i = 0; i < size; i++) {if (i != size - 1){builder.append(elementData[i]+",");
            }else {builder.append(elementData[i]);
            }
        }
        builder.append("]");
        return builder.toString();}

扩大

StringBuffer 和 StringBuilder 十分相似，均代表可变的字符序列。这两个类都是抽象类 AbstractStringBuilder 的子类，办法简直截然不同。
StringBuffer 线程平安，做线程同步查看，效率较低。
StringBuilder 线程不平安，不做线程同步查看，因而效率较高。倡议应用该类。

四、外围

数组扩容、元素前移、后移

ArrayList 源码中扩容为 50%

int newCapacity = oldCapacity + (oldCapacity >> 1);