【Java 数据结构】ArrayList 类 与 模拟实现顺序表
🔥博客主页🔥：【 坊钰_CSDN博客 】
欢迎各位点赞👍评论✍收藏⭐
目录
1. 线性表
2. ArrayList 类
3. ArrayList 的使用
3.1 ArrayList 的构造
3.2 ArrayList 的常用方法
3.3 ArrayList 的遍历
3.4 ArrayList 的扩容机制
4. 模拟实现顺序表
4.1 建立基本框架
4.2 求数组元素的个数
4.3 打印
4.4 扩容
4.5 尾插
4.6 头插
4.7 指定位置 pos 插入 val
4.8 删除第一个 key 的元素
4.9 删除全部 key 的元素
4.10 是否包含 key 的元素
4.11 把 key 的元素修改为 val
5. 全部码源
5.1 顺序表结构
5.2 测试代码
6. 小结
1. 线性表
线性表简单来说就是一条线性储存结构，线性表是一种很实用的数据结构，常见的线性表有：数组、链表、栈、队列...
2. ArrayList 类
在数据结构中，ArrayList 是一个类，实现了 List 接口，ArrayList 类也继承了许多接口
- ArrayList 实现了 RandomAccess 接口，表明 ArrayList 支持随机访问
- ArrayList 实现了 Cloneable 接口，表明 ArrayList 支持 clone 克隆的
- ArrayList 实现了 Serializable 接口，表明 ArrayList 支持序列化的
- ArrayList 底层是一段连续的空间，并且可以动态扩容，是动态类型的顺序表
3. ArrayList 的使用
3.1 ArrayList 的构造
ArrayList 有三种构造方法
ArrayList() //空构造器，未指定大小容量
ArrayList(int capacity) //创建指定大小的顺序表
ArrayList(Collection<? extends E>) //用其他顺序表创建一个新的顺序表(和旧顺序表元素一致)import java.util.ArrayList;
import java.util.List;
public class Test {
public static void main(String[] args) {
//建立顺序表，未指定大小，默认大小为 10
List<Integer> list1 = new ArrayList<>();
//建立大小为 20 的顺序表
List<Integer> list2 = new ArrayList<>(20);
//以 list2 的标准来建立顺序表
List<Integer> list3 = new ArrayList<>(list2);
}
}3.2 ArrayList 的常用方法
ArrayList 中有很多方法，我们只需了解几种常用的就行
这些方法在使用中直接使用就行哦
3.3 ArrayList 的遍历
ArrayList 的遍历有三种方法
- for 循环遍历
- for - each 循环遍历
- 迭代器遍历
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
public class Test {
public static void main(String[] args) {
//建立顺序表，未指定大小，默认大小为 10
List<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.add(5);
//for 循环遍历
for (int i = 0; i < list.size(); i++) {
System.out.print(list.get(i) + " ");
}
System.out.println();
//for-each 循环遍历
for(Integer x : list)
System.out.print(x + " ");
System.out.println();
//迭代器遍历
Iterator<Integer> it = list.listIterator();
while (it.hasNext()) {
System.out.print(it.next() + " ");
}
System.out.println();
}
}3.4 ArrayList 的扩容机制
有两个机制，同学们记住就行
- ArrayList 创建时，如果不指定大小，默认大小为 10
- 如果 ArrayList 满了，会自动按 1.5 倍扩容
4. 模拟实现顺序表
让我们自己写一个顺序表，实现同样的增删查改等....操作
4.1 建立基本框架
public class MyArrayList {
//创建数组作为顺序表
private int[] array;
//数组中元素的个数
private int useSize;
MyArrayList() {
//设置初始容量
array = new int[10];
}
}4.2 求数组元素的个数
/*
* 求数组元素的个数
* */
public int size() {
return this.useSize;
}4.3 打印
/*
* 打印
* */
public void print() {
for (int i = 0; i < useSize; i++) {
System.out.print(array[i] + " ");
}
System.out.println();
}4.4 扩容
/*
* 扩容
* */
private void expanCapacity() {
this.array = Arrays.copyOf(array,array.length * 2);
}4.5 尾插
/*
* 尾插
* */
public void addLast(int val) {
if (useSize == array.length) {
expanCapacity();
}
array[useSize] = val;
useSize++;
}4.6 头插
/*
* 头插
* */
public void addFont(int val) {
if (useSize == array.length) {
expanCapacity();
}
int cur = useSize;
int i = cur;
for (; i > 0 ; i--) {
array[i] = array[i - 1];
}
array[i] = val;
useSize++;
}4.7 指定位置 pos 插入 val
/*
* 在指定位置 pos 插入 val
* */
public void addPos(int pos,int val) {
if (pos < 0 || pos > useSize) {
System.out.println("Pos is false!");
return;
}
if (useSize == array.length) {
expanCapacity();
}
if (pos == 0) {
addFont(val);
return;
}
if (pos == useSize) {
addLast(val);
return;
}
int cur = useSize;
int i = cur;
for (; i > pos; i--) {
array[i] = array[i - 1];
}
array[i] = val;
useSize++;
}4.8 删除第一个 key 的元素
/*
* 删除第一个 key 的元素
* */
public void remove(int key) {
if (!contain(key)) {
System.out.println("Key is no!");
return;
}
int cur = 0;
for (int i = 0; i < useSize; i++) {
if (array[i] == key) {
cur = i;
break;
}
}
for (int j = cur; j < useSize - 1; j++) {
array[j] = array[j + 1];
}
useSize--;
}4.9 删除全部 key 的元素
/*
* 删除全部 key 的元素
* */
public void removeAll(int key) {
if (!contain(key)) {
System.out.println("Key is no!");
}
for (int i = 0; i < useSize; i++) {
if (key == array[i]) {
for (int j = i; j < useSize - 1; j++) {
array[j] = array[j + 1];
}
useSize--;
i--;
}
}
}4.10 是否包含 key 的元素
/*
* 是否包含 key 的元素
* */
public boolean contain(int key) {
for (int i = 0; i < useSize; i++) {
if (key == array[i]) {
return true;
}
}
return false;
}4.11 把 key 的元素修改为 val
/*
* 把 key 的元素修改为 val
* */
public void setVal(int key,int val) {
if (!contain(key)) {
System.out.println("Key is no!");
}
for (int i = 0; i < useSize; i++) {
if (array[i] == key) {
array[i] = val;
}
}
}5. 全部码源
5.1 顺序表结构
package deom2;
import java.util.Arrays;
public class MyArrayList {
//创建数组作为顺序表
private int[] array;
//数组中元素的个数
private int useSize;
MyArrayList() {
//设置初始容量
array = new int[10];
}
/*
* 打印
* */
public void print() {
for (int i = 0; i < useSize; i++) {
System.out.print(array[i] + " ");
}
System.out.println();
}
/*
* 求数组元素的个数
* */
public int size() {
return this.useSize;
}
/*
* 扩容
* */
private void expanCapacity() {
this.array = Arrays.copyOf(array,array.length * 2);
}
/*
* 尾插
* */
public void addLast(int val) {
if (useSize == array.length) {
expanCapacity();
}
array[useSize] = val;
useSize++;
}
/*
* 头插
* */
public void addFont(int val) {
if (useSize == array.length) {
expanCapacity();
}
int cur = useSize;
int i = cur;
for (; i > 0 ; i--) {
array[i] = array[i - 1];
}
array[i] = val;
useSize++;
}
/*
* 在指定位置 pos 插入 val
* */
public void addPos(int pos,int val) {
if (pos < 0 || pos > useSize) {
System.out.println("Pos is false!");
return;
}
if (useSize == array.length) {
expanCapacity();
}
if (pos == 0) {
addFont(val);
return;
}
if (pos == useSize) {
addLast(val);
return;
}
int cur = useSize;
int i = cur;
for (; i > pos; i--) {
array[i] = array[i - 1];
}
array[i] = val;
useSize++;
}
/*
* 删除第一个 key 的元素
* */
public void remove(int key) {
if (!contain(key)) {
System.out.println("Key is no!");
return;
}
int cur = 0;
for (int i = 0; i < useSize; i++) {
if (array[i] == key) {
cur = i;
break;
}
}
for (int j = cur; j < useSize - 1; j++) {
array[j] = array[j + 1];
}
useSize--;
}
/*
* 删除全部 key 的元素
* */
public void removeAll(int key) {
if (!contain(key)) {
System.out.println("Key is no!");
}
for (int i = 0; i < useSize; i++) {
if (key == array[i]) {
for (int j = i; j < useSize - 1; j++) {
array[j] = array[j + 1];
}
useSize--;
i--;
}
}
}
/*
* 是否包含 key 的元素
* */
public boolean contain(int key) {
for (int i = 0; i < useSize; i++) {
if (key == array[i]) {
return true;
}
}
return false;
}
/*
* 把 key 的元素修改为 val
* */
public void setVal(int key,int val) {
if (!contain(key)) {
System.out.println("Key is no!");
}
for (int i = 0; i < useSize; i++) {
if (array[i] == key) {
array[i] = val;
}
}
}
}
5.2 测试代码
package deom2;
import java.util.Arrays;
public class Test {
public static void main(String[] args) {
MyArrayList myArrayList = new MyArrayList();
myArrayList.addLast(1);
myArrayList.addLast(2);
myArrayList.addLast(3);
myArrayList.addLast(4);
myArrayList.addLast(5);
myArrayList.print();
myArrayList.addFont(5);
myArrayList.addFont(4);
myArrayList.addFont(3);
myArrayList.addFont(2);
myArrayList.addFont(1);
myArrayList.print();
myArrayList.addPos(3,9);
myArrayList.addPos(0,9);
myArrayList.addPos(12,9);
myArrayList.addFont(9);
myArrayList.addFont(9);
myArrayList.addFont(9);
myArrayList.print();
myArrayList.remove(5);
myArrayList.print();
myArrayList.removeAll(9);
myArrayList.print();
myArrayList.addPos(3,9);
myArrayList.addPos(3,9);
myArrayList.addPos(3,9);
myArrayList.addFont(9);
myArrayList.addLast(9);
myArrayList.print();
myArrayList.setVal(9,8);
myArrayList.print();
}
}
测试图片
6. 小结
以上就是对 ArrayList 类 和 顺序表 的了解，具体还需宝子们去实践，如果觉得该博客对你有用的话，希望一键三连，点个关注不迷路，谢谢支持