当前位置：首页 > news >正文

Java数据结构——ArrayList

news 2025/7/23 12:54:14

一、线性表

二、顺序表（模拟实现）

2.1需要模拟实现的接口功能

2.2 具体功能实现

2.2.1 初始化

2.2.2 扩容

2.2.3 add(int data) 尾插

2.2.4 add(int pos,int data) 插入到指定位置

2.2.5 contains(int toFind)

2.2.6 查询元素的位置

2.2.7 查询位置的元素

2.2.8 设置指定位置的元素

2.2.9 删除元素

2.2.10 打印

2.2.11 判满和判空

三、ArrayList简介

四、ArrayList使用

4.1 ArrayList的构造

4.1.1 无参构造

4.1.2 指定容量构造

4.1.3 利用其他collection构造

4.2 ArrayList的常见操作

4.3 ArrayList的遍历

4.3.1 for + 下标循环

4.3.2 for each 循环

4.3.3 迭代器循环

一、线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列...

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

二、顺序表（模拟实现）

2.1需要模拟实现的接口功能

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

2.2 具体功能实现

2.2.1 初始化

public class MyArrayList implements IList{public int[] elem;public int usedSize;//有效数据个数public MyArrayList(){this.elem=new int[10];}
}

顺序表的底层是用数组实现的，在构造方法中先初始化10个数组容量

2.2.2 扩容

    private void resize(){elem= Arrays.copyOf(elem,2*elem.length);}

如果数组空间不够，我们将数组大小扩大两倍

2.2.3 add(int data) 尾插

    @Overridepublic void add(int data) {//尾插if(isFull()){//扩容resize();}elem[usedSize]=data;usedSize++;}

尾插就是把数据插入到数组有效个数的下一个位置，插入之前我们需要判断是否空间满了，如果满了则扩容，尾插后有效数据个数也要+1

2.2.4 add(int pos,int data) 插入到指定位置

    @Overridepublic void add(int pos, int data) {//把数据存放到指定位置//顺序表插入数据的时候一定要有一个唯一的前驱，不可以跳着插入if(pos<0||pos>usedSize){throw  new PosOutException("pos位置不合法");}if(isFull()){resize();}for(int i=usedSize-1;i>=pos;i--){elem[i+1]=elem[i];}elem[pos]=data;usedSize++;}

插入到pos位置，首先我们需要保证pos位置的合法性，如果pos<0或者pos>usedSize则pos位置违法，因为插入的位置必须有前驱，不可以留有空位。如下图pos=5>usedSize,则留有空位违法

如果我们要在中间插入数据，我们需要移动pos位置之后的数据

我们需要从后往前移动数据，这样才能保证不被覆盖

如果采用下面的移动方法，从前往后移动，数据就会被覆盖