线性表之顺序表的实现

/**
* 线性表接口
*
* @ClassName List
* @Description 线性表接口
* @Author HuangCanCan
* @Date 2019/8/11 15:30
* @Version 1.0
**/
public interface List {
    /**
    * 返回线性表的大小，即数据元素的个数。
    */
    public int size();

    /**
    * 返回线性表中索引为 index的数据元素
    */
    public Object get(int index);

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

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

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

    /**
    * 将数据元素 e 插入到线性表中 index 索引的位置
    */
    public void add(int index, 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);

    /**
    * 删除线性表中索引为 index 的元素,并返回原数据元素
    */
    public Object remove(int index);

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

    /**
    * 替换线性表中索引为 index的数据元素为 e，返回原数据元素
    */
    public Object replace(int index, Object e);
}

import java.util.Arrays;

/**
* 顺序表，模拟ArrayList
* <p>
* 底层采用的数组，但是长度可以动态变化
* <p>
* java.util.ArrayList底层的扩容机制是： 每次增长50%(原来的数组长度右移一位)
*
* @ClassName ArrayList
* @Description 顺序表，模拟ArrayList
* @Author HuangCanCan
* @Date 2019/8/11 15:37
* @Version 1.0
**/
public class ArrayList implements List {
    /**
    * 底层是一个数组，目前还没有确定长度
    */
    private Object[] elementData;

    /**
    * 元素的个数
    * <p>
    * 不是数组分配了几个空间，而是元素的个数
    * <p>
    * size的大小，小于或者等于elementData数组的大小
    */
    private int size;

    public ArrayList() {
        this(8);//初始化大小为8

    }

    /**
    * @param initialCapacity 指定数组的初始长度
    */
    public ArrayList(int initialCapacity) {
        //给数组分配指定数量的空间
        this.elementData = new Object[initialCapacity];
        //指定顺序表的元素个数，默认是0
        //size=0;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public Object get(int index) {
        if (index < 0 || index >= size) {
            throw new RuntimeException("数组索引越界异常：" + index);
        }
        return this.elementData[index];
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean contains(Object e) {
        return indexOf(e) >= 0;
    }

    @Override
    public int indexOf(Object e) {//返回第一次出现的指定元素的索引
        if (e == null) {
            for (int i = 0; i < size; i++) {
                if (elementData[i] == null) {
                    return i;
                }
            }
        } else {
            for (int i = 0; i < size; i++) {
                if (e.equals(elementData[i])) {
                    return i;
                }
            }
        }
        return -1; //找不到元素就返回负数
    }

    @Override
    public void add(int index, Object e) {
        if (index < 0 || index >= size) {
            throw new RuntimeException("数组索引越界异常：" + index);
        }
        /*
        * 第一步：数组elementData的动态扩容
        * 数组扩容条件：数组满的时候 size == elementData.length
        * 扩容策略：增长一倍 或 增长一半
        * java.util.ArrayList底层的扩容机制是： 每次增长50%(原来的数组长度右移一位)
        */
        if (size == elementData.length) {
            grow();
        }
        /*
        * 第二部：  后移i及其后面元素，从最后一个元素开e始
        */
        for (int j = size; j > index; index--) {
            elementData[j] = elementData[j - 1];
        }

        /*
        * 第三步：给数组elementData第i个位置赋值赋值，元素个数size + 1
        */
        this.elementData[index] = e; //给数组赋值
        size++;//元素个数 + 1

    }

    @Override
    public void add(Object e) {
        /*
        * 第二步：数组elementData的动态扩容
        * 数组扩容条件：数组满的时候 size == elementData.length
        * 扩容策略：增长一倍 或 增长一半
        * java.util.ArrayList底层的扩容机制是： 每次增长50%(原来的数组长度右移一位)
        */
        if (size == elementData.length) {
            grow();
        }

        /*
        * 第一步：给数组elementData赋值，元素个数size + 1
        */
//        this.elementData[size] = e; //给数组赋值
//        size++;//元素个数 + 1
        this.elementData[size++] = e; //上面两句等同于这句

        System.out.println("length=" + elementData.length);

        //add(i,e) 是添加元素到指定位置，这个add(e)是添加元素到数组末尾，是add(i,e)方法特例，可以如下：
//        this.add(size,e);
    }

    private void grow() {
//        //创建一个新的数组，长度是就数组的两倍
//        Object[] newArr = new Object[elementData.length * 2];
//        //将旧数组的数据拷贝到新数组
//        for (int i = 0; i < size; i++) {
//            newArr[i] = elementData[i];
//        }
//        //让elementData指向新数组
//        elementData = newArr;

        //上面的步骤等同于下面这句，利用jdk提供的Arrays.copyOf方法
        elementData = Arrays.copyOf(elementData, elementData.length * 2);
    }

    @Override
    public boolean addBefore(Object obj, Object e) {//将数据元素 e 插入到元素 obj 之前,元素e是第一次出现的位置
        /**
        * 第一：找到元素obj的索引
        * 第二：把元素obj后面的元素向后移动一个位置（包含obj元素），
        * 第三步：把元素e放到obj元素的位置
        * 其实就是创建一个新数组，把元素obj前面的元素依次放到新数组中相应的位置；把元素e放到obj元素原来的位置；
        * 把包含元素obj以及obj后面的元素放到这个新数组中e元素的后面。
        * 新数组的长度为数组元素的个数+1
        */

        int index = indexOf(obj);
        if (index < 0) {
//            throw new RuntimeException("找不到该元素：" + obj);
            return false;
        }
        Object[] newArr = new Object[size + 1];
        for (int i = 0; i < size; i++) {
            if (i < index) {
                newArr[i] = elementData[i];
            }
            if (i == index) {
                newArr[i] = e;
                newArr[i + 1] = elementData[i];
            }
            if (i > index) {
                newArr[i + 1] = elementData[i];
            }
        }
        elementData = newArr;
        size++;
        return true;
    }

    @Override
    public boolean addAfter(Object obj, Object e) {//将数据元素 e 插入到元素 obj 之后，元素e是第一次出现的位置
        /**
        * 第一：找到元素obj的索引
        * 第二：把元素obj后面的元素往后移（不包含元素obj）
        * 第三：把元素e放到obj元素后一个位置
        */
        int index = indexOf(obj);
        if (index < 0) {
            return false;
        }
        Object[] newArr = new Object[size + 1];
        for (int i = 0; i < size; i++) {
            if (i <= index) {
                newArr[i] = elementData[i];
            }
            newArr[i + 1] = elementData[i];

            if (i == size - 1) {
                newArr[index + 1] = e;
            }
        }
        elementData = newArr;
        size++;

        return true;
    }

    @Override
    public Object remove(int index) {
        if (index >= size) {
            throw new RuntimeException("索引越界异常：" + index);
        }
        Object oldValue = elementData[index];

        /**
        * 将该索引i后面的元素向前移动一位
        */
//        Object[] newArr = new Object[size + 1];
//
//        for (int x = 0; x < size; x++) {
//            newArr[x] = elementData[x];
//            if (x >= index) {
//                newArr[x] = elementData[x + 1];
//            }
//        }
//        elementData = newArr;

//            上面注释的部分就等同于以下部分：
        int numMoved = size - index - 1;//需要移动删除的元素个数
        if (numMoved > 0)
            System.arraycopy(elementData, index + 1, elementData, index,
                    numMoved);

        size--;
        return oldValue;
    }

    @Override
    public boolean remove(Object e) {//删除第一个与 e 相同的元素
        int index = indexOf(e);
        if (index < 0) {
            return false;
        }
        remove(index);
        return true;
    }

    @Override
    public Object replace(int index, Object e) {//替换索引为 index 的数据元素为 e，返回原数据元素
        if (index >= size) {
            throw new RuntimeException("索引越界异常：" + index);
        }
        Object oldValue = elementData[index];
        elementData[index] = e;
        return oldValue;
    }

    @Override
    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();
    }
}