Java顺序表
前言：
接下来会进行持续更新关于Java数据结构的知识，那么接下来就让我们来进入到数据结构之线性表的世界中吧
一、线性表
线性表是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表有：顺序表、链表、栈、队列
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储
比如我们说的顺序表和链表两者就对应上述的储存方式。
二、顺序表
1.定义
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改
2.特点
顺序表的底层其实就是数组， 但是实际上是数组的超级版本；
顺序表支持动态扩容，可根据元素数量自动调整存储空间，
顺序表封装了对元素的操作逻辑（如插入时的移位、边界检查等）
这些更符合面向对象的思维。
三、ArrayList的具体实现
我们以整数型进行举例，ArrayList也就是对于数据元素进行增删改查，所以需要一些的方法来进行对于顺序表的操作，这个时候我们可以用接口来实现这些方法的定义与声明
1.接口方法的实现：
所以我们对于顺序表有以下的基本操作：
- 新增元素
- 在指定位置进行新增元素
- 判断元素是否存在
- 查找某元素的位置
- 获取指定位置元素
- 将指定元素进行修改新值
- 删除第一次出现元素
- 获取顺序表长度
- 清空顺序表
- 打印顺序表
那么首先我们需要定义接口Ilist：
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();
}
那么我们还需要再定义一个实现顺序表的类，类名MyArrayList：
public class MyArrayList implements Ilist{
public int[] array;//数组
public int usedSize;//下标长度，默认为0
public MyArrayList() {
this.array = new int[10];//这里进行构造方法的初始化的赋值，我们示例一个容量为10的数组大小
}
//为什么不对于usedSize进行初始化？
//因为其成员变量的默认值就是0
}
2.插入方法
插入操作算是顺序表中复杂的操作之一，因为需要保证物理地址的连续性。
1.新增元素
是从当前数组的默认最后一位进行插入新增元素的操作，那么也就是相当于创建数组
@Override
public void add(int data) {
this.array[this.usedSize] = data;
this.usedSize++;
}
还要注意一点，如果现在数组的状态是满的，应该判断数组是否为满,，
数组的自身长度等于给定长度，那么即是满的
public boolean isFull(){
return this.array.length == useSide;
}
既然满了，那么我们还需要对其进行扩容处理
private void grow(){//进行2倍扩容处理
this.array = Arrays.copyOf(this.array,this.array.length*2);
}
//直接使用Arrays中的copyof的方法，进行扩大并指定重新生成新数组的方式
这一步的最终代码：
public void add(int data) {
if (isFull()){
grow();
}
this.array[this.useSide] = data;
this.usedSize++;
}
测试代码：
public class Main {
public static void main(String[] args) {
MyArrayList myArrayList = new MyArrayList();
myArrayList.add(2);
myArrayList.add(0);
myArrayList.add(2);
myArrayList.add(5);
myArrayList.add(0);
myArrayList.add(8);
myArrayList.add(1);
myArrayList.add(0);
myArrayList.add(23);
myArrayList.add(05);
myArrayList.display();
System.out.println("=======");
myArrayList.add(24);
myArrayList.add(00);
myArrayList.display();
}
}
2.在指定位置进行新增元素
要在指定位置进行插入元素，那么就要判断插入的下标位置的是否合法，依旧还要判断数组的容量；
示例：
将56插入到指定位置：下标为1的位置
思路：需要把指定位置的后面的元素整体进行移动为1个元素单位的长度，用循环进行遍历，从而使其移动
核心代码：
public void add(int pos, int data) {
for (int i = useSide-1; i >= pos ; i--) {
this.array[i+1] = this.array[i];
}
array[pos] = data;
this.usedSize++;
}
那么我们还需要对其进行的容量和下标位置合法性的进行判断
前文已经提到如何判断容量和扩容，继续使用即可
在数组中我们可以看到，usedSize表示长度，也就是扩大一个元素数组的下标，所以说这时我们可以进行位置的插入
如果要对于下标为5的位置进行插入，会造成地址不连续
注意：在数据结构中，规定插入数据的位置，前驱必须存在
通俗的说：插入的位置前一个不能是空的
//对于下标的合法判断
public void checkPos(int pos) throws PosIllegal {
if (pos < 0 || pos > usedSize){
throw new PosIllegal("pos位置不合法");
}
}
既然会抛出异常，那么我们就需要定义一个异常类，来存放异常的；
//PosIllegal
public class PosIllegal extends RuntimeException{
public PosIllegal() {
}
public PosIllegal(String message) {
super(message);
}
}
这个部分的最终代码：
@Override
public void add(int pos, int data) {
try {
checkPos(pos);
if (isFull()){
grow();
}
for (int i = usedSize-1; i >= pos ; i--) {
this.array[i+1] = this.array[i];
}
array[pos] = data;
this.usedSize++;
}catch (PosIllegal e){
System.out.println("元素插入的pos位置不合法");
e.printStackTrace();
}
}
测试代码：
public class Main {
public static void main(String[] args) {
MyArrayList myArrayList = new MyArrayList();
System.out.println("=======");
myArrayList.add(1,20);
myArrayList.display();
System.out.println();
myArrayList.add(-1,20);
}
}
3.对元素的判断与查找
思路：用循环遍历进行判断是否相等就可以（不需要过多的讲解）
最终代码：
@Override
public boolean contains(int toFind) {
for (int i = 0; i < usedSize; i++) {
if (array[i] == toFind){
return true;
}
}
return false;
}
@Override
public int indexOf(int toFind) {
for (int i = 0; i < usedSize; i++) {
if (array[i] == toFind){
return i;
}
}
return -1;
}
4.元素获取与修改
获取指定位置的元素，我们需要判断下标是否合法，
但是我们可以看到在进行获取的时候，如果下标等于数组的长度，是无法获取元素的，所以在判断下标时要注意这个条件
下标是否合法的代码：
public void checkPos2(int pos) throws PosIllegal {
if (pos < 0 || pos >= usedSize){
throw new PosIllegal("pos位置不合法");
}
}
其实到了这里，还是远远不够的，如果当这个数组中全是空的话，也需要进行判断是否为空
思路：我们可以令长度等于0时，进行判断
private boolean isEmpty(){
return usedSize == 0;//如果为真，则返回true，反之则是false
}
但是我们不能直接进行判断，因为如果为空的话，表示出现了错误，我们可以将其封装为异常的方法，让为空的时候直接抛出异常
public void checkEmpty(){
if (isEmpty()){
throw new EmptyException("顺序表为空！");
}
}
做好上述的前期准备工作之后，我们可以写到最终的代码：
@Override
public int get(int pos) {
try {
checkEmpty();
checkPos2(pos);
return array[pos];
}catch (PosIllegal e){
e.printStackTrace();
}catch (EmptyException e){
e.printStackTrace();
}
return -1;
}
将指定位置的元素进行修改
与上述同样的合法下标为usedSize时，是会进行报错，并且要保持数组不能为空，所以思路与上述完全一样
代码：
@Override
public void set(int pos, int value) {
try {
checkEmpty();
checkPos2(pos);
array[pos] = value;
}catch (PosIllegal e){
e.printStackTrace();
}catch (EmptyException e){
e.printStackTrace();
}
}
5.删除首次出现元素
删除的思想：由于数组的整体一般是连续的，我们用删除元素的之后的元素整体向前进行覆盖，这样我们就可以进行删除元素
@Override
public void remove(int toRemove) {
try {
checkEmpty();
int pos = indexOf(toRemove);
if (pos == -1){
return;
}
for (int i = pos; i < usedSize-1; i++) {
//usedSize-1是为了防止数组移动在进行出现报错
array[i] = array[i+1];
}
}catch (PosIllegal e){
e.printStackTrace();
}catch (EmptyException e){
e.printStackTrace();
}
this.usedSize--;//删除后进行长度变化
}
测试代码：
System.out.println(myArrayList.contains(23));
System.out.println(myArrayList.indexOf(23));
System.out.println("=======");
System.out.println(myArrayList.get(13));
System.out.println(myArrayList.get(10));
myArrayList.set(10,55);
myArrayList.display();
myArrayList.remove(24);
myArrayList.display();
6.顺序表的长度
返回顺序表的长度：直接进行return即可
顺序表的清空：直接将数组的实际长度进行赋值为0；但是对于引用类型的我们需要将每个数组的进行赋值为null才可以，防止内存泄漏。
public void clear() {
this.usedSize = 0 ;
// for (int i = 0; i < this.usedSize; i++) {
// array[i] = null;
// }
}
3.顺序表的核心代码：
package IList;
import IList.exception.EmptyException;
import IList.exception.PosIllegal;
import java.util.Arrays;
public class MyArrayList implements IList {
public int[] array;//数组
public int usedSize;//下标长度，默认为0
public MyArrayList() {
this.array = new int[10];
}
@Override
public void add(int data) {
if (isFull()){
grow();
}
this.array[this.usedSize] = data;
this.usedSize++;
}
public boolean isFull(){//判断数组是否为满
return this.array.length == usedSize;
}
private void grow(){//进行2倍扩容处理
this.array = Arrays.copyOf(this.array,this.array.length*2);
}
@Override
public void add(int pos, int data) {
try {
checkPos(pos);
if (isFull()){
grow();
}
for (int i = usedSize-1; i >= pos ; i--) {
this.array[i+1] = this.array[i];
}
array[pos] = data;
this.usedSize++;
}catch (PosIllegal e){
System.out.println("元素插入的pos位置不合法");
e.printStackTrace();
}
}
public void checkPos(int pos) throws PosIllegal {
if (pos < 0 || pos > usedSize){
throw new PosIllegal("pos位置不合法");
}
}
@Override
public boolean contains(int toFind) {
for (int i = 0; i < usedSize; i++) {
if (array[i] == toFind){
return true;
}
}
return false;
}
@Override
public int indexOf(int toFind) {
for (int i = 0; i < usedSize; i++) {
if (array[i] == toFind){
return i;
}
}
return -1;
}
public void checkPos2(int pos) throws PosIllegal {
if (pos < 0 || pos >= usedSize){
throw new PosIllegal("pos位置不合法");
}
}
private boolean isEmpty(){
return usedSize == 0;
}
public void checkEmpty() throws EmptyException {
if (isEmpty()){
throw new EmptyException("顺序表为空！");
}
}
@Override
public int get(int pos) {
try {
checkEmpty();
checkPos2(pos);
return array[pos];
}catch (PosIllegal e){
e.printStackTrace();
}catch (EmptyException e){
e.printStackTrace();
}
return -1;
}
@Override
public void set(int pos, int value) {
try {
checkEmpty();
checkPos2(pos);
array[pos] = value;
}catch (PosIllegal e){
e.printStackTrace();
}catch (EmptyException e){
e.printStackTrace();
}
}
@Override
public void remove(int toRemove) {
try {
checkEmpty();
int pos = indexOf(toRemove);
if (pos == -1){
return;
}
for (int i = pos; i < usedSize; i++) {
array[i] = array[i+1];
}
}catch (PosIllegal e){
e.printStackTrace();
}catch (EmptyException e){
e.printStackTrace();
}
this.usedSize--;
}
@Override
public int size() {
return this.usedSize;
}
@Override
public void clear() {
// for (int i = 0; i < this.usedSize; i++) {
// array[i] = 0;
// }
this.usedSize = 0 ;
// for (int i = 0; i < this.usedSize; i++) {
// array[i] = null;
// }
}
@Override
public void display() {
for (int i = 0; i < this.usedSize; i++) {
System.out.print(this.array[i] + " ");
}
System.out.println();
}
}
总结：
这篇文章代表了开始正式向数据结构进军，数据结构是评判程序员的重要标准，也是每一位程序员的必经之路，希望我们能一直前进，加油！这期的内容就先到这里了，如果有什么内容上的不足，欢迎大家在评论区中指出！