数据结构——Java中的数组

布满荆棘的人生 2022-05-10 10:12 171阅读 0赞

### Java中定义数组的几种方式 ###

//Java中定义数组的几种方式
            int [] arr1 = new int [10];
            int [] arr2 = new int []{1,2,3,4};
            int [] arr3 = {1,2,3};

数组可以通过下标(索引)快速定位，索引可以富含语义，也可以没有语义，如：

1、含语义：班上有30个同学，对应的学号是0-29，那么数组中每个索引代表一个同学。

2、无语义：不能通过身份证号作为下标代表一个人。

![70][]

如我们开辟了含有8个元素的数组，但数组中只存放着三个元素，那么这个时候可能就存在问题了。

索引3-7并没有元素，访问scores\[3\]到scores\[7\]就是非法的，从用户的角度看，只有0-2索引存放着数据。

此时如何表示没有的元素呢？

那么这时候我们向数组中添加元素和删除该怎么做呢？

数组的长度在我们创建的时候就已经固定好了，如果我们添加的元素超过了8个又应该怎么做呢？

**Java为我们提供的数组是静态数组，下面我们就基于Java的静态数组，二次封装数组，实现我们的动态数组。**

对我们的动态数组实现增删改查操作。

### **使用泛型** ###

**Array类是一个容器，应该容纳"任意"的数据类型。**

**这里的任意申明了双引号，因为不可以是基本数据类型，只能是类对象**

**对于基本数据类型，Java为我们提供了对应的包装类型**

public class Array<E> {
        private E[] data;
        private int size;
    
        public Array(int capacity) {
            data =(E[]) new Object[capacity];
            size = 0;
        }
    
        public Array() {
            //空参数构造默认的capacity为10
            this(10);
        }
    
        //获取数组元素中元素个数
        public int getSize() {
            return this.size;
        }
    
        //获得数组容量
        public int getCapacity() {
            return data.length;
        }
    
        //判断数组是否为空
        public boolean isEmpty() {
            return size == 0;
        }
    
        //向数组尾部添加元素
        public void addLast(E e) {
            add(size, e);
        }
    
        //向数组头部添加元素
        public void addFirst(E e) {
            add(0, e);
        }
    
        //向数组中index索引处插入某个元素
        public void add(int index, E e) {
            //检查数组中是否能容纳新的元素
            if (size == data.length)
                System.out.println("数组需要扩容");
                resize(data.length * 2);
            if (index < 0 || index > size)
                throw new IllegalArgumentException("index非法");
            //移动元素
            for (int i = size - 1; i >= index; i--) {
                //后一个索引赋上前一个索引的元素，即每一个元素都向后挪了一个位置
                data[i + 1] = data[i];
            }
            data[index] = e;
            size++;
        }
    
        //获取数组中的值
        E get(int index) {
            if (index < 0 || index >= size)
                throw new IllegalArgumentException("index非法");
            return data[index];
        }
    
        //获取数组中的值
        E getLast() {
            return get(size - 1);
        }
    
        //获取数组中的值
        E getFirst() {
            return get(0);
        }
    
        //更新数组的值
        E update(int index, E e) {
            E oldValue = get(index);
            data[index] = e;
            return oldValue;
        }
    
        //数组中是否含有某元素,有返回true,无返回false
        public boolean contains(E e) {
            for (int i = 0; i < size; i++) {
                if (data[i].equals(e))
                    return true;
            }
            return false;
        }
    
        //查找数组中的某个元素，找到返回索引，找不到返回-1
        public int find(E e) {
            for (int i = 0; i < size; i++) {
                if (data[i].equals(e)) {
                    return i;
                }
            }
            return -1;
        }
    
        //删除数组中某个元素
        public E remove(int index) {
            if (index < 0 || index >= size) {
                throw new IllegalArgumentException("index非法");
            }
            E ret = data[index];
            for (int i = index + 1; i < size; i++) {
                data[i - 1] = data[i];
            }
            size--;
            data[size] = null;
            if(size == data.length / 4 && data.length / 2 != 0 )
                resize(data.length /2);
            return ret;
        }
    
        public void removeFirst() {
            remove(0);
        }
    
        public E removeLast() {
            return remove(size - 1);
        }
    
        //删除指定元素,如果有则删除,删除成功返回true,删除失败返回false
        public boolean removeElement(E e) {
            int index = find(e);
            if(index != -1){
                remove(index);
                return true;
            }
            return false;
        }
    
        //实现动态数组,动态扩容 size==data.lenngth 扩容2倍 和 缩容 size == data.length / 2
        private void resize(int newCapacity){
            //创建一个新的数组
            E[] newData = (E[]) new Object[newCapacity];
            //把原来的元素迁移到新的数组中
            for(int i = 0 ; i < size ; i++){
                newData[i] = data[i];
            }
            data = newData;
        }
    
        //打印数组中的元素
        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            sb.append(String.format("Array: size = %d , capacity = %d\n", size, data.length));
            //显示[1,2,3,4,5]
            sb.append("[");
            for (int i = 0; i < size; i++) {
                sb.append(data[i]);
                if (i != size - 1) {
                    sb.append(", ");
                }
            }
            sb.append("]");
            return sb.toString();
        }
    
    
    }

### 时间复杂度分析 ###

O描述的是算法的运行时间和输入数据之间的关系。

该Array中，增O(n)、删O(n)、改——①通过index O(1)  ②无index O(n) 、查——①通过index O(1)  ②无index O(n)

**均摊复杂度**

对于resize(newCapacity)，假设capacity=n ，经过n+1次addLast()，触发resize()，总共进行了2n+1次基本操作，平均每次addLast()操作进行2次基本操作，这样均摊时间复杂度是O(1)的。

**复杂度震荡**

addLast后 n->2n，resize()    时间复杂度O(n)，removeLast后 2n->n，resize()    时间复杂度O(n)，以此循环

若每一次都震荡，则时间复杂度为O(n)。

问题的出现原因：removeLast()时，resize()过于着急。

解决方案：Lazy策略，当size = capacity/4时，才resize()缩容。

[70]: /images/20220510/714932680ce54b9c8b2647d11c1a88bf.png