目录
一、线性表
二、顺序表
2.1、顺序表的定义
2.2、顺序表的接口实现
三、ArrayList
3.1、 ArrayList简介
3.2、ArrayList的实现
3.3、ArrayList实现的完整代码
一、线性表
线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列...
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。
二、顺序表
2.1、顺序表的定义
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
2.2、顺序表的接口实现
public interface List {// 新增元素,默认在数组最后新增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 位置的元素设为 valuepublic void set(int pos, int value);//删除第一次出现的关键字keypublic void remove(int toRemove);// 获取顺序表长度public int size();// 清空顺序表public void clear();// 打印顺序表，注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的public void display();//判断数组是否满了public boolean isFulled();
}
三、ArrayList
3.1、 ArrayList简介
在集合框架中，ArrayList是一个普通的类，实现了List接口。
注意：
1. ArrayList是以泛型方式实现的，使用时必须要先实例化
2. ArrayList实现了RandomAccess接口，表明ArrayList支持随机访问
3. ArrayList实现了Cloneable接口，表明ArrayList是可以clone的
4. ArrayList实现了Serializable接口，表明ArrayList是支持序列化的
5. 和Vector不同，ArrayList不是线程安全的，在单线程下可以使用，在多线程中可以选择Vector或者 CopyOnWriteArrayList
6. ArrayList底层是一段连续的空间，并且可以动态扩容，是一个动态类型的顺序表
3.2、ArrayList的实现
在实现顺序表之前，我们要先定义一个数组、一个整型变量和一个构造方法：
public int[] als;public int usedSize;public MyArrayList() {this.als =new int[10];}
//新增一个元素，默认在数组最后新增
//新增一个元素，默认在数组最后新增@Overridepublic void add(int data) {if(isFulled()){reSize();}als[usedSize]=data;usedSize++;}//判断顺序表是否已满
//判断顺序表是否已满@Overridepublic boolean isFulled() {return usedSize==als.length;}//若顺序表已满，进行扩容private void reSize(){als= Arrays.copyOf(als,2*als.length);}//在pos位置新增元素data
//在pos位置新增元素data@Overridepublic void add(int pos, int data) {if(pos<=usedSize&&pos>=0){if(isFulled()){reSize();}for(int i=usedSize-1;i>=pos;i--){als[i+1]=als[i];}als[pos]=data;usedSize++;}else{throw new PosOutOfException("数据不合法");//该异常为我自身设定，各位使用时需另外设定}}异常设置的代码：
public class PosOutOfException extends RuntimeException{public PosOutOfException(String message) {super(message);}
}
//判断是否包含元素toFind
//判断是否包含元素toFind@Overridepublic boolean contains(int toFind) {for(int i=0;i<usedSize;i++){if(als[i]==toFind){return true;}}return false;}
//查找某个元素对应的位置,如果未找到，返回-1
//查找某个元素对应的位置,如果未找到，返回-1@Overridepublic int indexOf(int toFind) {int num=-1;for(int i=0;i<usedSize;i++){if(als[i]==toFind){num=i;break;}}return num;}// 获取 pos 位置的元素
// 获取 pos 位置的元素@Overridepublic int get(int pos) {if(pos>=0&&pos<usedSize){return als[pos];}else{throw new PosOutOfException("pos位置不合法");}}// 给 pos 位置的元素设为 value
// 给 pos 位置的元素设为 value@Overridepublic void set(int pos, int value) {if(pos>=0&&pos<usedSize){als[pos]=value;}else{throw new PosOutOfException("pos位置不合法");}}
//删除第一次出现的关键字toRemove
//删除第一次出现的关键字toRemove@Overridepublic void remove(int toRemove) {int index=indexOf(toRemove);if(index==-1){return;}for(int i=index;i<usedSize-1;i++){als[i]=als[i+1];}usedSize--;}// 获取顺序表长度
// 获取顺序表长度@Overridepublic int size() {return this.usedSize;}// 清空顺序表
// 清空顺序表@Overridepublic void clear() {usedSize=0;}// 打印顺序表，注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的
// 打印顺序表，注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的@Overridepublic void display() {for(int i=0;i<usedSize;i++){System.out.print(als[i]+" ");}}注意：调用方法时用“.”来调用，以下以display()为例：
public class Main {public static void main(String[] args) {MyArrayList myArrayList=new MyArrayList();myArrayList.add(1);myArrayList.add(2);myArrayList.add(66);myArrayList.display();}
}结果如下：
3.3、ArrayList实现的完整代码
import java.util.Arrays;public class MyArrayList implements List{public int[] als;public int usedSize;public MyArrayList() {this.als =new int[10];}//新增一个元素，默认在数组最后新增@Overridepublic void add(int data) {if(isFulled()){reSize();}als[usedSize]=data;usedSize++;}//判断顺序表是否已满@Overridepublic boolean isFulled() {return usedSize==als.length;}//若顺序表已满，进行扩容private void reSize(){als= Arrays.copyOf(als,2*als.length);}//在pos位置新增元素data@Overridepublic void add(int pos, int data) {if(pos<=usedSize&&pos>=0){if(isFulled()){reSize();}for(int i=usedSize-1;i>=pos;i--){als[i+1]=als[i];}als[pos]=data;usedSize++;}else{throw new PosOutOfException("数据不合法");//该异常为我自身设定，各位使用时需另外设定}}//判断是否包含元素toFind@Overridepublic boolean contains(int toFind) {for(int i=0;i<usedSize;i++){if(als[i]==toFind){return true;}}return false;}//查找某个元素对应的位置,如果未找到，返回-1@Overridepublic int indexOf(int toFind) {int num=-1;for(int i=0;i<usedSize;i++){if(als[i]==toFind){num=i;break;}}return num;}// 获取 pos 位置的元素@Overridepublic int get(int pos) {if(pos>=0&&pos<usedSize){return als[pos];}else{throw new PosOutOfException("pos位置不合法");}}// 给 pos 位置的元素设为 value@Overridepublic void set(int pos, int value) {if(pos>=0&&pos<usedSize){als[pos]=value;}else{throw new PosOutOfException("pos位置不合法");}}//删除第一次出现的关键字toRemove@Overridepublic void remove(int toRemove) {int index=indexOf(toRemove);if(index==-1){return;}for(int i=index;i<usedSize-1;i++){als[i]=als[i+1];}usedSize--;}// 获取顺序表长度@Overridepublic int size() {return this.usedSize;}// 清空顺序表@Overridepublic void clear() {usedSize=0;}// 打印顺序表，注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的@Overridepublic void display() {for(int i=0;i<usedSize;i++){System.out.print(als[i]+" ");}}
}
以上便是本篇文章的全部内容，感谢大家的支持！下期见~~~