欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

手动实现动态数组(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);
    }
}