数据结构 之 顺序表 ArrayList （Java）
数据结构 之 顺序表 ArrayList （Java）
在该篇文章中，大概介绍了顺序表，以及模拟实现了顺序表中的常用方法；
在了解顺序表之前，我们需要去了解线性表：
1.线性表：
线性表是一种广泛应用的数据结构，是一个聚友n个相同特性的数据元素的有限序列；
常见的线性表有：顺序表（ArrayList），链表（LinkedList），栈（Stack），队列（Queue）...
线性表在逻辑上是线性结构，也就是一条直线，但是在物理结构上却不一定是连续的，线性表在存储数据时，通常以数组和链表的形式去存储。
2.顺序表
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储
ArrayList底层是一段连续的空间，并且可以动态扩容，是一个动态类型的顺序表
根据顺序表的源码可知：
1. ArrayList继承于AbstractList，并且ArrayList是以泛型的方式实现的，使用的时候必须要先实例化；
2. ArrayList实现了RandomAccess接口，表明ArrayList支持随机访问；
3. ArrayList实现了Cloneable接口，表明ArrayList是可以clone的；
4. ArrayList实现了Serializable接口，表明ArrayList是支持序列化的；
5. 和Vector不同，ArrayList不是线程安全的，在单线程下可以使用，在多线程中可以选择Vector或者 CopyOnWriteArrayList；
2.1 顺序表的使用：
2.1.1 构造方法：
首先我们要认识顺序表的构造方法，顺序表中一共有三个构造方法：
源码如下：
这是不带参数的构造方法：默认数组为空数组；
这是带一个参数的构造方法：将顺序表的容量大小置为参数大小
这是参数为Collection的构造方法：利用其他的Collection去构建ArrayList；
2.1.2 顺序表的常用方法：
通过观察源码，我们发现，ArrayList的方法非常多，但在接下来的介绍和模拟实现的过程中，我只会介绍和模拟最常见的方法；
首先我们先构建一个My_ArrayList类
< 1 > add 方法
add方法也就是我们常用的插入方法，源码对add方法进行了重载，在这里我们模拟实现add方法的其中一个重载方法。
模拟实现：
一般来说，在顺序表中插入元素，有两种插入方法，尾插和给定位置插入，（头插也就是给定位置为0的插入），由于顺序表是以数组的方式存储数据的，所以在插入之前，我们要判断一下，给定的位置是否合理，若不合理，则需要抛出异常，并且判断数组是否是满的，如果数组是满的，那我们就需要进行扩容；
大概的代码如下：
这是指定位置的add方法
指定位置的add方法写出来之后，那么头插和尾插就简单了；
头插即pos == 0， 尾插即pos == usedSize - 1；
< 2 > get方法：
get方法有一个参数pos，就是获取pos下标的元素，写法也十分简单：
在获取该下标的元素之前，我们同样要对该下标进行是否合法判断，若不合法则抛出异常，合法则返回该下标所对应的元素；
< 3 > set方法：
set方法有两个参数，一个是pos，也就是下标，另一个是value，是给定的值，作用是将pos位置的元素更新为value；
在更新数据之前，我们同样需要对pos位置进行合法性的判断，若不合法，则抛出异常，写法同样很简单：
< 4 > indexOf 方法：
该方法有一个参数toFind， 该方法的作用的找到toFind元素的下标并返回，若没有该元素则返回 -1；
< 5 > remove 方法：
remove方法有一个参数key， 作用是找到顺序表中的第一个key元素并将其删除；
在删除之前，我们需要判断顺序表是否为空，若为空，则抛出异常；
< 5 > contains 方法：
contains方法有一个参数toFind，作用是判断顺序表中是否包含toFind元素；
< 5 > clear 方法：
clear方法是将顺序表中的元素全部删除；
、
3. 模拟实现整体源码分享：
import java.util.Arrays;
public class MyArrayListIndexOutOfException extends RuntimeException{
public MyArrayListIndexOutOfException() {
super();
}
public MyArrayListIndexOutOfException(String str) {
super(str);
}
}
public class MyArrayListEmptyException extends RuntimeException{
public MyArrayListEmptyException() {
super();
}
public MyArrayListEmptyException(String str) {
super(str);
}
}
public class My_ArrayList {
public int[] elem;
public int usedSize;//0
//默认容量
private static final int DEFAULT_SIZE = 10;
public My_ArrayList() {
this.elem = new int[DEFAULT_SIZE];
}
/**
* 打印顺序表:
* 根据usedSize判断即可
*/
public void display() {
//usedSize==0
for (int i = 0; i < this.usedSize; i++) {
System.out.print(this.elem[i]+" ");
}
System.out.println();
}
// 新增元素,默认在数组最后新增
public void add(int data) {
//1、判断是否是满的，如果满的，那么进行扩容
if(isFull()) {
//扩容
this.elem = Arrays.copyOf(this.elem,2*this.elem.length);
}
//2、不满进行插入
this.elem[this.usedSize] = data;
this.usedSize++;
}
/**
* 判断当前的顺序表是不是满的！
* @return true:满 false代表空
*/
public boolean isFull() {
/*if(this.usedSize == this.elem.length) {
return true;
}
return false;*/
return this.usedSize == this.elem.length;
}
private boolean checkPosInAdd(int pos) {
if(pos < 0 || pos > this.usedSize) {
System.out.println("pos位置不合法");
return false;
}
return true;//合法
}
// 在 pos 位置新增元素
public void add(int pos, int data) {
//判断下标是否是合法的，若不合法，则抛出异常
if(!checkPosInAdd(pos)) {
throw new MyArrayListIndexOutOfException("添加方法的pos不合理！");
}
//判断是否是满的，若是满的，则进行扩容（此处为二倍扩容）
if (isFull()) {
this.elem = Arrays.copyOf(this.elem,2*this.elem.length);
}
//挪数据，将pos位置及pos位置之前的数据向后移动，并将pos位置空出来存放data参数
for (int i = this.usedSize-1; i >= pos ; i--) {
this.elem[i+1] = this.elem[i];
}
//挪完了数据，在pos位置存放data参数
this.elem[pos] = data;
this.usedSize++;
}
// 判定是否包含某个元素
public boolean contains(int toFind) {
for (int i = 0; i < this.usedSize; i++) { //遍历数组，寻找第一个个于toFind相同的元素
if(this.elem[i] == toFind) {
return true; //若找到了，则返回true
}
}
return false; //若没有找到，返回false
}
// 查找某个元素对应的位置
public int indexOf(int toFind) {
for (int i = 0; i < this.usedSize; i++) { //遍历整个数组，查找是否有该元素
if(this.elem[i] == toFind) {
return i; //若有则返回i
}
}
return -1; //若无则返回-1
}
private boolean checkPosInGet(int pos) {
if(pos < 0 || pos >= this.usedSize) {
System.out.println("pos位置不合法");
return false;
}
return true;//合法
}
// 获取 pos 位置的元素
public int get(int pos) {
if(!checkPosInGet(pos)) {
throw new MyArrayListIndexOutOfException("获取pos下标时，位置不合法");
}
//不用写判断空不空 没有问题的
// if(isEmpty()) {
// throw new MyArrayListEmptyException("获取元素的时候，顺序表为空！");
// }
return this.elem[pos];
}
private boolean isEmpty() {
return this.usedSize == 0;
}
// 给 pos 位置的元素设为【更新为】 value
public void set(int pos, int value) {
if(!checkPosInGet(pos)){
throw new MyArrayListIndexOutOfException("更新pos下标的元素，位置不合法");
}
//如果合法 ，那么其实不用判断顺序表为空的状态了
// if(isEmpty()) {
// throw new MyArrayListEmptyException("顺序表为空！");
// }
//顺序表为满的情况也可以更新
this.elem[pos] = value;
}
/**
* 删除第一次出现的关键字key
* @param key
*/
public void remove(int key) {
//判断顺序表是否为空，若为空，则抛出异常
if(isEmpty()) {
throw new MyArrayListEmptyException("顺序表为空，不能删除！");
}
//使用indexOf方法，找到key元素的下标
int index = indexOf(key);
//若没有key元素，则输出“不存在你要删除的数据”
if(index == -1) {
System.out.println("不存在你要删除的数据");
return;
}
//用key位置的后面的所有元素往前依次移动一次，覆盖掉key元素
for (int i = index; i < this.usedSize-1; i++) {
this.elem[i] = this.elem[i+1];
}
//删除完成，顺序表长度--
this.usedSize--;
// this.elem[usedSize] = null; 如果传入的参数是引用类型 这里需要置为空
}
// 获取顺序表长度
public int size() {
return this.usedSize;
}
// 清空顺序表
public void clear() {
/*
如果是引用数据类型 得一个一个置为空 这样做才是最合适的
for (int i = 0; i < this.usedSize; i++) {
this.elem[i] = null;
}
this.usedSize = 0;
*/
this.usedSize = 0;
}
}以上就是顺序表的全部内容
制作不易，三连支持谢谢！！！ 以上的模拟实现代码未必是最优解，仅代表本人的思路，望多多理解，谢谢！！ 最后送给大家一句话，同时也是对我自己的勉励： 不要因为没有掌声而放弃梦想！！！！！