首页 > 资讯 > 后端开发 > 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://www.lsjlt.com/news/153694.html(转载时请注明来源链接)

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

本篇文章演示代码以及资料文档资料下载

下载Word文档到电脑，方便收藏和打印～

下载Word文档

去做题

猜你喜欢

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

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

99+

2024-04-02
Java中ArrayList与顺序表的定义与实现方法

目录1、线性表定义特征2、顺序表定义实现打印数组新增元素判断是否包含某个元素查找元素获取pos位置的元素更改pos位置的值删除操作获取顺序表长度清空顺序表3、ArrayList简介：...

99+

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

探秘ArrayList源码：Java动态数组的背后实现一、成员变量二、构造器1、默认构造器2、带初始容量参数构造器3、指定collection元素参数构造器三、add()方法扩容机制四、场景分析1、对于ensureExpli...

99+

2023-08-16

java 开发语言算法数据结构
VBS如何实现ArrayList Class vbs中的数组类

这篇文章主要为大家展示了“VBS如何实现ArrayList Class vbs中的数组类”，内容简而易懂，条理清晰，希望能够帮助大家解决疑惑，下面让小编带领大家一起研究并学习一下“VBS如何实现ArrayList Class vbs中的数组...

99+

2023-06-08
Java实现计算器设计

本文实例为大家分享了Java实现计算器设计的具体代码，供大家参考，具体内容如下需求分析目的是实现一个基于Java的可以求解带括号加减乘除表达式的带界面的计算器。 ...

99+

2024-04-02
java 中ArrayList迭代的两种实现方法

java 中ArrayList迭代的两种实现方法Iterator与for语句的结合来实现，代码很简单，大家参考下。实现代码：package cn.us; import java.util.ArrayList; import java.uti...

99+

2023-05-31

java arraylist 迭代
设计与实现Golang中链表的数据结构

Golang中链表数据结构的设计与实现引言：链表是一种常见的数据结构，用于存储一系列的节点。每个节点包含数据和指向下一个节点的指针。在Golang中，我们可以通过使用结构体和指针来实现链表。链表的设计与结...

99+

2024-01-29
如何理解Java容器中ArrayList的源码分析

这篇文章给大家介绍如何理解Java容器中List的源码分析，内容非常详细，感兴趣的小伙伴们可以参考借鉴，希望对大家能有所帮助。如果没有特别说明，以下源码分析基于 JDK 1.8。一、ArrayList1. 概览实现了 RandomAcces...

99+

2023-06-05
Java中ArrayList与顺序表的概念与使用实例

目录前言泛型(Generic)泛型的引入泛型的基本概念包装类(Wrapper Class)包装类的引入基本数据类型与包装类的对应关系ArrayList与顺序表ArrayList简介A...

99+

2024-04-02
如何理解Java容器中的设计模式

如何理解Java容器中的设计模式，针对这个问题，这篇文章详细介绍了相对应的分析和解答，希望可以帮助更多想解决这个问题的小伙伴找到更简单易行的方法。一、迭代器模式Collection 继承了 Iterable 接口，其中的 iterator(...

99+

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

在Unix系统中，ASP容器和数组的无缝集成是一个非常常见的需求。ASP容器是一种用于运行ASP（Active Server Pages）应用程序的环境，而数组则是一种非常有用的数据结构，它可以存储多个值。在本文中，我们将介绍如何在Unix...

99+

2023-09-16

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

目录前言定义及相关术语API设计代码实现前言在实际生活中，很多应用相关的图都是有方向性的，最直观的就是网络，可以从A页面通过链接跳转到B页面，那么a和b连接的方向是a->b,...

99+

2022-11-13

Java数据结构有向图 Java有向图
PHP中的Spring容器如何实现数组和容器的依赖注入？

在PHP中，依赖注入是一种常见的实现方式，常用于解决对象之间的依赖关系。Spring容器是一个非常强大的依赖注入框架，它提供了一种灵活的方式来注入对象之间的依赖关系。在本文中，我们将介绍如何在PHP中使用Spring容器实现数组和容器的依...

99+

2023-06-19

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

随着计算机硬件的发展，多核处理器已经成为了主流。这也意味着，在编写Java程序时，我们需要更多地考虑并发编程。在这篇文章中，我们将探讨如何使用Java中的数组容器来实现高效率的并发编程。 Java中的数组容器在Java中，数组容器指的是...

99+

2023-09-19

并发数组容器
java怎么实现计数器

在Java中，可以使用变量来实现计数器。首先，声明一个整型变量来存储计数器的值，然后利用循环结构不断对计数器进行更新。以下是一个简单...

99+

2023-08-31

java
java整数与byte数组的转换实现代码

java整数与byte数组的转换实现代码这里对java中整数与byte数组的转换进行了实现，平时的项目中很少...

99+

2023-05-31

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

数组是一种常见的数据结构，用于存储一系列相同类型的数据。在Python中，我们可以使用数组容器对象来实现数组。本文将介绍数组容器对象在Python中的实现方式，并提供一些演示代码，帮助读者更好地理解和应用该容器对象。一、数组容器对象的定义...

99+

2023-08-20

数组容器对象
java中分组统计的三种实现方式

平时工作中，很多时候都会用到对数据进行分组操作，例如一个学生对象，有班级、名字、性别、分数等，需要按班级分组统计，该怎么操作呢？一个合理的算法可以提升不少效率。大家看一下下面的案例...

99+

2024-04-02
Java数据结构之栈与综合计算器的实现

目录1.栈1.1 栈的简介1.2 使用数组模拟栈1.3 栈的测试2.综合计算器的实现2.1 需求简介2.2 详细思路及分步图解2.3 完整代码及测试1.栈 1.1 栈的简介栈（st...

99+

2022-11-13

Java 栈综合计算器 Java 栈 Java 综合计算器
java熔断器设计如何实现

这篇文章主要介绍“java熔断器设计如何实现”，在日常操作中，相信很多人在java熔断器设计如何实现问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”java熔断器设计如何实现”的疑惑有所帮助！接下来，请跟着小编...

99+

2023-06-02