本文主要是介绍【JAVA数据结构】（ArrayList）顺序表，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
ArrayList 是Java集合框架中的一个类，底层使用的数据结构就是顺序表，它实现了List接口，提供了动态数组的功能，ArrayList可以根据需要自动进行扩容（不指定容量大小也能正常添加元素），允许存储任意类型的对象。
说白了，顺序表就是在数组上完成的增删查改。
ArrayList可以被认为是顺序表的一种实现
为了方便我们更好理解顺序表ArrayList运行原理，我们来模拟实现ArrayList的功能。
【说明】
1. ArrayList是以泛型方式实现的，使用时必须要先实例化
2. ArrayList实现了RandomAccess接口，表明ArrayList支持随机访问
3. ArrayList实现了Cloneable接口，表明ArrayList是可以clone的
4. ArrayList实现了Serializable接口，表明ArrayList是支持序列化的
5. 和Vector不同，ArrayList不是线程安全的，在单线程下可以使用，在多线程中可以选择Vector或者 CopyOnWriteArrayList
6. ArrayList底层是一段连续的空间，并且可以动态扩容，是一个动态类型的顺序表
一. ArrayList接口的实现
MyArrayList类
import java.util.Arrays;public class MyArrayList {int[] item ;//设立数组int UseSize;//用来表示顺序表目前的存储最后一个元素的位置public static final int CAPACITY = 10;//默认数组容量为10//构造方法：默认容量public MyArrayList(){this.item = new int[CAPACITY];}//构造方法重写：指定容量public MyArrayList(int initcapacity){this.item = new int[initcapacity];}// 打印顺序表，注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的//实质：遍历数组public void display (){//这里遍历到存储的最后一个元素位置 即 UseSize ,而非 item.lengthfor (int i = 0; i < this.UseSize; i++) {System.out.print(item[i] + " ");}}// 新增元素,默认在数组最后新增//小心越界情况public void add(int data){//可能越界故在下面方法写一个判断是否数组容量已满的情况if(IsFull()){this.item = Arrays.copyOf(this.item,2*(this.item.length));}this.item[this.UseSize] = data;this.UseSize++;}//越界处理：判断是否数组容量已满的情况public boolean IsFull(){if(this.UseSize == this.item.length){return true;}return false;}// 在 pos 位置新增元素public void add(int pos,int data){//注意判断pos位置是否合法if(pos < 0 || pos > this.UseSize){//System.out.println("位置不合法！");//return;//可以用抛出异常来解决（异常类方法在后面）throw new PosOutOfBoundException(pos + " 位置不合法");}//注意越界if(IsFull()){this.item = Arrays.copyOf(this.item,2*(this.item.length));}//注意 要先挪动包含pos在内后面的所有数据！//切记：从后往前挪！！for (int i = this.UseSize-1; i >= pos; i++) {this.item[i+1] = this.item[i];}this.item[pos] = data;this.UseSize++;}// 判定是否包含某个元素// 返回类型：Boolean//注意：如果是引用类型让你判断呢？//此时就要用equals->返回true or false(注意区别：compareTo ->返回大于 等于 小于 0 数字）public boolean contains(int toFind){for(int i = 0 ;i < this.UseSize;i++){if(this.item[i] == toFind){return true;}}return false;}// 查找某个元素对应的位置public int indexOf(int toFind) {for (int i = 0; i < this.UseSize; i++) {if(this.item[i] == toFind){return i;}}return -1;}// 获取 pos 位置的元素public int get(int pos) {//先判断pos位置是否合法 这里设置一个方法 CheckPosCheckPos(pos);return this.item[pos];}// 给 pos 位置的元素设为 valuepublic void set(int pos, int value) {//同上，先判断pos位置是否合法CheckPos(pos);this.item[pos] = value;}//判单pos的合法性public void CheckPos(int pos){if(pos<0 || pos >= this.UseSize){throw new PosOutOfBoundException(pos + " 位置不合法！");}}//删除第一次出现的数据元素valuepublic void remove(int toRemove) {//先查看是否有这个元素在顺序表中，并得到这个元素位置//可以运用我们上面已经写的方法indexOfint index = this.indexOf(toRemove);if(index == -1){System.out.println("没有这个数据!");return;//注意返回！}//从前往后移动数组的元素，往前覆盖前一个元素//注意！这里index接收的是元素下标，而toRemove是具体的数据for (int i = index; i < this.UseSize-1; i++) {this.item[i] = this.item[i+1];}//引用类型加一步：this.item[UseSize]=null; 即最后一个对象指向要设为空this.UseSize--;}// 获取顺序表长度public int size() {return this.UseSize; }// 清空顺序表public void clear() {//引用类型多一部：删掉的对象指向要设为空null/* for (int i = 0; i < this.UseSize; i++) {this.item[i]=null;} */this.UseSize = 0;}
}PosOutOfBoundsException 异常类
public class PosOutOfBoundException extends RuntimeException{public PosOutOfBoundException() {}public PosOutOfBoundException(String message) {super(message);}
}
二. ArrayList顺序表的使用
1.ArrayListt的构造
public static void main(String[] args) {// ArrayList创建，推荐写法// 构造一个空的列表//无参构造方法，未添加元素时，数组长度为0，//当添加第一个元素时，初始化数组长度为10List<Integer> list1 = new ArrayList<>();//构造一个容量为10的列表List<Integer> list2 = new ArrayList<>(10);list2.add(1);list2.add(2);list2.add(3);// list2.add("hhaha"); // 编译失败，List<Integer>已经限定了，list2中只能存储整形元素//构造一个list2元素一致的列表List<Integer> list3 = new ArrayList<>(list2);//注意！// 避免省略类型如下 ↓↓↓ ，否则：任意类型的元素都可以存放，使用时将是一场灾难// List list4 = new ArrayList();// list4.add("111");// list4.add(100);}2. ArrayList的常用方法
（1）添加元素
public static void main(String[] args) {List<Integer> list = new ArrayList<>();// 1. 尾插list.add(1);//尾插1list.add(2);list.add(3);System.out.println(list.toString()); // [1,2,3]// 2. 在pos位置插入元素datalist.add(1,3); //在1下标插入数据元素3System.out.println(list.toString()); // [1, 3, 2, 3]List<Integer> list1 = new ArrayList<>(list);// 3.将list集合中的元素尾插到list1中list.addAll(list1);System.out.println(list.toString());//[1, 3, 2, 3, 1, 3, 2, 3]// 4. 将list1集合中的元素从1下标插入list中list.addAll(1,list1);System.out.println(list.toString());}（2）删除元素
public static void main(String[] args) {ArrayList<Integer> list = new ArrayList<>();list.add(1);list.add(2);list.add(3);list.add(2);list.add(1);//删除下标为0的元素,并返回该元素int n = list.remove(0);System.out.println(n);// 1System.out.println(list.toString());// [2, 3, 2, 1]//清空元素list.clear();System.out.println(list.toString());// []
}（3）其他方法使用
public static void main(String[] args) {ArrayList<Integer> list= new ArrayList<>();list.add(1);list.add(3);list.add(5);list.add(3);list.add(1);//获取1下标的元素System.out.println(list.get(1));// 3//设置0下标的元素为3System.out.println(list.set(0,3));// 1//判断集合中是否存在元素5System.out.println(list.contains(5));// true//返回第一次3出现的位置System.out.println(list.indexOf(3));// 0//返回最后一次出现3的位置System.out.println(list.lastIndexOf(3));// 3//截取0~3位置的元素List<Integer> sub = list.subList(0,3);System.out.println(sub.toString());// [3, 3, 5]System.out.println(list.toString());// [3, 3, 5, 3, 1]
}
注意！List< E > subList(int fromIndex, int toIndex)方法
使用 subList() 方法截取时，实际上引用了原数组的空间，在对截取的集合进行修改时，也会影响原ArrayList中的值。
废话少说，举例说明：
public static void main(String[] args) {ArrayList<Integer> list= new ArrayList<>();list.add(1);list.add(3);list.add(5);list.add(3);list.add(1);//截取0~3位置的元素List<Integer> sub = list.subList(0,3); //截取的范围是[0, 3)System.out.println(sub.toString());// [3, 3, 5]System.out.println(list.toString());// [3, 3, 5, 3, 1]//由于截取的集合sub仍然是引用了原数组list，故改变sub的值会改变list的值//将sub中元素全部修改为8for (int i = 0; i < sub.size(); i++) {sub.set(i,8);}System.out.println(sub.toString()); // [8, 8, 8]System.out.println(list.toString()); // [8, 8, 8, 3, 1]
}3. ArrayList的遍历
先建立一个顺序表
List<Integer> list = new ArrayList<>();list.add(1);list.add(2);list.add(3);list.add(4);list.add(5);（1）用toString直接打印
System.out.println(list.toString()); //[1, 2, 3, 4, 5]（2）for循环
for (int i = 0; i < list.size(); i++) {System.out.print(list.get(i) + " "); // 1 2 3 4 5}
（3）foreach循环
for (Integer x : list){System.out.print(x + " ");}（4）使用迭代器
Iterator<Integer> iterator = list.iterator(); // 创建迭代器//默认从0开始打印while (iterator.hasNext()){System.out.print(iterator.next() + " ");}4. ArrayList的优缺点
优点：ArrayList（顺序表）适合根据下标查找和更新，此时的时间复杂度为 O (1)
缺点：① 也正是因为ArrayList是一个顺序表，任意位置插入或删除元素的时间复杂度过高O（n）（需要将后面所以的元素进行移动）
② 存放数据时的扩容机制是为1.5倍或2倍扩容，可能会导致内存空间的浪费
希望对你帮助
这篇关于【JAVA数据结构】（ArrayList）顺序表的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
