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

数据结构：ArrayList与顺序表

news 2025/1/9 17:25:01

📖一、什么是List

📖二、线性表

📖三、顺序表

🐬1、display()方法

🐬2、add(int data)方法

🐬3、add(int pos, int data)方法

🐬4、contains(int toFind)方法

🐬5、indexOf(int toFind)方法

🐬6、get(int pos)方法

🐬7、set(int pos, int value)方法

🐬8、remove(int toRemove)方法

🐬9、size()方法

🐬10、clear()方法

🐬11、完整代码

📖四、ArrayList简介

📖五、ArrayList的构造

🐬1、ArrayList()无参构造

🐬2、ArrayList(int initialCapacity))带参构造

🐬3、ArrayList(Collection c)利用Collection进行构造

📖六、ArrayList使用

🐬1、addAll(Collection c)方法

🐬2、remove(int index)方法

🐬3、remove(Object o)方法

🐬4、lastIndexOf(Object o)方法

🐬5、ListsubList(int fromIndex,int toIndex)方法

📖七、ArrayList的遍历

🐬1、for循环+下标

🐬2、for each

🐬3、迭代器

📖一、什么是List

在集合框架中，List是一个接口，继承自Collection。而Collection也是一个接口，同时他有一些方法，因此List种有着许多的方法。

虽然有很多方法但我们只需要记住以下一些常用方法即可

方法	解释
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 tolndex)	截取部分 list

📖二、线性表

线性表（linearlist）是n个具有相同特性的数据元素的有限序列。线性表是⼀种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列... 线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

📖三、顺序表

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上他们通常表现为数据的增删查改。（顺序表具有扩容能力，通常以自身的1.5倍或2倍进行扩容）

然而我们知道数组是不具备增删查改的功能的，因此我们需要自己创建一个类，自己来实现自己创建IList接口

下面我们就来实现一个顺序表

🐬1、display()方法

打印顺序表

🐬2、add(int data)方法

新增元素 , 默认在数组最后新增（尾插）

🐬3、add(int pos, int data)方法

在 pos 位置新增元素

🐬4、contains(int toFind)方法

判定是否包含某个元素

🐬5、indexOf(int toFind)方法

查找某个元素对应的位置

🐬6、get(int pos)方法

获取 pos 位置的元素

🐬7、set(int pos, int value)方法

给 pos 位置的元素设为 value

🐬8、remove(int toRemove)方法

删除第一次出现的关键字 key

🐬9、size()方法

获取顺序表长度

🐬10、clear()方法

清空顺序表

🐬11、完整代码

Ilist接口

package List;public interface IList {void add(int data);void add(int pos, int data);boolean contains(int toFind);int indexOf(int toFind);int get(int pos);void set(int pos, int value);void remove(int toRemove);int size();void clear();void display();
}

MyArrayList类

import List.EmptyTable;
import List.IList;
import List.Illegality;import java.nio.channels.ScatteringByteChannel;
import java.util.Arrays;public class MyArrayList implements IList {public int[] arr;public int usedsize;public static final int DEFAULT_SIZE = 10;public MyArrayList(){this.arr = new int[DEFAULT_SIZE];}@Overridepublic void display() {for (int i = 0; i < this.usedsize; i++) {System.out.print(arr[i]+" ");}System.out.println();}@Overridepublic void add(int data) {if(isFull()){Expansion();}this.arr[this.usedsize] = data;this.usedsize++;}public boolean isFull(){return this.usedsize == arr.length;}public void Expansion(){this.arr = Arrays.copyOf(this.arr, 2*this.arr.length);}@Overridepublic void add(int pos, int data) {try{check1(pos);if(isFull()){Expansion();}int right = this.usedsize;while(pos < right){arr[right] = arr[--right];}this.arr[pos] = data;this.usedsize++;}catch(Illegality e){e.printStackTrace();}}public void check1(int pos) throws Illegality{if( pos < 0 || pos > this.usedsize){throw new Illegality("pos不合法");}}@Overridepublic boolean contains(int toFind) {for (int i = 0; i < this.usedsize; i++) {if(this.arr[i] == toFind){return true;}}return false;}@Overridepublic int indexOf(int toFind) {for (int i = 0; i < this.usedsize; i++) {if(this.arr[i] == toFind){return i;}}return -1;}@Overridepublic int get(int pos) {try{empty();check2(pos);return this.arr[pos];}catch (Illegality e){e.printStackTrace();}catch (EmptyTable e){e.printStackTrace();}return -1;}public void check2(int pos) throws Illegality{if(pos < 0 || pos >= this.usedsize){throw new Illegality("pos不合法");}}public void empty() throws EmptyTable {if(this.usedsize == 0){throw new EmptyTable("顺序表为空");}}@Overridepublic void set(int pos, int value) {try{empty();check2(pos);this.arr[pos] = value;}catch (Illegality e){e.printStackTrace();}catch (EmptyTable e){e.printStackTrace();}}@Overridepublic void remove(int toRemove) {try{empty();int pos = indexOf(toRemove);if(pos == -1){return;}for (int i = pos; i < this.usedsize ; i++) {arr[pos] = arr[++pos];}this.usedsize--;}catch (EmptyTable e){e.printStackTrace();}}@Overridepublic int size() {return this.usedsize;}@Overridepublic void clear() {this.usedsize = 0;}}

异常

package List;public class Illegality extends RuntimeException{public Illegality(String message){super(message);}
}

package List;public class EmptyTable extends RuntimeException{public EmptyTable(String message){super(message);}
}

主函数

public class Test {public static void main(String[] args) {MyArrayList myArrayList = new MyArrayList();}
}

📖四、ArrayList简介

在上面我们自己实现了一个顺序表MyArrayList,但是在Java中编译器自带了一个顺序表ArrayList类，它同样实现了List接口，虽然它和我们自己实现的顺序表大同小异，但是它还有一些地方需要注意。

ArrayList是以泛型方式实现的，使用时必须要先实例化
ArrayList实现了RandomAccess接口，表明ArrayList⽀持随机访问
ArrayList实现了Cloneable接口，表明ArrayList是可以clone的
ArrayList实现了Serializable接口，表明ArrayList是支持序列化的
和Vector不同，ArrayList不是线程安全的，在单线程下可以使用，在多线程中可以选择Vector或者 CopyOnWriteArrayList
ArrayList底层是⼀段连续的空间，并且可以动态扩容，是⼀个动态类型的顺序表