手动实现动态数组(java)
程序员文章站
2022-06-09 16:58:09
...
- 数据结构:线性表, 树, 图, 集合等;
- 线性表: 是包含n个相同元素的有限序列;
- 数组是一种:内存连续的线性表;
- 动态数组: 动态的扩容与缩容, (缩容没有实现);
//方法列表:
public int sise();
public boolean isEmpty();
public boolean contains(int element);
public void add(int element);
public void add(int index, int element);
public int get(int index);
public int set(int index, int element);
public int remove(int element);
public void removeOfIndex(int index);
public void printElements()
/**
* Author: Batac
* 动态数组:
* 数组: 是一种连续存储结构的线性表;
* 优点: 查询速度快, 根据地址直接查找到元素(寻址法);
* 缺点: 插入与删减元素速度差, 最差需要移动其他所有元素
*/
public class ArrayList {
//数组
private int[] elements;
//元素个数
private int size;
//容量
private static int CAPATICY = 10;
//没有找到指定元素
private static final int ELEMENT_NOT_FOND = -1;
/**
* 有参构造方法
* @param capaticy
*/
public ArrayList(int capaticy){
if (capaticy < CAPATICY)capaticy = CAPATICY;
elements = new int[capaticy];
}
/**
* 无参构造方法
*/
public ArrayList(){
this(CAPATICY);
}
/**
* 设置元素个数
* @return
*/
public int sise(){
return this.size;
}
/**
* 判断元素是否为空
* @return
*/
public boolean isEmpty(){
if (this.sise() > 0)return false;
return true;
}
/**
* 判断元素是否存在
* @param element
* @return
*/
public boolean contains(int element){
int index = indexOf(element);
if (index == ELEMENT_NOT_FOND)return false;
return true;
}
/**
* 添加元素
* @param element
*/
public void add(int element){
add(size,element);
}
/**
* 获取指定索引出元素
* @param index
* @return
*/
public int get(int index){
indexOutOfBoundsExceptioni(index);
return elements[index];
}
/**
* 设置元素到指定位置
* @param index
* @param element
* @return
*/
public int set(int index, int element){
indexOutOfBoundsExceptioni(index);
add(index,element);
return -1;
}
/**
* 添加元素到指定位置
* @param index
* @param element
*/
public void add(int index, int element){
changeCapaticy();//扩容或者缩容
indexOutOfBoundsExceptioni(index);//判断索引是否越界
for (int i=size;i>index;i--){
elements[i] = elements[i-1];
}
elements[index] = element;
size++;
}
/**
* size为0的时候,直接将所有索引清楚
*/
public void clear(){
size = 0;
//缩容
}
/**
* 删除元素
* @param element
* @return
*/
public int remove(int element){
//查找元素所在位置
int index = indexOf(element);
if (index == ELEMENT_NOT_FOND){
return ELEMENT_NOT_FOND;
}
//删除元素
removeOfIndex(index);
return index;
}
/**
* 获取元素索引
* @param element
* @return
*/
private int indexOf(int element){
for (int i=0;i<size;i++){
int ele = elements[i];
if (ele == element){
return i;
}
}
return ELEMENT_NOT_FOND;
}
/**
* 扩容获取缩容
*/
private void changeCapaticy(){
if (size+1 == CAPATICY){
CAPATICY += 10;
System.out.println("扩容:"+CAPATICY+",size:"+size);
}else{
return;
}
int[] temps = new int[CAPATICY];
for (int i=0;i<size;i++){
temps[i] = elements[i];
}
elements = temps;
}
/**
* 判断索引是否合法 -> 内部使用
* @param index
*/
private void indexOutOfBoundsExceptioni(int index){
if (index < 0 || index > size){
throw new IndexOutOfBoundsException("index:"+index+",Size:"+size);
}
}
/**
* 删除指定索引的元素
* @param index
*/
public void removeOfIndex(int index){
indexOutOfBoundsExceptioni(index);
for (int i=index;i<size;i++){
elements[i] = elements[i+1];
}
size--;
}
/**
* 打印内容
*/
public void printElements(){
String str = "[";
for (int i=0;i<size;i++){
// System.out.println(elements[i]+"");
if (i == size-1){
str += elements[i]+"";
}else{
str = str+elements[i]+",";
}
}
str += "]";
System.out.println(str);
}
}
上一篇: 原生js手动 实现下拉刷新
下一篇: 手动实现数组方法