深入浅出ArrayList实现

2019年08月22日 网络转载 Comments Off on 深入浅出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);

Copyright © 知乐思维 保留所有权利.   Ality主题 粤ICP备14062485

用户登录

分享到: