前言

在数据结构中，线性表是最基础也是最常用的结构之一，而顺序表作为线性表的重要实现方式，更是每个程序员必须掌握的基础知识。本文将从原理到实践，全面讲解顺序表的设计思想、实现方法及应用场景。

什么是List

在集合框架中，List是一个接口，继承自Collection。

Collection也是一个接口，该接口中规范了后序容器中常用的一些方法，具体如下所示：

Iterable也是一个接口，表示实现该接口的类是可以逐个元素进行遍历的，具体如下：

站在数据结构的角度来看，List就是一个线性表，即n个具有相同类型元素的有限序列，在该序列上可以执行增删改查以及变量等操作。

常见接口介绍

List中提供了好的方法，具体如下：

虽然方法比较多，但是常用方法如下：

线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列…
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

顺序表

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
有一个常用的类叫做ArrayLIst类，他实现了List接口，接下来的学习中，ArrayLIst是一个重要的内容。
ArrayList也有许多自定义的方法，为了更灵活的使用，我们初学时可以先模拟实现一下他的常见的方法。

下面我将自己动手实现一下常用方法：
因为是实现了List接口，所以我们也先建立一个接口：

package demo1;

public interface IList {
    // 新增元素,默认在数组最后新增
    public void add(int data) ;
    // 在 pos 位置新增元素
    public void add(int pos, int data) ;
    // 判定是否包含某个元素
    public boolean contains(int toFind) ;
    // 查找某个元素对应的位置
    public int indexOf(int toFind) ;
    // 获取 pos 位置的元素
    public int get(int pos) ;
    // 给 pos 位置的元素设为 value
    public void set(int pos, int value) ;
    //删除第一次出现的关键字key
    public void remove(int toRemove) ;
    // 获取顺序表长度
    public int size() ;
    // 清空顺序表
    public void clear();
    // 打印顺序表，注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的
    public void display();
}

针对这些方法，在MyArrayList中尝试实现：

package demo1;

import java.util.Arrays;

public class MyArrayList implements IList {
    private int[] array;
    private int usedsize;
    public static final int CAPACITY = 10;
    public MyArrayList(){
        this.array = new int[CAPACITY];
    }
    @Override
    public void add(int data) {
        if(isFull()){
            growSize();
        }
        array[usedsize] = data;
        usedsize++;
    }

    public void growSize(){
        this.array = Arrays.copyOf(array,2*array.length);
    }

    public boolean isFull(){
        return this.array.length == usedsize;
    }

    public void checkPos(int pos) throws PosIllegal{
        if(pos < 0 || pos >usedsize){
            throw new PosIllegal("插入位置不合法");
        }
    }
    @Override
    public void add(int pos, int data) {
        try{
            checkPos(pos);
            if(isFull()){
                growSize();
            }
            int n = usedsize - 1;
            while(n >= pos){
                array[n + 1] = array[n];
                n--;
            }
            array[pos] = data;
            usedsize++;
        }catch(PosIllegal e){
            e.printStackTrace();
        }
    }

    @Override
    public boolean contains(int toFind) {
        for (int i = 0; i < usedsize; i++) {
            if(array[i] == toFind){
                return true;
            }
        }

        return false;
    }

    @Override
    public int indexOf(int toFind) {
        for (int i = 0; i < usedsize; i++) {
            if(array[i] == toFind){
                return i;
            }
        }
        return -1;
    }

    public void isEmpty ()throws EmptyException{
        if(this.usedsize == 0){
            throw new EmptyException("目标为空表");
        }
    }

    private void checkPos2(int pos)throws PosIllegal{
        if(pos < 0 || pos >=usedsize){
            throw new PosIllegal("目标位置不合法");
        }
    }
    @Override
    public int get(int pos) {
        try{
            isEmpty();
            checkPos2(pos);
            return array[pos];

        }catch(PosIllegal e){
            e.printStackTrace();
        }catch(EmptyException e){
            e.printStackTrace();
        }
        return -1;
    }

    @Override
    public void set(int pos, int value) {
        try{
            isEmpty();
            checkPos2(pos);
            array[pos] = value;

        }catch(PosIllegal e){
            e.printStackTrace();
        }catch(EmptyException e){
            e.printStackTrace();
        }

    }

    @Override
    public void remove(int toRemove) {
        try{
            isEmpty();
            int index = indexOf(toRemove);
            if(index == -1){
                return;
            }
            for (int i = index; i < usedsize - 1; i++) {
                array[i] = array[i + 1];
            }
            usedsize--;
        }catch(EmptyException e){
            e.printStackTrace();
        }
    }

    @Override
    public int size() {
        return this.usedsize;
    }

    @Override
    public void clear() {
        this.usedsize = 0;
    }

    @Override
    public void display() {
        for (int i = 0; i < usedsize; i++) {
            System.out.print(array[i] + " ");
        }
        System.out.println();
    }
}

因为是初学，所以建议大家动手亲自实现一下ArrayLIst类，然后，我们进入下一章深入学习一下ArrayLIst。