深入浅出ArrayList实现

ArrayList是一种以数组实现的List，与数组相比，它具有动态扩展的能力，因此也可称之为动态数组。

简易版C语言ArrayList

来源：连续存储-数组 郝斌老师-数据结构

#include <stdio.h>
#include <malloc.h>//包含了malloc函数
#include <stdlib.h>//包含了exit函数
#include <stdbool.h>//包含了bool
/*定义了一个数据类型，该数据类型的名字叫做struct Arr，
该数据类型含有三个成员，分别是pBase、len、cnt*/
struct Arr
{
    int *pBase; //存储的是数组的第一个元素的地址
    int len;  //数组所能容纳的最大元素的个数
    int cnt;//当前数组有效的元素的个数
};

void init_arr(struct Arr *pArr, int length);//对数组进行初始化,分号不能省
bool append_arr(struct Arr *pArr, int val); //末尾追加
bool insert_arr(struct Arr *pArr, int pose, int val);/*插入数据元素,（功能靠自己定义）
                                                     pose插入数据的位置，pose的值从1开始,表示下标为0的第一个位置开始，
                                                     若pose的值为4，表示在第四个元素的前面插入一个val的值*/
bool delete_arr(struct Arr *pArr, int pose,int *pVal);//删除数据元素,*pVal返回删除元素的值
bool is_empty(struct Arr *pArr);//判断数组是否为空
bool is_full(struct Arr *pArr);//判断数组是否满
void sort_arr(struct Arr *pArr);//对数组进行排序,冒泡排序
void show_arr(struct Arr *pArr);//输出函数
void inversion_arr(struct Arr *pArr);//倒置

int main(void)
{
    struct Arr arr;
    int val;
    //init_arr(arr);//error ，传输数据用指针，进行地址传输
    init_arr(&arr, 6);
    //printf("%d\n", arr.len);
    show_arr(&arr);
    append_arr(&arr, 1);
    append_arr(&arr, 2);
    append_arr(&arr, 8);
    append_arr(&arr, 6);
    append_arr(&arr, 23);
    append_arr(&arr, 9);
    show_arr(&arr);
    
    if (delete_arr(&arr, 2, &val))//括号中的delete操作参数，将val的地址发送给pVal
    {
        printf("删除成功！\n");
        printf("您删除的元素是: %d\n", val);
    }
    else
    {
        printf("删除失败！\n");
    }
    /*append_arr(&arr, 2);
    append_arr(&arr, 3);
    append_arr(&arr, 4);
    append_arr(&arr, 5);
    insert_arr(&arr, 3, 99);*/
    /*if (append_arr(&arr, 7))
    {
    printf("追加成功！\n");
    }
    else
    {
    printf("追加失败！\n");
    }*/
    show_arr(&arr);
    inversion_arr(&arr);
    printf("倒置之后的数组内容是：\n");
    show_arr(&arr);
    sort_arr(&arr);
    show_arr(&arr);
    return 0;
}
void init_arr(struct Arr *pArr, int length)
{
    pArr->pBase = (int *)malloc(sizeof(int) *length);
    if (NULL == pArr->pBase)//地址分配成成功，pBase为有效值，否则是NULL
    {
        printf("动态内存分配失败！\n");
        exit(-1);//终止整个程序
    }
    else
    {
        pArr->len = length;
        pArr->cnt = 0;
    }
    return;//init函数终止结束
}
bool is_empty(struct Arr *pArr)//判断数组是否为空
{
    if (0 == pArr->cnt)
        return true;
    else
        return false;

}
void show_arr(struct Arr *pArr)
{
    if (is_empty(pArr))/*(*pArr)表示结构体变量的地址的地址赋给了pArr，
                       pArr本身就是指针，存放的是地址所以传参的时候不需要取地址符*/
        printf("数组为空!\n");
    else
    {
        for (int i = 0; i < pArr->cnt; i++)
            printf("%d ", pArr->pBase[i]);
        printf("\n");
    }
}
/*伪函数
{
if (数组为空)
提示用户数组为空
else
输出数组有效内容
}*/
bool is_full(struct Arr *pArr)
{
    if (pArr->cnt == pArr->len)
        return true;
    else
        return false;

}
bool append_arr(struct Arr *pArr, int val)//追加元素
{
    if (is_full(pArr))
        return false;//满时返回false
                     //不满时追加
    pArr->pBase[pArr->cnt] = val;
    (pArr->cnt)++;
    return true;//表示添加元素成功
}
bool insert_arr(struct Arr *pArr, int pose, int val)//在pose的前面将val插入到数组里面
{
    int i;
    if (is_full(pArr))
        return false;
    if (pose<1 || pose>pArr->cnt + 1)
        return false;
    for (i = pArr->cnt - 1; i >= pose - 1; --i)
    {
        pArr->pBase[i + 1] = pArr->pBase[i];
    }
    pArr->pBase[pose - 1] = val;
    (pArr->cnt)++;
    return true;
}
bool delete_arr(struct Arr *pArr, int pose, int *pVal)
{
    int i;
    if (is_empty(pArr))
        return false;
    if (pose<1||pose>pArr->cnt)
        return false;
    *pVal = pArr->pBase[pose - 1];//先进行赋值，以免进行删除操作之后没有返回值
    //将val的地址赋给了pVal，则*pVal就是主函数的val即意味着等待着删除的元素
    //赋给了形参pVal指向的主函数的val
    for (i = pose; i < pArr->cnt; i++)//进行删除操作
    {
        pArr->pBase[i - 1] = pArr->pBase[i];
    }
    pArr->cnt--;//删除之后，有效个数减一
    return true;
}
void inversion_arr(struct Arr *pArr)
{
    int i = 0;
    int j = pArr->cnt - 1;
    int temp;
    while (i < j)
    {
        temp = pArr->pBase[i];
        pArr->pBase[i] = pArr->pBase[j];
        pArr->pBase[j] = temp;
        i++;
        j--;
    }
    return;
}
void sort_arr(struct Arr *pArr)
{
    int i, j, temp;
    for (i = 0; i < pArr->cnt; i++)
    {
        for (j = i + 1; j < pArr->cnt; j++)
        {
            if (pArr->pBase[i] > pArr->pBase[j])
            {
                temp = pArr->pBase[i];
                pArr->pBase[i] = pArr->pBase[j];
                pArr->pBase[j] = temp;
            }

        }
    }
}

在线C语言编译：https://c.runoob.com/compile/11

image.png

JAVA ArrayList源码

ArrayList

部分源码如下：

/**
 * 默认容量
 */
private static final int DEFAULT_CAPACITY = 10;

/**
 * 空数组，如果传入的容量为0时使用
 */
private static final Object[] EMPTY_ELEMENTDATA = {};

/**
 * 空数组，传传入容量时使用，添加第一个元素的时候会重新初始为默认容量大小
 */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/**
 * 存储元素的数组
 */
transient Object[] elementData; // non-private to simplify nested class access

/**
 * 集合中元素的个数
 */
private int size;

ArrayList(int initialCapacity)构造方法
传入初始容量，如果大于0就初始化elementData为对应大小，如果等于0就使用EMPTY_ELEMENTDATA空数组，如果小于0抛出异常。

public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        // 如果传入的初始容量大于0，就新建一个数组存储元素
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        // 如果传入的初始容量等于0，使用空数组EMPTY_ELEMENTDATA
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        // 如果传入的初始容量小于0，抛出异常
        throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
    }
}

ArrayList()构造方法
不传初始容量，初始化为DEFAULTCAPACITY_EMPTY_ELEMENTDATA空数组，会在添加第一个元素的时候扩容为默认的大小，即10。

public ArrayList() {
    // 如果没有传入初始容量，则使用空数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA
    // 使用这个数组是在添加第一个元素的时候会扩容到默认大小10
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

add(E e)方法
添加元素到末尾，平均时间复杂度为O(1)。

public boolean add(E e) {
    // 检查是否需要扩容
    ensureCapacityInternal(size + 1);
    // 把元素插入到最后一位
    elementData[size++] = e;
    return true;
}

private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

private static int calculateCapacity(Object[] elementData, int minCapacity) {
    // 如果是空数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA，就初始化为默认大小10
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    if (minCapacity - elementData.length > 0)
        // 扩容
        grow(minCapacity);
}

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    // 新容量为旧容量的1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 如果新容量发现比需要的容量还小，则以需要的容量为准
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 如果新容量已经超过最大容量了，则使用最大容量
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // 以新容量拷贝出来一个新数组
    elementData = Arrays.copyOf(elementData, newCapacity);
}

add(int index, E element)方法
添加元素到指定位置，平均时间复杂度为O(n)。

public void add(int index, E element) {
    // 检查是否越界
    rangeCheckForAdd(index);
    // 检查是否需要扩容
    ensureCapacityInternal(size + 1);
    // 将inex及其之后的元素往后挪一位，则index位置处就空出来了
    System.arraycopy(elementData, index, elementData, index + 1, size - index);
    // 将元素插入到index的位置
    elementData[index] = element;
    // 大小增1
    size++;
}

private void rangeCheckForAdd(int index) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

remove(int index)方法
删除指定索引位置的元素，时间复杂度为O(n)。

public E remove(int index) {
    // 检查是否越界
    rangeCheck(index);

    modCount++;
    // 获取index位置的元素
    E oldValue = elementData(index);

    // 如果index不是最后一位，则将index之后的元素往前挪一位
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index, numMoved);

    // 将最后一个元素删除，帮助GC
    elementData[--size] = null; // clear to let GC do its work

    // 返回旧值
    return oldValue;
}

System.arraycopy()

image.png

public static native void arraycopy(Object src,  int  srcPos,
                                        Object dest, int destPos,
                                        int length);

源码分析见：
https://blog.csdn.net/u011642663/article/details/49512643

（1）ArrayList内部使用数组存储元素，当数组长度不够时进行扩容，每次加一半的空间，ArrayList不会进行缩容；
（2）ArrayList支持随机访问，通过索引访问元素极快，时间复杂度为O(1)；
（3）ArrayList添加元素到尾部极快，平均时间复杂度为O(1);
（4）ArrayList添加元素到中间比较慢，因为要搬移元素，平均时间复杂度O(n)；
（5）ArrayList从尾部删除元素极快，时间复杂度为O(1)；
（6）ArrayList从中间删除元素比较慢，因为要搬移元素，平均时间复杂O(n)；