搜 索

Java数据结构基础丨数组

  • 354阅读
  • 2021年02月17日
  • 0评论
首页 / 默认分类 / 正文

数组的基本知识

  • 数组是最为简单、最为常用的数据结构。
  • 数组对应的英语名称是 Array,是有限个相同类型的变量所组成的有序集合;数组中的每一个变量被称为元素。
  • 数组是一种线性表数据结构(除了数组,还有链表、队列、栈等);与其对立的是非线性表(二叉树、堆、图等)。数组的下标从0开始,而不是1;直到 array.length-1 为止。
  • 数组里边存放的数据类型要一致,可以基本数据类型,也可以是引用数据类型,但是唯一的标准就是相同的类型。
  • 打印Java数组用的是 ArrayName.toString() 而不是 ArrayName 。

    // myArray1仅仅是一个地址引用
    int[] myArray1 = {3, 6, 7, 9, 5};
    // 直接输出的是内存地址
    System.out.println(myArray1);
    // myArray1.toString()才是真正的数组值
    System.out.println(Arrays.toString(myArray1));

数组的基本操作

  1. 读取
    数组支持随机访问,根据下标随机访问的时间复杂度为O(1)。
    System.out.println(array[index]);
  2. 插入

    • 尾部插入——这是最简单的情况,直接把要插入的元素放在数组尾部的空闲位置即可,不需要移动数据。
      array[index] = value;
    • 中间插入——这种情况稍复杂,需要移动数据:假设某有序数组的长度为 n,要将一个新数据插入到该数组的第 K 个位置,那么需要将 k~n 这部分的元素都顺序地往后挪一位,以腾出第 K 个位置给新数据。

      /**
       * @param index 新元素插入的位置
       * @param element 插入的新元素
       * @throws Exception 超出边界异常
       */
      public void insert(int index, int element) throws Exception {
       // 判断访问下标是否超出范围
       if(index < 0 || index > size){
           throw new IndexOutOfBoundsException("超出数组实际元素范围!");
       }
       // 从右往左循环,将元素逐个向右移动1位
       for(int i = size-1; i >= index; i--){
           array[i+1] = array[i];
       }
       // 腾出的位置放入新元素
       array[index] = element;
       size++;
      }
    • 如果数组中存储的数据并没有任何规律,数组只是被当做一个存储数据的集合,那么实现将新数据插入到第 k 个位置,为了避免大规模的数据搬移,可以取巧:直接将原本第k位的数据移到数组元素的最后,再把新数据直接放入第 k 个位置。
    • 超范围插入——数组的长度是不变的,一旦数组完成初始化后,它的长度就固定下来了,在内存中占有的空间也就固定了,即使里面的数据被清空了,占有的空间还是保留下来了,依然是属于数组的,当然长度依旧是不变的。那么,想要向空间已满的数组插入一个新数据,这是要为难我胖虎?这就要涉及到数组的扩容了。
    CSDN-Arrays.copyOf()&System.arraycopy()
  3. 删除
    和插入操作类似,最好的情况是删除数组末尾的数据;最坏的情况是删除开头的数据。若要删除第 k 个位置的数据,为了内存的连续性,也需要搬移数据。前提与插入的取巧操作一样,删除第 k 个位置的数据,也可以取巧:可以把数组的最后一个元素复制到第 k 个位置,再删除最后一个元素。和插入操作相反,如果要删除的元素位于数组中间,其后的元素都需要向前移动1位。

    /**
     * @param index 删除的位置
     * @return 返回删除的元素
     * @throws Exception 超出边界异常
     */
    public int delete(int index) throws Exception {
      // 判断访问下标是否超出范围
      if(index < 0 || index >= size){
          throw new IndexOutOfBoundsException("超出数组实际元素范围!");
      }
      int deletedElement = array[index];
      // 从左往右循环,将元素逐个向左移动1位
      for(int i=index; i < size-1; i++){
          array[i] = array[i+1];
      }
      size--;
      return deletedElement;
    }

数组类Arrays的常用方法

  • 从数组中查询指定位置的元素,或者查询某元素在指定数组中的位置——binarySearch(Object[] array, Object key),如果要搜索的元素在指定的范围内,则返回搜索键的索引。
  • 比较两个数的大小——compare(),如果二者相等返回 0,如果前者大于后者,返回 1;反之返回 -1。
  • 比较数组元素的个数和对应位置的元素是否相等——Arrays.equals(arrayA, arrayB),返回布尔型结果。
  • 在数组指定位置进行数值填充——Arrays.fill(array, value),只能使用同一个数值进行填充。
  • 数组复制——Arrays.copyOf(dataType[] srcArray,int length)。
官方文档

数组的优劣

数组具有非常高效的随机访问能力,只要知道下标,就可以用常量时间找到相对应的元素。由于数组元素连续紧密地存储在内存中,插入、删除元素操作都会导致大量元素被迫移动,影响效率。数组适合的是读操作多、写操作少的场景。
数组有一个缺点,就是一旦声明,就不能改变容量,这个也是其使用频率不高的原因。

打 赏
  • 支付宝
  • 微信
Alipay
WeChatPay
评论区
暂无评论
avatar