【Java】动态数组(顺序表)

Java_0">Java实现一个可动态增长的数组

线性表

线性表 linear list 是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表:顺序表、链表、栈、队列、字符串…
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

顺序表

概念及结构

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
顺序表一般可以分为:

静态顺序表:使用定长数组存储。动态顺序表:使用动态开辟的数组存储。
静态顺序表适用于确定知道需要存多少数据的场景.

静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用.

接口实现

我们来实现一个动态顺序表. 以下是需要支持的接口.

public class SeqList { // 打印顺序表
	public void display() { }
	// 在 pos 位置新增元素
	public void add(int pos, int data) { }
	// 判定是否包含某个元素
	public boolean contains(int toFind) { return true; } // 查找某个元素对应的位置
	public int search(int toFind) { return -1; }
	// 获取 pos 位置的元素
	public int getPos(int pos) { return -1; }
	// 给 pos 位置的元素设为 value
	public void setPos(int pos, int value) { } //删除第一次出现的关键字key
	public void remove(int toRemove) { }
	// 获取顺序表长度
	public int size() { return 0; }
	// 清空顺序表
	public void clear() { }
}

实现动态数组的源码

public class MyArray {
    int num[];
    int size;

    public MyArray(int length) {
        this.num = new int[length];
    }
    /**
     * 向动态数组中添加元素，默认向数组末尾添加
     * @param data
     */
    public void add(int data) {
        if (size == num.length) {
            num = Arrays.copyOf(num,num.length << 1);
        }
        num[size] = data;
        size ++;
    }

    /**
     * 向动态数组的任意位置插入元素
     * @param index 插入的目标索引
     * @param data
     */
    public void add(int index,int data) {
        // 判断index是否合法
        if (index < 0 || index > size) {
            // 只要index > size 都是非法的，因为数组无法取到数组长度的下标
            System.out.println("索引非法!");
            return;
        }
        // 数组尾插
        if (index == size) {
            add(data);
        }else {// 数组中间位置插入
            // 判断内部数组是否满载
            if (size == num.length) {
                //扩容
                grow();
                //num = Arrays.copyOf(num,num.length << 1);
            }
            // 将index以及之后元素向后搬移
            System.arraycopy(num,index,num,index + 1,size - index);
            num[index] = data;
            size ++;
        }
    }

    //获取数组指定位置的值
    public int get(int index) {
        if(rangeCheck(index)) {
            return num[index];
        }
        return -1;
    }


    //修改数组指定位置的值
    public boolean set(int index,int data) {
        if(rangeCheck(index)) {
            num[index] = data;
            return true;
        }
        return false;
    }

    //删除指定位置的值
    public boolean remove(int data) {
        for (int i = 0; i < size; i++) {
            if(num[i] == data) {
                //将找到的data值的index后的值向前移动，覆盖data值所在位置
                System.arraycopy(num,i+1,num,i,size-i-1);
                num[size] = 0;
                size--;
                return true;
            }
        }
        return false;
    }

    //清空数组
    public void clear() {
        //将数组中的值都赋值为0
        Arrays.fill(num,0,size,0);
    }

    // 返回动态数组长度
    public int size() {
        return size;
    }

    // 打印动态数组内容
    public void print() {
        // 数组永远无法取到数组长度下标，因此不能等于size
        for (int i = 0; i < size; i++) {
            System.out.print(num[i] + "、");
        }
        System.out.println();
    }

    //需要有一个方法来检验index下标的合法性
    //由于该方法只属于MyArray的内部调用，因此将其封装
    private boolean rangeCheck(int index) {
        if(index < 0 || index >= size) {
            return false;
        }
        return true;
    }

    //内部数组的扩容方法
    private void grow() {
        num = Arrays.copyOf(num,num.length << 1);
    }
}

测试代码

package MyArray;

public class Test {
    public static void main(String[] args) {
        MyArray myArray = new MyArray(3);
        //在数组末尾插入元素
        myArray.add(1);
        myArray.add(3);
        myArray.add(5);
        //在数组任意位置插入元素
        myArray.add(3,7);
        myArray.add(4,8);
        //获取数组任意位置的值
        myArray.get(4);
        //修改数组任意位置的值
        myArray.set(3,10);

        myArray.print();
        //删除数组某个指定位置的值
        myArray.remove(3);
        myArray.print();
    }
}