Java数据结构——ArrayList
·
目录
2.2.4 add(int pos,int data) 插入到指定位置
一、线性表
线性表（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 位置的元素设为 value
void set(int pos, int value);
//删除第一次出现的关键字key
void 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) 尾插
@Override
public void add(int data) {//尾插
if(isFull()){
//扩容
resize();
}
elem[usedSize]=data;
usedSize++;
}尾插就是把数据插入到数组有效个数的下一个位置，插入之前我们需要判断是否空间满了，如果满了则扩容，尾插后有效数据个数也要+1
2.2.4 add(int pos,int data) 插入到指定位置
@Override
public 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位置之后的数据
我们需要从后往前移动数据，这样才能保证不被覆盖
如果采用下面的移动方法，从前往后移动，数据就会被覆盖
2.2.5 contains(int toFind)
查询顺序表是否包含查询的元素
@Override
public boolean contains(int toFind) {
if(isEmpty()) return false;
for(int i=0;i<usedSize;i++){
if(elem[i]==toFind){
return true;
}
}
return false;
}2.2.6 查询元素的位置
@Override
public int indexOf(int toFind) {
if(isEmpty()){
return -1;
}
for (int i = 0; i < usedSize; i++) {
if(elem[i]==toFind){
return i;
}
}
return -1;
}2.2.7 查询位置的元素
@Override
public int get(int pos) {
if(pos<0||pos>=usedSize){
throw new PosOutException("pos位置不合法");
}
return elem[pos];
}2.2.8 设置指定位置的元素
@Override
public void set(int pos, int value) {
if(pos<0||pos>=usedSize){
throw new PosOutException("pos位置不合法");
}
elem[pos]=value;
}2.2.9 删除元素
@Override
public void remove(int toRemove) {
int index=indexOf(toRemove);
if(index==-1) return;
for(int i=0;i<usedSize-1;i++){
elem[i]=elem[i+1];
}
usedSize--;
}删除元素跟添加元素相反，我们把元素从前到后往前一个位置移动
2.2.10 打印
@Override
public void display() {
for (int i = 0; i < usedSize; i++) {
System.out.print(elem[i]+" ");
}
}2.2.11 判满 和 判空
@Override
public boolean isFull() {
if(elem.length==usedSize){
return false;
}else{
return true;
}
}
@Override
public boolean isEmpty(){
if(usedSize==0){
return true;
}else{
return false;
}
}三、ArrayList简介
ArrayList是一个普通的类，实现了List接口，具体框架图如下
- ArrayList是以泛型方式实现的，使用时必须要先实例化
- ArrayList实现了RandomAccess接口，表明ArrayList支持随机访问
- ArrayList实现了Cloneable接口，表明ArrayList是可以clone的
- ArrayList实现了Serializable接口，表明ArrayList是支持序列化的
- 和Vector不同，ArrayList不是线程安全的，在单线程下可以使用，在多线程中可以选择Vector或者CopyOnWriteArrayList
- ArrayList底层是一段连续的空间，并且可以动态扩容，是一个动态类型的顺序表
四、ArrayList使用
4.1 ArrayList的构造
4.1.1 无参构造
public static void main(String[] args) {
//构造一个空的顺序表
ArrayList<Integer> arrayList=new ArrayList<>();
}4.1.2 指定容量构造
public static void main(String[] args) {
//构造一个容量为3的顺序表
ArrayList<Integer> arrayList=new ArrayList<>(10);
arrayList.add(1);
arrayList.add(2);
arrayList.add(3);
System.out.println(arrayList); // [1, 2, 3]
}4.1.3 利用其他collection构造
public static void main(String[] args) {
ArrayList<Integer> arrayList=new ArrayList<>();
arrayList.add(1);
arrayList.add(2);
arrayList.add(3);
System.out.println(arrayList); //[1, 2, 3]
ArrayList<Integer> arrayList1=new ArrayList<>(arrayList);
arrayList1.add(99);
System.out.println(arrayList1); //[1, 2, 3, 99]
}4.2 ArrayList的常见操作
| 方法 | 解释 |
| boolean add(E e) | 尾插e |
| void add(int index,E element) | 将e插入到index位置 |
| boolean addAll(Collection<? extends E> c) | 尾插c中的元素 |
| E remove(int index) | 删除index位置元素 |
| boolean remove(Object o) | 删除遇到的第一个o |
| E get(int index) | 获取下标index位置元素 |
| E set(int index,E element) | 将下标index位置元素设置为element |
| void clear() | 清空 |
| boolean contains(Object o) | 判断o是否在线性表中 |
| int indexOf(Object o) | 返回第一个o所在下标 |
| int lastIndexOf(Object o) | 返回最后一个o的下标 |
| List<E> subList(int fromIndex,int toIndex) | 截取部分list |
4.3 ArrayList的遍历
4.3.1 for + 下标 循环
public static void main(String[] args) {
ArrayList<Integer> list=new ArrayList<>();
list.add(0);
list.add(1);
list.add(2);
list.add(3);
list.add(4);
System.out.println(list);
System.out.println("====for+下标=======");
for(int i=0;i<list.size();i++){
System.out.print(list.get(i)+" ");
}
}4.3.2 for each 循环
public static void main(String[] args) {
ArrayList<Integer> list=new ArrayList<>();
list.add(0);
list.add(1);
list.add(2);
list.add(3);
list.add(4);
System.out.println(list);
System.out.println("=====for each循环=======");
for (Integer x:list) {
System.out.print(x+" ");
}
}4.3.3 迭代器循环
public static void main(String[] args) {
ArrayList<Integer> list=new ArrayList<>();
list.add(0);
list.add(1);
list.add(2);
list.add(3);
list.add(4);
System.out.println(list);
System.out.println();
System.out.println("======Iterator迭代器遍历======="); //0 1 2 3 4
Iterator<Integer> it=list.iterator();
while(it.hasNext()){
System.out.print(it.next()+" ");
}
System.out.println();
System.out.println("=======ListIterator迭代器遍历2========"); //0 1 2 3 4
ListIterator<Integer> lit=list.listIterator();
while(lit.hasNext()){
System.out.print(lit.next()+" ");
}
System.out.println();
System.out.println("=====逆序迭代器遍历3======="); //4 3 2 1 0
ListIterator<Integer> litPrev=list.listIterator(list.size());
while(litPrev.hasPrevious()){
System.out.print(litPrev.previous()+" ");
}
System.out.println();
}
北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台
更多推荐
20
0- 0
已为社区贡献4条内容
所有评论(0)