文章目录
- ArrayList简介
- ArrayList模拟实现
- 打印顺序表
- 获取顺序表的长度
- 判断当前的顺序表是不是满的
- 判断当前顺序表是不是空的
- 数组扩容
- 新增元素,默认在数组最后新增
- 在指定pos位置新增元素
- 判定是否包含某个元素
- 查找某个元素对应的位置
- 获取指定pos位置的元素
- 将指定pos位置的元素替换成value
- 删除第一次出现的关键字key
- 清空顺序表
- 完整代码
ArrayList简介
ArrayList 类是一个可以动态修改的数组，与普通数组的区别就是它是没有固定大小的限制，我们可以添加或删除元素。ArrayList 继承了 AbstractList ，并实现了 List 接口。
简单来说ArrayList的底层就是一个动态的顺序表。
而顺序表的底层就是数组.
因此要模式实现ArrayList就相当于基于数组实现一些操作，例如增删查改等。
ArrayList模拟实现
public int[] elem;
public int usedSize;//记录有效数据的个数
//默认容量
private static final int DEFAULT_SIZE = 10;
public MyArraylist() {
this.elem = new int[DEFAULT_SIZE];
}
将数据放在elem这个数组中，usedSize用于计算有效数据的个数，DEFAULT_SIZE是elem的默认容量。
打印顺序表
打印顺序表，我们可以使用循环对顺序表中的数据进行打印。
/**
* 打印顺序表:
* 根据usedSize判断即可
*/
public void display() {
for (int i = 0; i < this.usedSize; i++) {
System.out.print(this.elem[i] + " ");
}
System.out.println();
}
注意：顺序表中elem的有效数据是从[0,usedSize)，不能直接将整个数组打印完，我们存放的数据不一定能将数组放满。
获取顺序表的长度
此处的顺序表长度并不是底层数组的长度,而是数组种有效数据的个数.因此我们直接返回usedSize即可
public int size() {
return this.usedSize;
}
判断当前的顺序表是不是满的
要想判断当前的顺序表是不是满的,只需要看看usedSize(有效数据的个数)是不是大于等与底层数组的长度 如果是满的,返回true.如果不是满的,就返回false
/**
* 判断当前的顺序表是不是满的！
*/
public boolean isFull() {
if (size() >= this.elem.length) {
return true;
}
return false;
// 更简单的写法
// return size() >= this.elem.length;
}
判断当前顺序表是不是空的
判断当前顺序表是不是空的,只要看顺序表的有效数据是不是等于0即可
//判断顺序表是否为空
private boolean isEmpty() {
return size()==0;
}
数组扩容
在实现增加元素之前,我们要考虑一下,当数组满了之后,应该怎么做.顺序表不是链表,不用考虑满不满的这种情况,但顺序表不一样,数组长度是我们事先定好的.
如果数组长度设置的过大,而数据量很少,势必会造成空间的浪费.设置的过小,可能无法把所有元素存放进去.
为了避免这种情况,我们就可以使用动态顺序表.虽然听上去很高大上,但其实也就是加了一个动态扩容的过程
扩容也并不复杂,使用Arrays.copyOf方法即可
数组名 = Arrays.copyOf(要拷贝的数组,拷贝数组的长度);
在拷贝时,如果要拷贝数组的长度超过了原数组,那么超过原数组的部分,就是数组类型的默认值
新增元素,默认在数组最后新增
在解决数组满了这种情况之后,新增元素就很简单了.
一共分为两步:首先先判断数组是否满了,数组满了,就进行扩容.然后进行新增元素.如果没满,直接增加元素即可
/** 新增元素,默认在数组最后新增
* 判断顺序表是否满了
* 满了->扩容
* @param data
*/
public void add(int data) {
if (isFull()) {
//扩容
this.elem = Arrays.copyOf(this.elem,2*this.elem.length);
}
this.elem[usedSize] = data;
usedSize++;
}
在指定pos位置新增元素
在指定位置新增元素,首先要判断数组是否满了,如果满了要进行扩容.其次,pos位置是否合法,合法位置才能新增元素.
因为是从指定位置新增元素,如果这个位置不是在最后面,那么在新增元素时,首先要把pos及其以后位置的元素都往后移动一位,将pos位置空出来,这样才能将元素放进去
public void add(int pos, int data) {
if(isFull()){
this.elem = Arrays.copyOf(this.elem,2*this.elem.length);
}
if(checkPos(pos)){
for (int i = usedSize; i >= pos; i--) {
this.elem[i] = this.elem[i-1];
}
this.elem[pos] = data;
}
this.usedSize++;
}
// 检查pos位置是否合法
private boolean checkPos(int pos) {
if (pos < 0 || pos > size()) {
System.out.println("pos位置不合法");
return false;
}
return true;//合法
}
判定是否包含某个元素
直接对数组进行遍历然后比较即可,如果相等,直接返回true 如果遍历完没有与它相等的,就返回false
// 判定是否包含某个元素
public boolean contains(int toFind) {
for (int i = 0; i < this.usedSize; i++) {
if (toFind == this.elem[i]) {
return true;
}
}
return false;
}
查找某个元素对应的位置
与上面判断是否包含某个元素相同,遍历就行.
如果相等,返回当前的i值,如果不相等,就继续遍历.如果遍历完还没找到,就返回-1
// 查找某个元素对应的位置
public int indexOf(int toFind) {
for (int i = 0; i < this.usedSize; i++) {
if (toFind == this.elem[i]) {
return i;
}
}
return -1;
}
获取指定pos位置的元素
先检查顺序表是否为空,如果是空的.直接返回-1.如果不为空,再检查pos位置是否合法.
用自定义异常解决了顺序表为空这种情况,处理方法不一,合理即可
// 获取 pos 位置的元素
public int get(int pos) {
if(isEmpty()){
throw new EmptyException("顺序表为空!");
}
if(checkPos(pos)){
return this.elem[pos];
}
return -1;
}
将指定pos位置的元素替换成value
先判断顺序表是否为空,在判断pos位置是否合法.满足即可将pos位置的值更新为value
// 给 pos 位置的元素设为【更新为】 value
public void set(int pos, int value) {
if(isEmpty()){
throw new EmptyException("顺序表为空!");
}
if(pos < 0 || pos > size()){
System.out.println("pos位置不合法");
return;
}
this.elem[pos] = value;
}
删除第一次出现的关键字key
先判断顺序表是否为空,是空直接返回
然后判断顺序表中是否存在key,如果存在key,直接让key所在的位置的后面元素,一个一个往前覆盖,如果不存在,直接返回即可
public void remove(int key) {
if(isEmpty()){
throw new EmptyException("顺序表为空!");
}
if(contains(key)) {
int ret = indexOf(key);
for (int i = ret; i < usedSize; i++) {
this.elem[i] = this.elem[i+1];
}
}
this.usedSize--;
}
清空顺序表
public void clear() {
this.usedSize = 0;
}
这里的清空并不是真的清空,而是下次增加元素时,会把之前有的元素覆盖掉.如果不覆盖,那么原来的数据还是存在数组中的
如果想要彻底清空顺序表,就需要使用循环,将数组一个一个置为0
完整代码
主要部分:
import java.util.Arrays;
public class MyArrayList {
public int[] elem;
public int usedSize;//0//默认容量
private static final int DEFAULT_SIZE = 10;
public MyArrayList() {
this.elem = new int[DEFAULT_SIZE];
}
/**
* 打印顺序表:
* 根据usedSize判断即可
*/
public void display() {
for (int i = 0; i < this.usedSize; i++) {
System.out.print(this.elem[i] + " ");
}
System.out.println();
}
/** 新增元素,默认在数组最后新增
* 判断顺序表是否满了
* 满了->扩容
* @param data
*/
public void add(int data) {
if (isFull()) {
//扩容
this.elem = Arrays.copyOf(this.elem,2*this.elem.length);
}
this.elem[usedSize] = data;
usedSize++;
}
/**
* 判断当前的顺序表是不是满的！
* @return true:满 false代表空
*/
public boolean isFull() {
// if (size() >= this.elem.length) {
// return true;
// }
// return false;
return size() >= this.elem.length;
}
private boolean checkPos(int pos) {
if (pos < 0 || pos > size()) {
System.out.println("pos位置不合法");
return false;
}
return true;//合法
}
/** 在 pos 位置新增元素
* 方法：将pos位置的元素向后移动
* 情况：
* pos位置不合法
* 不能间隔
* @param pos
* @param data
*
*/
public void add(int pos, int data) {
if(isFull()){
this.elem = Arrays.copyOf(this.elem,2*this.elem.length);
}
if(checkPos(pos)){
for (int i = usedSize; i >= pos; i--) {
this.elem[i] = this.elem[i-1];
}
this.elem[pos] = data;
}
this.usedSize++;
}
// 判定是否包含某个元素
public boolean contains(int toFind) {
for (int i = 0; i < this.usedSize; i++) {
if (toFind == this.elem[i]) {
return true;
} else {
continue;
}
}
return false;
}
// 查找某个元素对应的位置
public int indexOf(int toFind) {
for (int i = 0; i < this.usedSize; i++) {
if (toFind == this.elem[i]) {
return i;
}
}
return -1;
}
// 获取 pos 位置的元素
public int get(int pos) {
if(isEmpty()){
throw new EmptyException("顺序表为空!");
}
if(checkPos(pos)){
return this.elem[pos];
}
return -1;
}
//判断顺序表是否为空
private boolean isEmpty() {
return size()==0;
}
// 给 pos 位置的元素设为【更新为】 value
public void set(int pos, int value) {
if(isEmpty()){
throw new EmptyException("顺序表为空!");
}
if(pos < 0 || pos > size()){
System.out.println("pos位置不合法");
return;
}
this.elem[pos] = value;
}
/**
* 删除第一次出现的关键字key
* @param key
*/
public void remove(int key) {
if(isEmpty()){
throw new EmptyException("顺序表为空!");
}
if(contains(key)) {
int ret = indexOf(key);
for (int i = ret; i < usedSize; i++) {
this.elem[i] = this.elem[i+1];
}
}
this.usedSize--;
}
// 获取顺序表长度
public int size() {
return this.usedSize;
}
// 清空顺序表
public void clear() {
this.usedSize = 0;
}
}
自定义异常部分
public class EmptyException extends RuntimeException{
public EmptyException() {
}
public EmptyException(String message) {
super(message);
}
}
