首页 > 资讯 > 后端开发 > Python >Java中数组容器(ArrayList)设的计与实现

477

分享到

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

2024-04-02 19:04:59 477人浏览八月长安

Python 官方文档：入门教程 => 点击学习

摘要

目录ArrayList为我们提供了哪些功能设计原理分析代码实现完整代码本篇文章主要跟大家介绍我们最常使用的一种容器ArrayList、Vector的原理，并且自己使用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> {

  
  boolean add(E o);

  
  boolean add(int index, E o);

  
  boolean remove(E o);

  
  boolean remove(int index);

  
  boolean append(E o);

  
  int size();

  
  boolean isEmpty();

  
  boolean contain(E o);

  
  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;
  }

  
  public void ensureCapacity(int capacity) {
    int candidateCapacity = findCapacity(capacity);
    if (elementData.length < candidateCapacity)
      grow(candidateCapacity);
  }

  
  private int findCapacity(int 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在指定下标插入数据。

首先将插入下标后的数据往后移动一个位置
然后在将数据放在指定下标的位置。

  
  @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。

首先先删除指定下标的数据。
然后将指定下标后的数据往前移动一个位置
在实际的操作过程中我们可以不删除，直接移动，这样也覆盖被插入位置的数据了。

  
  @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 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;

  
  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; // 将数组设置为空数组
  }

  
  public void ensureCapacity(int capacity) {
    int candidateCapacity = findCapacity(capacity);
    if (elementData.length < candidateCapacity)
      grow(candidateCapacity);
  }

  
  private int findCapacity(int minCapacity) {
    
    if (elementData == EMPTY_INSTANCE){
      return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return 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;
  }

  
  @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;
  }

  
  @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;
  }

  
  @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));
  }
}

以上就是Java中数组容器(ArrayList)设的计与实现的详细内容，更多关于Java数组容器的资料请关注编程网其它相关文章！

您可能感兴趣的文档:

--结束END--

本文标题: Java中数组容器(ArrayList)设的计与实现

本文链接: https://lsjlt.com/news/153694.html(转载时请注明来源链接)

有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

回答

如何调试操作系统的错误？
操作系统

2023-11-15发布

回答

操作系统中的I/O系统是如何实现的？
操作系统

2023-11-15发布

回答

如何实现操作系统的内存管理？
操作系统

2023-11-15发布

回答

什么是虚拟内存，它对操作系统有什么影响？
操作系统

2023-11-15发布

回答

ASP中的MVC架构和WebForms架构有什么区别和使用场景？
ASP.NET

2023-11-15发布

回答

ASP中的数据验证和数据校验有什么不同？
ASP.NET

2023-11-15发布

回答

ASP中的ADO对象和DAO对象有什么区别和使用方法？
ASP.NET

2023-11-15发布

回答

Node.js中的包管理器NPM是什么？如何使用它进行依赖管理？
node.js

2023-11-15发布

回答

Vue.js中的动态组件是什么？如何使用它来动态渲染组件？
VUE

2023-11-15发布

回答

如何使用Vue.js实现懒加载和预加载？
VUE

2023-11-15发布

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

目录

ArrayList为我们提供了哪些功能

设计原理分析

代码实现

完整代码

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

java中的数组（Array）与列表（ArrayList）的区别

Java中ArrayList与顺序表的定义与实现方法

VBS如何实现ArrayList Class vbs中的数组类

探秘ArrayList源码：Java动态数组的背后实现

Java实现计算器设计

java中的ArrayList与一般数组有什么区别？效率如何？

Java中ArrayList与顺序表的概念与使用实例

如何理解Java容器中ArrayList的源码分析

设计与实现Golang中链表的数据结构

如何理解Java容器中的设计模式

java 中ArrayList迭代的两种实现方法

dubbo-go 中的 TPS Limit 设计与实现

如何在 Unix 系统中实现 ASP 容器与数组的无缝集成？

PHP中的Spring容器如何实现数组和容器的依赖注入？

Java数据结构之有向图设计与实现详解

Redis | 第4章 Redis中的数据库《Redis设计与实现》

Java中的并发编程：如何利用数组容器实现高效率？

数组容器对象在Python中是如何实现的？

java怎么实现计数器

python分析数据的方法是什么

如何使用Python实现抽奖小程序

python copy函数的作用是什么

python ffmpeg模块怎么安装和使用

python进程池创建队列的方法是什么

python无法运行文件的原因有哪些

python can't open file报错怎么解决

python keyerror错误怎么解决

python字符串处理与应用的方法有哪些

python全局变量如何定义