用Java实现变长数组ArrayList

互联网 2021/4/9 1:25:17

微信公众号:Java随笔录 关注可了解更多Java相关的技术分享。问题或建议,欢迎公众号留言!文章目录 前言思考代码实现用法公众号前言 在上一篇文章《用Java实现一个栈》中,小录实现了一个比较通用的栈(Stack),实现了基本的栈操作,包括初始化、入栈、出栈、获取栈顶元…

微信公众号:Java随笔录
关注可了解更多Java相关的技术分享。问题或建议,欢迎公众号留言!

文章目录

      • 前言
      • 思考
      • 代码实现
      • 用法
      • 公众号

前言

在上一篇文章《用Java实现一个栈》中,小录实现了一个比较通用的栈(Stack),实现了基本的栈操作,包括初始化、入栈、出栈、获取栈顶元素、判断栈是否为空、获取栈内元素的个数等,另外还支持泛型。

延续上篇文章的主题,小录又实现了变长数组(ArrayList),好好回顾一下基础的数据结构知识。

思考

开始代码实现之前,我们先大致列一下要实现变长数组所需要的方法:初始化数组、添加元素、获取指定位置的元素、设置指定位置的元素、获取数组的长度、判断是否为空等。这些是之前实现栈时就考虑过的,另外数组还需要移除指定位置的元素。

这次仍然使用泛型来实现变长数组,以便使用各种数据类型。我们还要把一些内容提出为常量,把一些公用方法提出来。同时拓展一些方法,比如是否包含指定元素、返回指定元素的索引(如果不存在,则返回-1;如果存在,则返回第一个找到的元素的索引)、返回第一个元素、返回最后一个元素。

代码实现

import java.util.Arrays;

/**
 * @author jiangnanmax
 * @email jiangnanmax@gmail.com
 * @description ArrayList
 * @date 2021/3/29
 **/

public class ArrayList<E> {

    /**
     * 默认初始化数组长度
     */
    private static final int INITIAL_CAPACITY = 10;

    private Object[] array;
    private int size = 0;

    public ArrayList() {
        this(INITIAL_CAPACITY);
    }

    public ArrayList(int initial) {
        if (initial <= 0) {
            throw new IllegalArgumentException("Illegal Capacity: " + initial);
        }
        array = new Object[initial];
    }

    /**
     * 添加新元素
     *
     * @param e
     */
    public E add(E e) {
        ensureCapacityHelper(size + 1);
        array[size++] = e;
        return e;
    }

    /**
     * 返回制定索引位置的元素
     *
     * @param index
     * @return
     */
    public E get(int index) {
        rangeCheck(index);
        return elementData(index);
    }

    /**
     * 设置指定索引位置的元素
     *
     * @param index
     * @param element
     * @return
     */
    public E set(int index, E element) {
        rangeCheck(index);
        E oldValue = elementData(index);
        array[index] = element;
        return oldValue;
    }

    /**
     * 删除指定索引位置的元素
     * 该元素的后续元素需要前移
     *
     * @param index
     * @return
     */
    public E remove(int index) {
        rangeCheck(index);
        E oldValue = elementData(index);
        int numMoved = size - index - 1;
        if (numMoved > 0) {
            System.arraycopy(array, index + 1, array, index, numMoved);
        }
        array[--size] = null; // 设置为null,GC会回收原始的内存空间
        return oldValue;
    }

    /**
     * 清空容器
     */
    public void clear() {
        for (int i = 0; i < size; i++) {
            array[i] = null; // 同样设置为null,让GC工作
        }
    }

    /**
     * 找到指定元素在容器中的索引位置
     * 不存在则返回-1
     *
     * @param e
     * @return
     */
    public int indexOf(E e) {
        if (e == null) {
            for (int i = 0; i < size; i++) {
                if (array[i] == null) {
                    return i;
                }
            }
        } else {
            for (int i = 0; i < size; i++) {
                if (e.equals(array[i])) {
                    return i;
                }
            }
        }
        return -1;
    }

    /**
     * 判断指定元素是否存在于容器中
     *
     * @param e
     * @return
     */
    public boolean contains(E e) {
        return indexOf(e) != -1;
    }

    /**
     * 获取容器中的第一个元素
     *
     * @return
     */
    public E getFirst() {
        return get(0);
    }

    /**
     * 获取容器中的最后一个元素
     *
     * @return
     */
    public E getLast() {
        return get(size - 1);
    }

    /**
     * 获取当前容器中的元素个数
     *
     * @return
     */
    public int size() {
        return size;
    }

    /**
     * 判断容器是否为空
     *
     * @return
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 确保容器的容量够用
     *
     * @param minCapacity
     */
    private void ensureCapacityHelper(int minCapacity) {
        if (minCapacity > array.length) {
            grow();
        }
    }

    /**
     * 扩大容器的容量
     *
     */
    private void grow() {
        int oldCapacity = array.length;
        int newCapacity =  oldCapacity << 1;
        if (newCapacity < oldCapacity) {
            throw new OutOfMemoryError();
        } else {
            array = Arrays.copyOf(array, newCapacity);
        }
    }

    /**
     * 范围检查
     *
     * @param index
     */
    private void rangeCheck(int index) {
        if (index >= size) {
            throw new IndexOutOfBoundsException("Illegal Index: " + index);
        }
    }

    /**
     * 由于使用了泛型,返回元素时需要做强转
     * 这里抽象出一个功能函数,获取指定索引位置的元素
     *
     * @param index
     * @return
     */
    private E elementData(int index) {
        return (E) array[index];
    }

}

用法

public class TestArrayList {

    public static void main(String[] args) {
        ArrayList<String> stringArrayList = new ArrayList<>();
        stringArrayList.add("欢迎关注");
        stringArrayList.add("Java随笔录");

        System.out.println(stringArrayList.get(0));
        System.out.println(stringArrayList.get(1));
    }

}

/**
输出:

欢迎关注
Java随笔录

 */

公众号

  • 关注公众号,即时接收关于Java的技术分享!

随时随地学软件编程-关注百度小程序和微信小程序
关于找一找教程网

本站文章仅代表作者观点,不代表本站立场,所有文章非营利性免费分享。
本站提供了软件编程、网站开发技术、服务器运维、人工智能等等IT技术文章,希望广大程序员努力学习,让我们用科技改变世界。
[用Java实现变长数组ArrayList]http://www.zyiz.net/tech/detail-154086.html

上一篇:2020学习Java开发有前途吗?看看资深程序员怎么说

下一篇:Tomcat源码解析

赞(0)

共有 条评论 网友评论

验证码: 看不清楚?
    关注微信小程序
    程序员编程王-随时随地学编程

    扫描二维码或查找【程序员编程王】

    可以随时随地学编程啦!

    技术文章导航 更多>
    扫一扫关注最新编程教程