使用顺序存储结构实现线性表（顺序表）

1、什么是顺序存储结构

  顺序存储是所有的结点元素存放在一块连续的存储区域中，用存储结点的物理位置来体现结点之间的逻辑关系的存储方法。在高级语言中，一块连续的存储空间通常可用一个数组来表示。因此，顺序存储通常用一个数据元素类型的数组来存储。最经典的顺序存储结构是顺序表，将线性结构的元素按序存放在一个数组中。

2、什么是线性表

  线性表是最基本、最简单、也是最常用的一种数据结构。线性表（linear list）是数据结构的一种，一个线性表是 n 个具有相同特性的数据元素的有限序列。线性表中数据元素之间的关系是一对一的关系，线性表主要由顺序表示或链式表示，在实际应用中，常以栈、队列、字符串等特殊形式使用。

  顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素，称为线性表的顺序存储结构或顺序表。它以“物理位置相邻”来表示线性表中数据元素间的逻辑关系，可随机存取表中任一元素。

  链式表示指的是用一组任意的存储单元存储线性表中的数据元素，称为线性表的链式存储结构。它的存储单元可以是连续的，也可以是不连续的。在表示数据元素之间的逻辑关系时，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置），这两部分信息组成数据元素的存储映像，称为结点（node）。它包括两个域；存储数据元素信息的域称为数据域；存储直接后继存储位置的域称为指针域。指针域中存储的信息称为指针或链。

3、Java ArrayList 源码剖析

  Java 的 JDK 中封装了很多数据结构，其中 ArrayList 就是线性表的顺序存储结构。
  ArrayList 实现了 List 接口，是顺序容器，即元素存放的数据与放进去的顺序相同，允许放入 null 元素，底层通过数组实现。每个 ArrayList 都有一个默认容量（capacity），表示底层数组的实际大小，容器内存储元素的个数不能多于当前容量。当向容器中添加元素时，如果容量不足，容器会自动增大底层数组的大小。

定义 MyList 接口

  在 JDK 中 List 是线性结构的接口，所有的线性结构都要实现该接口。我们定义一个简化版的 List 接口 MyList，包含一些常用的方法。
  因为我们的线性结构中存储的元素类型并不确定，所以我们使用泛型来表示未确定的数据类型。

/**
 * 线性结构接口的定义
 **/
public interface MyList<T> {

    /**
     * 新增一个元素
     */
    void add(T value);

    /**
     * 向指定下标添加元素
     */
    void insert(int index, T value);

    /**
     * 删除第一个相同的元素
     */
    void delete(T value);

    /**
     * 根据索引删除元素
     */
    void delete(int index);

    /**
     * 将指定索引位置的元素替换成新元素
     */
    void update(int index, T value);

    /**
     * 当前列表中是否含有 target 这个元素
     */
    boolean contains(T target);

    /**
     * 返回指定索引处的元素
     */
     T at(int index);

    /**
     * 查找 element 的索引，如果没有返回-1
     */
    int indexOf(T element);

    /**
     * 返回元素的个数
     */
     int getSize();
}

实现类 MyArrayList

  顺序表是通过数组实现的，我们在 MyArrayList 中定义一个类型为泛型的数组用来存储顺序表中的数据（元素）；其中 size 表示顺序表中元素的个数，即数组中有效元素的个数；而 capacity 表示顺序表当前的最大容量，即数组的长度。

/**
 * 用顺序存储（数组）方式来实现线性表（顺序表）
 **/
public class MyArrayList<T> implements MyList<T> {
    /**
     * 真正存储元素的底层结构
     */
    private T[] elements;

    /**
     * 元素个数
     */
    private int size = 0;

    /**
     * 容量（默认容量为10）
     */
    private int capacity = 10;
}

1）创建顺序表

  创建顺序表的方法有两种：

1. 用户不指定顺序表的容量，使用默认的容量创建顺序表。
2. 根据用户指定的容量来创建顺序表。

    /**
     * 指定容量创建顺序表
     */
    public MyArrayList(int capacity) {
        // 如果数据合法，则创建指定容量的数组，否则使用默认值
        if (capacity > 0) {
            this.capacity = capacity;
        }
        elements = (T[]) new Object[capacity];
    }

    /**
     * 如果用户没有指定容量，则使用默认容量创建顺序表
     */
    public MyArrayList() {
        elements = (T[]) new Object[capacity];
    }

2）添加元素

  由于顺序表是通过数组实现的，当数组容量不足时，需要先对数组进行扩容，再添加数据。

    @Override
    public void add(T value) {
        // 当元素的个数等于容量时，需要对数组进行扩容
        if (size == capacity) {
            capacity *= 2;
            // 创建一个更大容量的数组
            T[] newArray = (T[]) new Object[capacity];
            // 将原数组中的值拷到新数组中
            // for (int i = 0; i < size; i++) {
            //    newArray[i]=elements[i];
            // }
            System.arraycopy(elements, 0, newArray, 0, size);
            elements = newArray;
        }
        elements[size++] = value;
    }

3）插入元素

  插入元素分两种情况：

1. 向顺序表的末尾加入元素：直接调用 add 方法即可。
2. 向顺序表中插入元素：先判断顺序表的容量是否足够，如果不足先进行扩容。然后将该顺序表的元素向后移动，为即将加入的元素空出位置，最后插入元素。（类似于数组的插入排序）

    @Override
    public void insert(int index, T value) {
        // 如果下标等于 size，则是向顺序表的末尾添加元素，直接调用 add 方法即可
        if (index == size) {
            add(value);
        } else if (index > -1 && index < size) {
            // 下标大于-1 且小于元素的个数，则表示向顺序表中插入元素
            // 如果元素的个数等于容量时，先对数组进行扩容
            if (size == capacity) {
                capacity *= 2;
                T[] newArray = (T[]) new Object[capacity];
                // 将原数组中的值拷到新数组中
                System.arraycopy(elements, 0, newArray, 0, size);
                elements = newArray;
            }
            //
            int pointer = size;
            // 逆序遍历顺序表
            while (pointer >= index) {
                // 如果 pointer 等于0则元素无需移动
                if (pointer != 0) {
                    // 将前一个元素赋给当前元素
                    elements[pointer] = elements[pointer - 1];
                }
                pointer--;
            }
            // 插入元素
            elements[index] = value;
            // 个数自加
            size++;
        }
    }

4）删除元素

  删除元素的方式分为：根据下标删除元素和根据元素值删除元素。

  根据下标删除元素，首先判断下标是否合法，如果合法只需将数组中该元素后的元素向前移动一格即可。

    @Override
    public void delete(int index) {
        // 如果下标合法，则将数组中的元素向前移动，覆盖要删除的元素
        if (index > -1 && index < size) {
            while (index < size - 1) {
                elements[index] = elements[index + 1];
                index++;
            }
            // 删除后元素长度减一
            size--;
        }
    }

  根据值删除元素，则只会删除顺序表中第一个和该值相等的元素。首先遍历顺序表查找指定元素的下标，然后进行删除。

    @Override
    public void delete(T value) {
        // 查找 value 元素在顺序表的下标
        int index = indexOf(value);
        // 如果存在则进行删除
        if (index >= 0) {
            delete(index);
        }
    }

    @Override
    public int indexOf(T element) {
        // 遍历顺序表查找第一个和 element 值相等的元素并返回下标
        for (int i = 0; i < size; i++) {
            if (elements[i].equals(element)) {
                return i;
            }
        }
        return -1;
    }

5）打印顺序表

  在 java 中输出一个类的值就是在调用该类的 toString 方法，所以我们只需要重写 toString 方法即可。在重写 toString 方法时，我们只需要返回顺序表中有效的值即可。

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("[");
        for (int i = 0; i < size; i++) {
            sb.append(elements[i]).append(i == size - 1 ? "" : ", ");
        }
        sb.append("]");
        return sb.toString();
    }

总结

  其他的方法的实现比较简单，这里不多做解释，MyArrayList 的全部代码如下：

/**
 * 用顺序存储（数组）方式来实现线性表（顺序表）
 **/
public class MyArrayList<T> implements MyList<T> {
    /**
     * 真正存储元素的底层结构
     */
    private T[] elements;

    /**
     * 元素个数
     */
    private int size = 0;

    /**
     * 容量（默认容量为10）
     */
    private int capacity = 10;

    /**
     * 指定容量创建顺序表
     */
    public MyArrayList(int capacity) {
        // 如果数据合法，则创建指定容量的数组，否则使用默认值
        if (capacity > 0) {
            this.capacity = capacity;
        }
        elements = (T[]) new Object[capacity];
    }

    /**
     * 如果用户没有指定容量，则使用默认容量创建顺序表
     */
    public MyArrayList() {
        elements = (T[]) new Object[capacity];
    }

    @Override
    public void add(T value) {
        // 当元素的个数等于容量时，需要对数组进行扩容
        if (size == capacity) {
            capacity *= 2;
            T[] newArray = (T[]) new Object[capacity];
            // 将原数组中的值拷到新数组中
            // for (int i = 0; i < size; i++) {
            //    newArray[i]=elements[i];
            // }
            System.arraycopy(elements, 0, newArray, 0, size);
            elements = newArray;
        }
        elements[size++] = value;
    }

    @Override
    public void insert(int index, T value) {
        // 如果下标等于size，则是向顺序表的末尾添加元素，直接调用 add 方法即可
        if (index == size) {
            add(value);
        } else if (index > -1 && index < size) {
            // 下标大于-1且小于元素的个数，则表示向顺序表中插入元素
            // 如果元素的个数等于容量时，先对数组进行扩容
            if (size == capacity) {
                capacity *= 2;
                T[] newArray = (T[]) new Object[capacity];
                // 将原数组中的值拷到新数组中
                System.arraycopy(elements, 0, newArray, 0, size);
                elements = newArray;
            }
            //
            int pointer = size;
            // 逆序遍历顺序表
            while (pointer >= index) {
                // 如果 pointer 等于0则元素无需移动
                if (pointer != 0) {
                    // 将前一个元素赋给当前元素
                    elements[pointer] = elements[pointer - 1];
                }
                pointer--;
            }
            // 插入元素
            elements[index] = value;
            // 个数自加
            size++;
        }
    }

    @Override
    public void delete(T value) {
        int index = indexOf(value);
        if (index >= 0) {
            delete(index);
        }
    }

    @Override
    public void delete(int index) {
        // 如果下标合法，则将数组中的元素向前移动，覆盖要删除的元素
        if (index > -1 && index < size) {
            while (index < size - 1) {
                elements[index] = elements[index + 1];
                index++;
            }
            // 删除后元素长度减一
            size--;
        }
    }

    @Override
    public void update(int index, T value) {
        elements[index] = value;
    }

    @Override
    public boolean contains(T target) {
        return indexOf(target) >= 0;
    }

    @Override
    public T at(int index) {
        return elements[index];
    }

    @Override
    public int indexOf(T element) {
        for (int i = 0; i < size; i++) {
            if (elements[i].equals(element)) {
                return i;
            }
        }
        return -1;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("[");
        for (int i = 0; i < size; i++) {
            sb.append(elements[i]).append(i == size - 1 ? "" : ", ");
        }
        sb.append("]");
        return sb.toString();
    }

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