关于数据结构和算法:数组容器ArrayList设计与Java实现看完这个你不懂ArrayList你找我

4次阅读

共计 9788 个字符，预计需要花费 25 分钟才能阅读完成。

数组容器 (ArrayList) 设计与 Java 实现

本篇文章次要跟大家介绍咱们最常应用的一种容器 ArrayList、Vector 的原理，并且本人应用 Java 实现本人的数组容器 MyArrayList，让本人写的容器能像ArrayList 那样工作。在本篇文章当中首先介绍 ArrayList 的一些基本功能，而后去剖析咱们本人的容器 MyArrayList 应该如何进行设计，同时剖析咱们本人的具体实现办法，最初进行代码介绍！！！

ArrayList 为咱们提供了哪些性能？

咱们来看一个简略的代码，随机生成 100 个随机数，查看生成随机数当中是否存在 50 这个数。

public class MyArrayList {public static void main(String[] args) {Random random = new Random();
    ArrayList<Integer> list = new ArrayList<>();
    for (int i = 0; i < 100; i++) {list.add(random.nextInt(5000));
    }
    for (int i = 0; i < 100; i++) {if (list.get(i) == 50) {System.out.println("蕴含数据 50");
      }
    }
    list.set(5, 1000);// 设置下标为 5 的数据为 100
    list.remove(5);// 删除下标为 5 的数据
    list.remove(new Integer(888));// 删除容器当中的第一个值为 5 的数据
  }
}

上述代码蕴含了 ArrayList 最根本的一个性能，一个是 add 办法，向数组容器当中退出数据，另外一个办法是 get 从容器当中拿出数据，set办法扭转容器里的数据，remove办法删除容器当中的数据。ArrayList的很多其余的办法都是围绕这四个最根本的办法开展的，因而咱们在这里不认真介绍其余的办法了，前面咱们本人实现的时候遇到问题的时候天然会须要设计相应的办法，而后咱们进行解决即可。

当初咱们就须要去设计一个数组容器实现“增删改查”这四个基本功能。

设计原理剖析

首先明确一点咱们须要应用什么工具去实现这样一个容器。咱们手里有的工具就是 Java 提供给咱们的最根本的性能——数组（这个如同是废话，咱们的题目就是 数组容器🤣）。

当咱们在 Java 当中应用数组去存储数据时，数据在 Java 当中的内存布局大抵如下图所示。

咱们在设计数组容器这样一个数据结构的时候次要会遇到两个问题：

  • 咱们申请数组的长度是多少。
  • 当数组满了之后怎么办，也就是咱们的扩容机制。

对于这两个问题，首先咱们数组的初始大小能够有默认值，在咱们本人实现的 MyArrayList 当中设置为 10，咱们在应用类时也能够传递一个参数指定初始大小。第二个问题当咱们的数组满的时候咱们须要对数组进行扩容，在咱们实现的 MyArrayList 当中咱们采取的形式是，新数组的长度是原数组的两倍（这个跟 JDK 的ArrayList形式不一样，ArrayList扩容为原来的 1.5 倍）。

代码实现

为了让咱们的类实现的更加简略咱们在代码当中就不做很多非必要的逻辑判断并且抛出异样，咱们的代码只有能体现出咱们的思维即可。

  • 首先定义一个接口MyCollection，示意咱们要实现哪些办法！
public interface MyCollection<E> {

  /**
   * 往链表尾部退出一个数据
   * @param o 退出到链表当中的数据
   * @return
   */
  boolean add(E o);

  /**
   * 示意在第 index 地位插入数据 o
   * @param index
   * @param o
   * @return
   */
  boolean add(int index, E o);

  /**
   * 从链表当中删除数据 o
   * @param o
   * @return
   */
  boolean remove(E o);

  /**
   * 从链表当中删除第 index 个数据
   * @param index
   * @return
   */
  boolean remove(int index);

  /**
   * 往链表尾部退出一个数据，性能和 add 一样
   * @param o
   * @return
   */
  boolean append(E o);

  /**
   * 返回链表当中数据的个数
   * @return
   */
  int size();

  /**
   * 示意链表是否为空
   * @return
   */
  boolean isEmpty();

  /**
   * 示意链表当中是否蕴含数据 o
   * @param o
   * @return
   */
  boolean contain(E o);

  /**
   * 设置下标为 index 的数据为 o
   * @param index
   * @param o
   * @return
   */
  boolean set(int index, E o);
}
  • 咱们的构造函数，初始化过程。
  public MyArrayList(int initialCapacity) {this();
    // 增长数组的空间为 initialCapacity，即申请一个数组
    // 且数组的长度为 initialCapacity
    grow(initialCapacity); 
  }

  public MyArrayList() {
    this.size = 0; // 容器当中的数据个数在开始时为 0
    this.elementData = EMPTY_INSTANCE; // 将数组设置为空数组
  }

  • 咱们须要实现的最简单的办法就是 add 了，这个办法是四个办法当中最简单的，其余的办法都绝对比较简单。

    • 进入 add 办法之后，咱们须要找到符合要求的最小数组长度，这个值通常是容器当中元素的个数 size + 1，也就是图中的minCapacity 首先先比拟这个值和当初数组的长度，如果长度不够的话则须要进行扩容，将数组的长度扩充到原来的两倍。
    • 如果不须要扩容，则间接讲元素放入到数组当中即可。

  @Override
  public boolean add(E o) {
    // 这个函数的次要作用就是确保数组的长度至多为 size + 1
    ensureCapacity(size + 1);
    // 新减少了一个数据，容器的大小须要 + 1
    elementData[++size] = o;
    return true;
  }

  /**
   * 这个函数的次要作用就是确保数组的长度至多为 capacity
   * @param capacity
   */
  public void ensureCapacity(int capacity) {int candidateCapacity = findCapacity(capacity);
    if (elementData.length < candidateCapacity)
      grow(candidateCapacity);
  }

  /**
   * 这个函数的次要目标就是找到最终数组长度需要的容量
   * @param minCapacity
   * @return
   */
  private int findCapacity(int minCapacity) {
    /**
     * 如果 if 条件为 true 即 elementData 还是初始化时设置的空数组
     * 那么返回默认大小和须要大小的最大值 
     * 否则间接返回 minCapacity
     */
    if (elementData == EMPTY_INSTANCE){return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
  }
  • 咱们为什么须要将 ensureCapacity 的拜访限度权限设置为public？因为咱们想让用户尽量去应用这个函数，因为如果咱们如果写出上面这样的代码咱们会始终申请内存空间，而后也须要将后面的数组开释掉，会给垃圾回收器造成更大的压力。
    ArrayList<Integer> list = new ArrayList<>();
    for (int i = 0; i < 1000000; i++) {list.add(i);
    }

上面咱们对 ArrayList 的办法进行测试：

import java.util.ArrayList;

class Person {

  String name;

  public String getName() {return name;}

  public void setName(String name) {this.name = name;}

  @Override
  public String toString() {
    return "Person{" +
        "name='" + name + '\'' +
        '}';
  }
}


public class ArrayListTest {public static void main(String[] args) {ArrayList<Person> o1 = new ArrayList<>();
    o1.ensureCapacity(10000000);
    long start = System.currentTimeMillis();
    for (int i = 0; i < 10000000; i++) {o1.add(new Person());
    }
    long end = System.currentTimeMillis();
    System.out.println("end - start:" + (end - start));
    ArrayList<Person> o2 = new ArrayList<>();
    start = System.currentTimeMillis();
    for (int i = 0; i < 10000000; i++) {o2.add(new Person());
    }
    end = System.currentTimeMillis();
    System.out.println("end - start:" + (end - start));
  }
}
// 输入后果
end - start: 1345
end - start: 4730

从下面的测试后果咱们能够看出提前应用 ensureCapacity 办法之后，程序执行的工夫更加短。

  • 插入数据的 add 办法。
  @Override
  public boolean add(E o) {
    // 这个函数的次要作用就是确保数组的长度至多为 size + 1
    ensureCapacity(size + 1);
    // 新减少了一个数据，容器的大小须要 + 1
    elementData[size] = o;
    size++;
    return true;
  }

  • add在指定下标插入数据。

    • 首先将插入下标后的数据往后挪动一个地位
    • 而后在将数据放在指定下标的地位。

  /**
   * 在下标 index 地位插入数据 o
   * 首先先将 index 地位之后的数据往后挪动一个地位
   * 而后将 index 赋值为 o
   * @param index
   * @param o
   * @return
   */
  @Override
  public boolean add(int index, E o) {
    // 确保容器当中的数组长度至多为 size + 1
    ensureCapacity(size + 1);
    // 将 elementData index 地位之后的数据往后挪动一个地位
    // 做一个原地拷贝
    System.arraycopy(elementData, index, elementData, index + 1,
        size - index); // 挪动的数据个数为 size - index
    elementData[index] = o;
    size++;
    return true;
  }

  • 删除数据的办法remove。

    • 首先先删除指定下标的数据。
    • 而后将指定下标后的数据往前挪动一个地位
    • 在理论的操作过程中咱们能够不删除，间接挪动，这样也笼罩被插入地位的数据了。

  /**
   * 移除下标为 index 的数据
   * @param index
   * @return
   */
  @Override
  public boolean remove(int index) {
    // 须要被挪动的数据个数
    int numMoved = size - index - 1;
    if (numMoved > 0)
      System.arraycopy(elementData, index+1, elementData, index,
          numMoved);
    elementData[--size] = null;

    return true;
  }
  • 移除容器当中具体的某个对象。
  /**
   * 这个办法次要是用于溢出容器当中具体的某个数据
   * 首先先通过 for 循环遍历容器当中的每个数据，* 比拟找到雷同的数据对应的下标，而后通过下标移除办法
   * @param o
   * @return
   */
  @Override
  public boolean remove(E o) {if (o == null) {for (int index = 0; index < size; index++)
        if (elementData[index] == null) {remove(index);
          return true;
        }
    } else {for (int index = 0; index < size; index++)
        if (o.equals(elementData[index])) {remove(index);
          return true;
        }
    }
    return false;
  }
  • set办法，这个办法就很简略了。
  @Override
  public boolean set(int index, E o) {elementData[index] = o;
    return true;
  }
  • 重写 toString 办法。
  @Override
  public String toString() {if (size <= 0)
      return "[]";

    StringBuilder builder = new StringBuilder();
    builder.append("[");
    for (int index = 0; index < size; index++) {builder.append(elementData[index].toString() + ",");
    }
    builder.delete(builder.length() - 2, builder.length());
    builder.append("]");
    return builder.toString();}
  • 测试代码
public static void main(String[] args) {MyArrayList<Integer> list = new MyArrayList<>();
    for (int i = 0; i < 15; i++) {list.add(-i);
    }
    System.out.println(list.contain(5));
    System.out.println(list);
    list.remove(new Integer(-6));
    System.out.println(list);
    System.out.println(list.elementData.length); // 容器会扩容两倍，而默认容器长度为 10，因而这里是 20 
    list.add(5, 99999);
    System.out.println(list);
    System.out.println(list.contain(99999));
  }
// 代码输入
false
[0, -1, -2, -3, -4, -5, -6, -7, -8, -9, -10, -11, -12, -13, -14]
[0, -1, -2, -3, -4, -5, -7, -8, -9, -10, -11, -12, -13, -14]
20
[0, -1, -2, -3, -4, 99999, -5, -7, -8, -9, -10, -11, -12, -13, -14]
true

残缺代码

import java.util.ArrayList;
import java.util.Arrays;


public class MyArrayList<E> implements MyCollection<E> {

  /**
   * 容器当中存储数据的个数
   */
  private int size;

  /**
   * 容器中数组的默认长度
   */
  private static final int DEFAULT_CAPACITY = 10;

  /**
   * 寄存具体数据的数组，也就是咱们容器当中真正存储数据的中央
   */
  Object[] elementData;

  /**
   * 当容器当中没有数据将 elementData 设置为这个值，这个值是所有实例一起共享的
   */
  private static final Object[] EMPTY_INSTANCE = {};


  public MyArrayList(int initialCapacity) {this();
    // 增长数组的空间为 initialCapacity，即申请一个数组
    // 且数组的长度为 initialCapacity
    grow(initialCapacity);
  }

  public MyArrayList() {
    this.size = 0; // 容器当中的数据个数在开始时为 0
    this.elementData = EMPTY_INSTANCE; // 将数组设置为空数组
  }

  /**
   * 这个函数的次要作用就是确保数组的长度至多为 capacity
   * @param capacity
   */
  public void ensureCapacity(int capacity) {int candidateCapacity = findCapacity(capacity);
    if (elementData.length < candidateCapacity)
      grow(candidateCapacity);
  }

  /**
   * 这个函数的次要目标就是找到最终数组长度需要的容量
   * @param minCapacity
   * @return
   */
  private int findCapacity(int minCapacity) {
    /**
     * 如果 if 条件为 true 即 elementData 还是初始化时设置的空数组
     * 那么返回默认大小和须要大小的最大值
     * 否则间接返回 minCapacity
     */
    if (elementData == EMPTY_INSTANCE){return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
  }

  /**
   * 该函数次要保障 elementData 的长度至多为 minCapacity
   * 如果数组的长度小于 minCapacity 则须要进行扩容，反之
   * @param minCapacity 数组的最短长度
   */
  private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    // 新的数组长度为原来数组长度的两倍
    int newCapacity = oldCapacity << 1;

    // 如果数组新数组的长度 newCapacity 小于所须要的长度 minCapacity
    // 新申请的长度应该为 minCapacity
    if (newCapacity < minCapacity) {newCapacity = minCapacity;}
    // 申请一个长度为 newCapacity 的数组，在将原来数组
    // elementData 的数据拷贝到新数组当中
    elementData = Arrays.copyOf(elementData, newCapacity);
  }

  @Override
  public boolean add(E o) {
    // 这个函数的次要作用就是确保数组的长度至多为 size + 1
    ensureCapacity(size + 1);
    // 新减少了一个数据，容器的大小须要 + 1
    elementData[size] = o;
    size++;
    return true;
  }

  /**
   * 在下标 index 地位插入数据 o
   * 首先先将 index 地位之后的数据往后挪动一个地位
   * 而后将 index 赋值为 o
   * @param index
   * @param o
   * @return
   */
  @Override
  public boolean add(int index, E o) {
    // 确保容器当中的数组长度至多为 size + 1
    ensureCapacity(size + 1);
    // 将 elementData index 地位之后的数据往后挪动一个地位
    // 做一个原地拷贝
    System.arraycopy(elementData, index, elementData, index + 1,
        size - index); // 挪动的数据个数为 size - index
    elementData[index] = o;
    size++;
    return true;
  }

  /**
   * 这个办法次要是用于溢出容器当中具体的某个数据
   * 首先先通过 for 循环遍历容器当中的每个数据，* 比拟找到雷同的数据对应的下标，而后通过下标移除办法
   * @param o
   * @return
   */
  @Override
  public boolean remove(E o) {if (o == null) {for (int index = 0; index < size; index++)
        if (elementData[index] == null) {remove(index);
          return true;
        }
    } else {for (int index = 0; index < size; index++)
        if (o.equals(elementData[index])) {remove(index);
          return true;
        }
    }
    return false;
  }

  /**
   * 移除下标为 index 的数据
   * @param index
   * @return
   */
  @Override
  public boolean remove(int index) {
    // 须要被挪动的数据个数
    int numMoved = size - index - 1;
    if (numMoved > 0)
      System.arraycopy(elementData, index+1, elementData, index,
          numMoved);
    elementData[--size] = null;

    return true;
  }

  @Override
  public boolean append(E o) {return add(o);
  }

  @Override
  public int size() {return size;}

  @Override
  public boolean isEmpty() {return size == 0;}

  @Override
  public boolean contain(E o) {if (o == null) {for (int index = 0; index < size; index++)
        if (elementData[index] == null) {return true;}
    } else {for (int index = 0; index < size; index++)
        if (o.equals(elementData[index])) {return true;}
    }
    return false;
  }

  @Override
  public String toString() {if (size <= 0)
      return "[]";

    StringBuilder builder = new StringBuilder();
    builder.append("[");
    for (int index = 0; index < size; index++) {builder.append(elementData[index].toString() + ",");
    }
    builder.delete(builder.length() - 2, builder.length());
    builder.append("]");
    return builder.toString();}
    
  @Override
  public boolean set(int index, E o) {elementData[index] = o;
    return true;
  }


  public static void main(String[] args) {MyArrayList<Integer> list = new MyArrayList<>();
    for (int i = 0; i < 15; i++) {list.add(-i);
    }
    System.out.println(list.contain(5));
    System.out.println(list);
    list.remove(new Integer(-6));
    System.out.println(list);
    System.out.println(list.elementData.length);
    list.add(5, 99999);
    System.out.println(list);
    System.out.println(list.contain(99999));
  }
}

本篇文章咱们介绍了 ArrayList 的外部原理，并且咱们实现了一个本人的简略数组容器 MyArrayList，然而咱们还有一些内容没有波及，比方clone、equals 和迭代器，这些内容咱们下期剖析 ArrayList 源码再进行剖析，我是 LeHung，咱们下期再见！！！

关注公众号：一无是处的钻研僧，理解更多计算机常识。

正文完
数据结构和算法
2022-07-06
 0
关于数据结构和算法:linear-list-链式存储方式经典问题-判定链表中有无cycle-以及-cycle-entrance-附数学推导
关于数据结构和算法:数据结构和算法二复杂度分析
关于数据结构和算法:你以为只是简单的排序一
关于数据结构和算法:数据结构选择排序

站内搜索

-「」