【数据结构】Java -- 顺序表(详解)
//对数组进行各式各样的操作
import java.util.Arrays;
public class MyArrayList implements IList {
//首先，MyArrayList 底层操纵的是一个数组
//需要定义一个 数组
public int[] elem;
// usedSize 相当于数组里面 有效元素的个数
// 当数组里面增加元素或者减少元素的时候，usedSize 加或减
public int usedSize;
//默认的数组容量
public static final int DEFAULT_CAPACITY = 5;
public MyArrayList() {
//在构造方法里面可以初始化 数组
this.elem = new int[DEFAULT_CAPACITY];
}
//接下来可以对数组进行增删查改的操作
// 可以把这些操作全部放在接口里面
/*
打印顺序表当中所有的元素
*/
@Override
public void display() {
//可以通过 usedSize 来确定 数组里面元素的个数
for (int i = 0; i < usedSize; i++) {
System.out.print(elem[i] + " ");
}
System.out.println();
}
/**
* 添加元素，默认添加到数组的最后位置
*
* @param data 元素
*/
@Override
public void add(int data) {
//1.首先在 添加元素之前 要对数组里面的元素个数进行判断
// 如果数组满了，要对数组进行扩容
if (isFull()) {
//满了
// 返回值还是一个 int 类型的数组
// 相当于 对 elem 数组进行操作
// 拷贝完成之后 让elem指向新的数组
elem = Arrays.copyOf(elem, 2 * elem.length);
}
//usedSize 位置放元素
elem[usedSize] = data;
usedSize++;
}
// 判断数组是否满了
@Override
public boolean isFull() {
// 如何判断呢？
// 这时需要对 usedSize 进行判断
return usedSize == elem.length;
}
/**
* 给 pos 位置添加一个元素
*
* @param pos //
* @param data
*/
@Override
public void add(int pos, int data) {
//1.首先还要进行 边界条件的判断
//pos位置判断
checkPosOfAdd(pos);
//2.满的话
if (isFull()) {
elem = Arrays.copyOf(elem, 2 * elem.length);
}
// 2.比如向 下标为1的位置添加元素
// 不可以先挪 原本 下标为 1 上的元素
//需要从 最后一个 存储 数据元素 的位置向后挪
//相当于 [i + 1] = [i] i--
for (int i = usedSize - 1; i >= pos; i--) {
elem[i + 1] = elem[i];
}
elem[pos] = data;
usedSize++;
}
//对 pos 位置进行判断
private void checkPosOfAdd(int pos){
if (pos < 0 || pos > usedSize){
//说明pos位置不合法
throw new PosException("pos位置为：" + pos);
}
}
/**
* 查找当前元素是否存在
* @param toFind
* @return
*/
@Override
public boolean contains(int toFind) {
for (int i = 0; i < usedSize; i++) {
if (elem[i] == toFind){
return true;
}
}
return false;
}
/**
* 找当前元素 下标
* @param toFind
* @return
*/
@Override
public int indexOf(int toFind) {
for (int i = 0; i < usedSize; i++) {
if (elem[i] == toFind){
return i;
}
}
return -1;
}
/**
* 获取 pos 位置的值
* @param pos
* @return
*/
@Override
public int get(int pos) {
//不合法怎么办？
checkPosOfGet(pos);
//合法，为空怎么办？
if (isEmpty()){
//抛一个 空的异常
throw new EmptyException("顺序表为空！！！");
//也可以返回一个 -1
}
return elem[pos];
}
@Override
public boolean isEmpty() {
return usedSize == 0;
}
private void checkPosOfGet(int pos){
if (pos < 0 || pos >= usedSize){
//说明pos位置不合法
throw new PosException("pos位置不合法：" + pos);
}
}
/**
* 更新 pos 位置的值
* @param pos
* @param value
*/
@Override
public void set(int pos, int value) {
//首先 pos 要合法
checkPosOfGet(pos);
//其次判断是否为空
if (isEmpty()){
//抛一个 空的异常
throw new EmptyException("顺序表为空！！！");
//也可以返回一个 -1
}
elem[pos] = value;
}
/**
* 删除 toRemove 这个数字
* @param toRemove
*/
@Override
public void remove(int toRemove) {
//首先 删除这个数字 要找到 这个数字的下标
//如果为空 不能删
if (isEmpty()){
//抛一个 空的异常
throw new EmptyException("顺序表为空！！！");
//也可以返回一个 -1
}
int index = indexOf(toRemove);
//这个时候需要 一个一个数向前覆盖
for (int i = index; i < usedSize - 1; i++) {
elem[i] = elem[i + 1];
}
usedSize--;
}
@Override
public int size() {
return this.usedSize;
}
/**
* 清空顺序表 防止内存泄漏
*/
@Override
public void clear() {
//如果数组里面放的是引用类型
//说明每个 元素存的是 地址
//现在里面放的是 int类型
usedSize = 0;
}
}