用Java实现变长数组ArrayList

拼搏现实的明天。 2022-11-17 10:05 177阅读 0赞

> 微信公众号：**Java随笔录**  
> 关注可了解更多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的技术分享！

![20210207183855124.JPG][]

[Java]: https://jiangnanmax.blog.csdn.net/article/details/114989230
[20210207183855124.JPG]: /images/20221022/09f5cdca61f1434db87afc9b90478dbd.png