欢迎各位点赞👍评论✍收藏⭐
目录
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 类 和 顺序表 的了解,具体还需宝子们去实践,如果觉得该博客对你有用的话,希望一键三连,点个关注不迷路,谢谢支持