【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.length
for (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位置是否合法 这里设置一个方法 CheckPos
CheckPos(pos);
return this.item[pos];
}
// 给 pos 位置的元素设为 value
public 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 + " 位置不合法！");
}
}
//删除第一次出现的数据元素value
public void remove(int toRemove) {
//先查看是否有这个元素在顺序表中，并得到这个元素位置
//可以运用我们上面已经写的方法indexOf
int 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，
//当添加第一个元素时，初始化数组长度为10
List<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);//尾插1
list.add(2);
list.add(3);
System.out.println(list.toString()); // [1,2,3]
// 2. 在pos位置插入元素data
list.add(1,3); //在1下标插入数据元素3
System.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);// 1
System.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下标的元素为3
System.out.println(list.set(0,3));// 1
//判断集合中是否存在元素5
System.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中元素全部修改为8
for (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倍扩容，可能会导致内存空间的浪费
希望对你帮助
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2024-09-04，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
