动态数组：扩容与缩容

动态数组：扩容与缩容

动态数组 是一种动态存储的线性表，所有元素的内存地址都是连续的。

很多语言的开发都需要用到数组来存储数据，本文主要是学习了一下实现数组的一些基本方法，以及扩容操作和缩容操作的原理。

数组打印：
Java中数组的打印直接是打印的对象的类型，例如直接打印:

     ArrayList list  = new ArrayList();
     list.add(11);
     list.add(22);
     list.add(33);
     System.out.println(list);

打印结果：

com.yy.ArrayList@4e25154f

为了达到打印能看到数组内部的元素，或者其他情况，需要重写ArrayList中的toString()方法:

   @Override
    public String toString() {
        StringBuilder string = new StringBuilder();
        string.append("size=").append(size).append(", [");
        for (int i = 0; i < size; i++) {
            if (i != 0) string.append(", ");
            string.append(elements[i]);
        }
        string.append("]");
        return string.toString();
    }

重写以后，打印结果如下：

size=3, [11, 22, 33]

快速生成代码：

  • 快速生成构造函数：command + option + s -> Generate Contructor using Fields
  • 快速生成重写toString方法：command + option + s -> Generate toString...
image.png

示例：一个person类生成的构造方法和toString：

public class Person {
    private int age;
    private String name;
    public Person(int age, String name) {
        this.age = age;
        this.name = name;
    }

    @Override
    public String toString() {
        return "Person [age=" + age + ", name=" + name + "]";
    }

}

1.1 添加元素

1.1.1 添加元素到末尾

添加元素到末尾思路：

  • 当 size == 0 的时候，elements[0] = element;
  • 当 size > 0 的时候，elements[size] = element;
  • 最后size ++ ；
    /*
     *  添加元素到末尾
     **/
    public void add(int element) {
        elements[size ++] = element;
    }

1.1.2 删除index位置元素

删除元素-摘自小码哥课件

如图，在index=3位置，未删除之前elements[3] = 44;
删除index == 3位置元素44 思路：

  • index == 5 6 7 位置元素向前挪动一位（for 循环）
  • index == 6位置元素不需要处理，因为删除完成以后size --，只能访问到前6个元素。
    /*
     *  删除index位置元素
     **/
    public int remove(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index" + index + ",Size"+ size);
        }
        int old = elements[index];
        for (int i = index + 1; i < size; i++) {
            elements[i - 1] = elements[i];
        }
        size --;
        return old;
    }

1.1.3 添加元素到index位置

image.png

如图，在index=2位置，添加一个新的元素;
原有index == 2，3，4位置元素往后挪动 思路：

  • index == 2 3 4 位置元素向后挪动一位（for 循环）
  • 注意： 挪动顺序，从高往低
    • 4-->5;
    • 3-->4;
    • 2-->3;
  • 插入新元素到index == 2。
  • size ++；
       /*
        *  添加，插入元素
        **/
       public void add(int index, int element) {
           if (index < 0 || index > size) {
               throw new IndexOutOfBoundsException("Index" + index + ",Size"+ size);
           }
           for (int i = size - 1 ;i >= index; i--) {
               elements[i + 1] = elements[i];
           }
           elements[index] = element;
           size ++;
       }

2. 数组的扩容

当添加元素时，创建的elements数组容量不够了，这时候不能直接给elements扩容，因为创建的时候elements的容量就已经开辟好了；

所以需要创建一个新的数组，并将elements中的元素挪到新的数组中；

步骤如下：

  • 判断容量是否够用，也就是size + 1 <= elements.length；
  • 创建一个新的数组newElements，容量为elements的1.5倍(使用位运算效率更高)；
  • 将elements中的元素挪到newElements中；
  • 将element指针指向newElements；
扩容示例-摘自小码哥课件

代码实现如下：

    /*
     * 扩容
     * */
    private void ensureCapacity(int capacity){
        if(elements.length >= capacity) return;
        int oldCapacity = elements.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        int[] newElements = new int[newCapacity];
        for (int i = 0; i < size; i++) {
            newElements[i] = elements[i];
        }
        elements = newElements;
        System.out.println(oldCapacity + "扩容到" + newCapacity);
    }

测试是否能扩容实现：


测试扩容

2. 数组的缩容

当删除元素时，elements数组中元素会越来越少，当少到一定程度时，数组原有开辟的空间就会浪费，所以就要考虑到缩容操作；

    /*
     *  删除index位置元素
     **/
    public E remove(int index) {
        rangeCheck(index);
        E old = elements[index];
        for (int i = index + 1; i < size; i++) {
            elements[i - 1] = elements[i];
        }
        elements[--size] = null; //将最后一个元素存放的指针清空
        trim(); //缩容操作
        return old;
    }

所以和扩容一样，需要创建一个新的数组，并将elements中的元素挪到新的数组中；

步骤如下：

  • 判断容量是否够用，也就是size 大于elements容量的一半时，或者容量小于DEFAULIT_CAPACITY默认容量10时，没必要进行缩容操作；
  • 创建一个新的数组newElements，容量为elements的1/2(使用位运算效率更高)；
  • 将elements中的元素挪到newElements中；
  • 将element指针指向newElements；
  private void trim(){
      int capacity = elements.size;
      int newCapacity = capacity >> 1; //右移一位相当于除以2
      if(size >= newCapacity || capacity <= DEFAULIT_CAPACITY) return;
      @SuppressWarnings("unchecked")
      E[] newElements = (E[]) new Object[newCapacity];
      for (int i = 0; i < size; i ++){
          newElements[i] = elements[i];
      }
     elements = newElements;
     System.out.println(capacity + "缩容到" + newCapacity)；
  }
image.png

2 泛型

在之前实现的动态数组中，存放的元素只能是int类型，有一定的局限性；
所以我们要将数组的内容改成可以存放对象，这样里面存放任何东西都行；包括基本数据类型和对象类型；

java中存在泛型这个概念：

2.1 Java 泛型（generics）

是 JDK 5 中引入的一个新特性, 泛型提供了编译时类型安全检测机制，该机制允许程序员在编译时检测到非法的类型。
泛型的本质是参数化类型，也就是说所操作的数据类型被指定为一个参数。

2.2 泛型方法

你可以写一个泛型方法，该方法在调用时可以接收不同类型的参数。根据传递给泛型方法的参数类型，编译器适当地处理每一个方法调用。
下面是定义泛型方法的规则：

  • 所有泛型方法声明都有一个类型参数声明部分（由尖括号分隔），该类型参数声明部分在方法返回类型之前（在下面例子中的<E>）。
  • 每一个类型参数声明部分包含一个或多个类型参数，参数间用逗号隔开。一个泛型参数，也被称为一个类型变量，是用于指定一个泛型类型名称的标识符。
  • 类型参数能被用来声明返回值类型，并且能作为泛型方法得到的实际参数类型的占位符。
  • 泛型方法体的声明和其他方法一样。注意类型参数只能代表引用型类型，不能是原始类型（像int,double,char的等）。
public class GenericMethodTest
{
   // 泛型方法 printArray                         
   public static < E > void printArray( E[] inputArray )
   {
      // 输出数组元素            
         for ( E element : inputArray ){        
            System.out.printf( "%s ", element );
         }
         System.out.println();
    }
 
    public static void main( String args[] )
    {
        // 创建不同类型数组： Integer, Double 和 Character
        Integer[] intArray = { 1, 2, 3, 4, 5 };
        Double[] doubleArray = { 1.1, 2.2, 3.3, 4.4 };
        Character[] charArray = { 'H', 'E', 'L', 'L', 'O' };
 
        System.out.println( "整型数组元素为:" );
        printArray( intArray  ); // 传递一个整型数组
 
        System.out.println( "\n双精度型数组元素为:" );
        printArray( doubleArray ); // 传递一个双精度型数组
 
        System.out.println( "\n字符型数组元素为:" );
        printArray( charArray ); // 传递一个字符型数组
    } 
}

2.3 修改动态数组存放泛型对象

  1. 修改类型参数声明;

  2. 修改数组elements中存放的元素类型int为E；

    • 在java中所有的类最终都继承自 java.lang.Object

    private E[] elements = (E[]) new Object[capacity];

    • 点击修改警告，会添加类型转换，

  3. 修改扩容时newElements中的存放元素类型int为E，以及其他传入的参数，返回的参数为int型的为E（注意传入的参数index不需要修改）

修改后的打印：


image.png

注意：修改后，创建数组时要指定类型，比如Person，Integer，Double，Integer相当于Int的对象类型；

2.4 数组存放int和泛型的区别

  1. 当数组中存放的是基本数据类型时，存放的就是数据本身；
  2. 当数组中存放的是泛型对象时，直接将对象放到数组中不现实，因为每个对象的属性值数不一样，所以对象的大小不一样，会导致数组分配的内存特别大；
  3. 所以对象类型的元素，存放到数组中的是对象的指针，如下图：
image.png

当查询数组中的某一个元素时，返回的是这个对象的地址，再通过地址去查找这个对象；

2.4.1 内存管理细节：数组的清空操作

1、在动态数组的clear清空操作时，要特殊处理：

    /*
     * 清除元素
     * **/
    public void clear(){
        //清空数组内部保存的对象的地址 --> 及时的清除不要的对象
        for (int i = 0; i < size; i++) {
            elements[i] = null;
        }
        size = 0;
    }

清空数组时，需要遍历一遍将对应的地址置为null，地址置为null后就回自动将对象释放，不然得等数组中重新存放元素时，这个对象才能释放，万一不存放元素，这个对象就会一直在内存中；

注意：不能将elements = null，也就是objects指针置为空，这样操作也能达到目的，但是以后只要是清空了，数组也会被释放，每次都得重新创建数组，这不合理，合理的操作应该是只需要将数组中存放的地址置为空就行。

2、 在数组remove移除操作时，挪动完成以后对最后一个位置存放的元素的指针应当清除操作：

/*
*  删除index位置元素
**/
public E remove(int index) {
   rangeCheck(index);
   E old = elements[index];
   for (int i = index + 1; i < size; i++) {
       elements[i - 1] = elements[i];
   }
   elements[--size] = null; //将最后一个元素存放的指针清空
   return old;
}

2.5 数组是否可以存放null

1、 假如数组不允许存放null，在add操作时，加入判断即可：

if(element == null) return;

2、但是java官方默认是可以加入null的，但是在返回index方法需要特殊处理：
index 返回第一个null元素的index；

    /*
     * 元素索引
     * ***/
    public int indexof(E element) {
        if (element == null) {
            for (int i = 0; i < size; i++) {
                if(elements[i]==null) return i;
            }
        }else{
            for (int i = 0; i < size; i++) {
                if(element.equals(elements[i])) return i;
            }   
        }
        return ELEMENT_NOT_FOUND;
    }
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 213,335评论 6赞 492
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 90,895评论 3赞 387
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 158,766评论 0赞 348
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 56,918评论 1赞 285
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 66,042评论 6赞 385
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 50,169评论 1赞 291
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 39,219评论 3赞 412
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 37,976评论 0赞 268
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 44,393评论 1赞 304
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,711评论 2赞 328
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,876评论 1赞 341
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 34,562评论 4赞 336
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 40,193评论 3赞 317
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,903评论 0赞 21
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,142评论 1赞 267
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 46,699评论 2赞 362
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 43,764评论 2赞 351