AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

【动手实现系列】手撕ArrayList

2023-09-14 52
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 【动手实现系列】手撕ArrayList

@[toc]

说到前面

学过Java的同学就会知道，ArrayList是Java中的集合。
ArrayList就是动态数组，它的底层是数组实现，我们来阅读一下ArrayList的源码。
先看它的无参构造方法：

    public ArrayList() {
   
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

其中的DEFAULTCAPACITY_EMPTY_ELEMENTDATA是一个Object类型的空数组。

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {
   };

所以通过无参构造方法就创建了一个Object类型的空数组，再看add()方法：

    public boolean add(E e) {
   
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

在往数组中添加元素之前，它调用了ensureCapacityInternal()方法，所以来看看该方法：

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

该方法又继续调用了ensureExplicitCapacity()方法，通过calculateCapacity()方法计算出容量：

    private static int calculateCapacity(Object[] elementData, int minCapacity) {
   
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
   
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }

从传递过来的参数和DEFAULT_CAPACITY中找出最大值，方法参数为当前数组的大小，DEFAULT_CAPACITY为数组的初始容量：

private static final int DEFAULT_CAPACITY = 10;

综上所述，ArrayList先初始化了一个空数组，然后在添加元素之前先申请足够的内存空间，初始申请的容量为10。

其它方法比较简单，就不一一分析了。
由于ArrayList是数组的实现，所以查找快，但增删慢。

实现ArrayList

数据结构专栏的文章已经更新了好几篇了，本篇文章我们就来实现一下ArrayList，检验一下自己的学习进度，操作类似于顺序表，所以如果你把顺序表掌握了，那么实现ArrayList就会很简单。

基本操作

我们照着ArrayList的API，把它的方法基本实现一遍：

结构定义

#define InitializeSize 10        //初始容量为10

typedef struct{
   
    int *data;        //动态数组
    int length;        //有效元素长度
    int size;        //预分配数组大小
}ArrayList,*PArrayList;

该结构共有三个变量，第一个data表示动态数组，第二个length表示集合的当前元素个数，第三个size表示集合的最大容量。

初始化集合

前面分析了ArrayList的初始化方式，这里我们自己实现的话可以简单一点，初始直接申请容量为10的数组内存，代码实现如下：

//初始化集合
ArrayList CreateList(){
   
    ArrayList list;
    //分配动态数组内存
    list.data = (int*) malloc(sizeof(int) * InitializeSize);
    if(list.data == NULL){
   
        exit(-1);
    }
    //初始化长度和大小
    list.length = 0;
    list.size = InitializeSize;
    return list;
}

对应于ArrayList的无参构造方法。

初始化指定容量大小的集合

ArrayList还有指定容量大小的构造方法，通过传入的参数申请数组内存空间：

//构造一个具有指定初始容量的空列表
ArrayList CreateListOfInitialCapacity(int initialCapacity){
   
    ArrayList list;
    //分配动态数组内存
    list.data = (int*) malloc(sizeof(int) * initialCapacity);
    if(list.data == NULL){
   
        exit(-1);
    }
    //初始化长度和大小
    list.length = 0;
    list.size = initialCapacity;
    return list;
}

这个很简单，稍微修改一下即可。

添加元素

接下来我们实现ArrayList的add()方法，add()方法分为两种：

  1. 将元素添加到集合中的指定位置
  2. 将元素直接添加到集合尾部

将元素添加到集合中的指定位置

在添加元素之前，我们需要判断当前集合是否满，如果满了，则申请内存空间，我们就规定申请原来数组的两倍内存即可：

int AddOfIndexList(PArrayList pList,int pos,int val){
   
    int i;
    //判断pos值的合法性
    if(pos < 0 || pos > pList->length){
   
        return 0;
    }
    //调用扩容函数
    CapacityList(pList);
    //将插入位置后面的元素都向后移动一位
    for(i = pList->length;i > pos;--i){
   
        //元素后移
        pList->data[i] = pList->data[i - 1];
    }
    //插入元素值
    pList->data[pos] = val;
    //有效元素长度加1
    pList->length++;
    return 1;//添加成功，返回1
}

先判断指定的位置是否符合当前集合，然后调用扩容函数，接着讲插入位置后面的元素都向后移动一位，最后将指定位置的元素值修改为添加的元素值，记得集合元素个数加1。

下面是扩容函数：

void CapacityList(PArrayList pList){
   
    int *tmp, i, *p, *q;
    //若有效元素长度等于数组大小，则为集合扩容
    if (pList->length >= pList->size) {
   
        //申请原数组两倍的存储空间作为新集合
        tmp = (int *)malloc(sizeof(int) * pList->size * 2);
        //变量p暂时存放原数组
        p = pList->data;
        //变量q暂时存放新数组
        q = tmp;
        //将原数组的元素值复制到新数组
        for (i = 0; i < pList->length; i++) {
   
            //复制元素
               *q = *p;
               //地址后移
            p++;
            q++;
        }
        //释放原数组内存
        free(pList->data);
        //集合的数组指针指向新数组
        pList->data = tmp;
        //数组大小变为原来的两倍
        pList->size = pList->size * 2;
    }
}

来分析一下，首先我们需要判断当前集合是否满了，判断条件为length == size，也就是当集合中的元素个数等于集合的最大容量时，说明集合满了。此时就去申请原数组的两倍内存空间作为新集合。

这里需要注意的是要用两个变量去分别存储原数组和新数组，然后通过循环将原数组的元素值复制到新数组中，最后释放原数组的内存，然后让data指向新数组，记得集合容量乘2(如果不用变量存储，会直接改变两个数组的地址，从而操作失败)。

将元素直接添加到集合尾部

添加到集合尾部就很简单了，直接看代码：

void AddList(PArrayList pList,int val){
   
    //调用AddListAsLocate()函数即可，位置为有效元素长度
    AddOfIndexList(pList,pList->length,val);
}

这就是为什么我要先实现指定位置的元素插入了，这样在直接添加到集合尾部的函数中直接调用原先的函数就可以了，位置为集合的尾部。

移除集合中的所有元素

移除集合中的所有元素非常简单，直接将数组中的所有元素看做无效即可，将元素个数置为0：

void ClearList(PArrayList pList){
   
    //将有效元素长度置为0
    pList->length = 0;
}

返回集合中首次出现的指定元素的索引

int IndexOfList(PArrayList pList,int val){
   
    int i;
    //遍历集合中的元素值
    for(i = 0;i < pList->length;++i){
   
        //查找元素值
        if(pList->data[i] == val)
            return i;
    }
    return 0;
}

通过遍历集合中的所有元素来匹配指定的元素值，若匹配成功，则返回索引，若无匹配成功，则返回0。

查找集合中是否包含指定的元素

int ContainsList(PArrayList pList,int val){
   
    //调用IndexOfList()函数
    if(IndexOfList(pList,val))
        return 1;
    else
        return 0;
}

该功能我们只需调用IndexOfList()函数即可，若返回值为0，则说明集合中没有指定的元素。

返回集合中指定位置上的元素

int GetList(PArrayList pList,int pos){
   
    //判断pos值的合法性
    if(pos < 0 || pos > pList->length - 1){
   
        return 0;
    }
    //返回元素值
    return pList->data[pos];
}

某些操作非常简单，我就不分析了。

判断集合是否为空

int ListEmpty(PArrayList pList){
   
    //判断集合的有效元素长度是否为0
    if(pList->length == 0)
        return 1;
    else
        return 0;
}

返回集合中最后一次出现的指定元素的索引

返回集合中指定元素最后一次出现的位置，我们可以从尾部到头部遍历集合，然后一一匹配元素值：

int LastIndexOfList(PArrayList pList,int val){
   
    int i;
    //从尾端开始遍历集合中的元素值
    for(i = pList->length - 1;i >= 0;--i){
   
        //查找元素值
        if(pList->data[i] == val)
            return i;
    }
    return 0;
}

移除集合中指定位置上的元素

int RemoveOfIndexList(PArrayList pList,int pos){
   
    int i,val;
    //判断pos值的合法性
    if(pos < 0 || pos > pList->length - 1){
   
        return 0;
    }
    //将删除位置后面的元素都向前移动一位
    val = pList->data[pos];        //保存删除位置的元素值
    for(i = pos;i < pList->length;++i){
       
        pList->data[i] = pList->data[i + 1];
    }
    //有效元素长度减1
    pList->length--;
    return val;                    //返回删除的元素值
}

移除元素需要先将指定位置后面的元素都向前移动一位，在这之前，先将指定位置的元素值保存，否则将被后面的元素覆盖，最后记得元素个数减1。

移除集合中首次出现的指定元素（如果存在）

int RemoveList(PArrayList pList,int val){
   
    int i;
    //遍历集合中的元素
    for (i = 0; i < pList->length; ++i){
   
        if(pList->data[i] == val){
   
            //调用RemoveOfIndexList()函数
            RemoveOfIndexList(pList,i);
            return 1;
        }
    }
    return 0;
}

用指定的元素替代集合中指定位置上的元素

int SetList(PArrayList pList,int pos,int val){
   
    //判断pos值的合法性
    if(pos < 0 || pos > pList->length - 1){
   
        return 0;
    }
    //取出列表原位置上的元素
    int oldVal = pList->data[pos];
    //替换列表原位置上的元素
    pList->data[pos] = val;
    return oldVal;            //返回原位置上的元素
}

返回集合中的元素个数

int ListSize(PArrayList pList){
   
    //返回集合大小
    return pList->length;
}

移除集合中索引在 fromIndex（包括）和 toIndex（不包括）之间的所有元素

void RemoveRangeList(PArrayList pList,int fromIndex,int toIndex){
   
    int i,size;
    //判断fromIndex和toIndex值的合法性
    if(fromIndex < 0 || toIndex > pList->length){
   
        return;
    }
    //size为需要移除的元素个数
    size = toIndex - fromIndex; 
    for(i = 0;i < size;++i){
   
        //调用RemoveOfIndexList()函数，从fromIndex位置开始，删除size个元素
        RemoveOfIndexList(pList,fromIndex);
    }
}

来分析一下该函数吧，假设我有这样一个序列{1,2,3,4,5}，要移除索引为0到3的元素值，该如何实现呢？
首先我们移除索引为0的元素值1，按道理我们需要移除索引为1的元素值2，但是需要注意了，当你移除索引为0的元素值1后，序列就变为{2,3,4,5}，此时移除元素2的索引仍然为0。通过分析得知，我们只需知道需要移除的元素个数，然后从fromIndex开始，移除指定的元素个数即可。

将集合的容量调整为集合的当前大小

void TrimToSizeList(PArrayList pList){
   
    int *tmp, i, *p, *q;
    //申请集合大小的存储空间
    tmp = (int*)malloc(sizeof(int) * pList->length);
    //变量p暂时存放原数组
    p = pList->data;
    //变量q暂时存放新数组
    q = tmp;
    //将原数组的元素复制到新数组
     for (i = 0; i < pList->length; i++) {
   
        //复制元素
        *q = *p;
        //地址后移
        p++;
        q++;
    }
    //释放原数组内存
    free(pList->data);
    //集合的数组指针指向新数组
    pList->data = tmp;
    //数组大小变为当前列表的大小
    pList->size = pList->length;
}

这里和扩容函数的操作类似，就不具体分析了。

最后

到这里，关于ArrayList的实现就结束了，还有部分ArrayList的方法未实现，大家可以自己尝试一下。

源代码

//C实现ArrayList

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>

#define InitializeSize 10

typedef struct{
   
    int *data;        //动态数组
    int length;        //有效元素长度
    int size;        //预分配数组大小
}ArrayList,*PArrayList;

//函数声明
ArrayList CreateList();//初始化集合
ArrayList CreateListOfInitialCapacity(int initialCapacity);//构造一个具有指定初始容量的空列表
void AddList(PArrayList pList,int val);//将指定的元素添加到此列表的尾部
int AddOfIndexList(PArrayList pList,int pos,int val);//将指定的元素插入此列表中的指定位置
void ClearList(PArrayList pList);//移除此集合中的所有元素
int ContainsList(PArrayList pList,int val);//如果此列表中包含指定的元素，则返回 1
int GetList(PArrayList pList,int pos);//返回此列表中指定位置上的元素
int IndexOfList(PArrayList pList,int val);//返回此列表中首次出现的指定元素的索引，或如果此列表不包含元素，则返回 0
int ListEmpty(PArrayList pList);//如果此列表中没有元素，则返回 1
int LastIndexOfList(PArrayList pList,int val);//返回此列表中最后一次出现的指定元素的索引，或如果此列表不包含索引，则返回 0
int RemoveOfIndexList(PArrayList pList,int pos);//移除此列表中指定位置上的元素
int RemoveList(PArrayList pList,int val);//移除此列表中首次出现的指定元素(如果存在)
void RemoveRangeList(PArrayList pList,int fromIndex,int toIndex);//移除列表中索引在 fromIndex(包括)和 toIndex(不包括)之间的所有元素
int SetList(PArrayList pList,int pos,int val);//用指定的元素替代此列表中指定位置上的元素
int ListSize(PArrayList pList);//返回此列表中的元素数
int* ListToArray(PArrayList pList);//按适当顺序(从第一个到最后一个元素)返回包含此列表中所有元素的数组
void TrimToSizeList(PArrayList pList);//将此 ArrayList 实例的容量调整为列表的当前大小。应用程序可以使用此操作来最小化 ArrayList 实例的存储量
void TraverseList(PArrayList pList);//集合的遍历操作


int main(int argc, char const *argv[])
{
   
    /* code */
    return 0;
}

//初始化集合
ArrayList CreateList(){
   
    ArrayList list;
    //分配动态数组内存
    list.data = (int*) malloc(sizeof(int) * InitializeSize);
    if(list.data == NULL){
   
        exit(-1);
    }
    //初始化长度和大小
    list.length = 0;
    list.size = InitializeSize;
    return list;
}

//为集合扩容(通常在往集合中添加元素时进行集合扩容)
void CapacityList(PArrayList pList){
   
    int *tmp, i, *p, *q;
    //若有效元素长度等于数组大小，则为集合扩容
    if (pList->length >= pList->size) {
   
        //申请原数组两倍的存储空间作为新集合
        tmp = (int *)malloc(sizeof(int) * pList->size * 2);
        //变量p暂时存放原数组
        p = pList->data;
        //变量q暂时存放新数组
        q = tmp;
        //将原数组的元素值复制到新数组
        for (i = 0; i < pList->length; i++) {
   
            //复制元素
               *q = *p;
               //地址后移
            p++;
            q++;
        }
        //释放原数组内存
        free(pList->data);
        //集合的数组指针指向新数组
        pList->data = tmp;
        //数组大小变为原来的两倍
        pList->size = pList->size * 2;
    }
}

//构造一个具有指定初始容量的空列表
ArrayList CreateListOfInitialCapacity(int initialCapacity){
   
    ArrayList list;
    //分配动态数组内存
    list.data = (int*) malloc(sizeof(int) * initialCapacity);
    if(list.data == NULL){
   
        exit(-1);
    }
    //初始化长度和大小
    list.length = 0;
    list.size = initialCapacity;
    return list;
}

//将指定的元素插入此列表中的指定位置
int AddOfIndexList(PArrayList pList,int pos,int val){
   
    int i;
    //判断pos值的合法性
    if(pos < 0 || pos > pList->length){
   
        return 0;
    }
    //调用扩容函数
    CapacityList(pList);
    //将插入位置后面的元素都向后移动一位
    for(i = pList->length;i > pos;--i){
   
        //元素后移
        pList->data[i] = pList->data[i - 1];
    }
    //插入元素值
    pList->data[pos] = val;
    //有效元素长度加1
    pList->length++;
    return 1;//添加成功，返回1
}

//将指定的元素添加到此列表的尾部
void AddList(PArrayList pList,int val){
   
    //调用AddListAsLocate()函数即可，位置为有效元素长度
    AddOfIndexList(pList,pList->length,val);
}

//如果此列表中没有元素，则返回 1
int ListEmpty(PArrayList pList){
   
    //判断集合的有效元素长度是否为0
    if(pList->length == 0)
        return 1;
    else
        return 0;
}

//集合的遍历操作
void TraverseList(PArrayList pList){
   
    int i;
    //判断集合是否为空
    if(ListEmpty(pList)){
   
        //输出空集合
        printf("[]\n");
    }
    for(i = 0;i < pList->length;++i){
   
        //输出元素值
        printf("%d\t",pList->data[i]);
    }
}

//移除此集合中的所有元素
void ClearList(PArrayList pList){
   
    //将有效元素长度置为0
    pList->length = 0;
}

//返回此列表中指定位置上的元素
int GetList(PArrayList pList,int pos){
   
    //判断pos值的合法性
    if(pos < 0 || pos > pList->length - 1){
   
        return 0;
    }
    //返回元素值
    return pList->data[pos];
}

//返回此列表中首次出现的指定元素的索引，或如果此列表不包含元素，则返回 0
int IndexOfList(PArrayList pList,int val){
   
    int i;
    //遍历集合中的元素值
    for(i = 0;i < pList->length;++i){
   
        //查找元素值
        if(pList->data[i] == val)
            return i;
    }
    return 0;
}

//如果此列表中包含指定的元素，则返回 1
int ContainsList(PArrayList pList,int val){
   
    //调用IndexOfList()函数
    if(IndexOfList(pList,val))
        return 1;
    else
        return 0;
}

//返回此列表中最后一次出现的指定元素的索引，或如果此列表不包含索引，则返回 0
int LastIndexOfList(PArrayList pList,int val){
   
    int i;
    //从尾端开始遍历集合中的元素值
    for(i = pList->length - 1;i >= 0;--i){
   
        //查找元素值
        if(pList->data[i] == val)
            return i;
    }
    return 0;
}

//移除此列表中指定位置上的元素
int RemoveOfIndexList(PArrayList pList,int pos){
   
    int i,val;
    //判断pos值的合法性
    if(pos < 0 || pos > pList->length - 1){
   
        return 0;
    }
    //将删除位置后面的元素都向前移动一位
    val = pList->data[pos];        //保存删除位置的元素值
    for(i = pos;i < pList->length;++i){
       
        pList->data[i] = pList->data[i + 1];
    }
    //有效元素长度减1
    pList->length--;
    return val;                    //返回删除的元素值
}

//移除此列表中首次出现的指定元素(如果存在)
int RemoveList(PArrayList pList,int val){
   
    int i;
    //遍历集合中的元素
    for (i = 0; i < pList->length; ++i){
   
        if(pList->data[i] == val){
   
            //调用RemoveOfIndexList()函数
            RemoveOfIndexList(pList,i);
            return 1;
        }
    }
    return 0;
}

//移除列表中索引在 fromIndex(包括)和 toIndex(不包括)之间的所有元素
void RemoveRangeList(PArrayList pList,int fromIndex,int toIndex){
   
    int i,size;
    //判断fromIndex和toIndex值的合法性
    if(fromIndex < 0 || toIndex > pList->length){
   
        return;
    }
    //size为需要移除的元素个数
    size = toIndex - fromIndex; 
    for(i = 0;i < size;++i){
   
        //调用RemoveOfIndexList()函数，从fromIndex位置开始，删除size个元素
        RemoveOfIndexList(pList,fromIndex);
    }
}

//用指定的元素替代此列表中指定位置上的元素
int SetList(PArrayList pList,int pos,int val){
   
    //判断pos值的合法性
    if(pos < 0 || pos > pList->length - 1){
   
        return 0;
    }
    //取出列表原位置上的元素
    int oldVal = pList->data[pos];
    //替换列表原位置上的元素
    pList->data[pos] = val;
    return oldVal;            //返回原位置上的元素
}

//返回此列表中的元素数
int ListSize(PArrayList pList){
   
    //返回集合大小
    return pList->length;
}

//按适当顺序(从第一个到最后一个元素)返回包含此列表中所有元素的数组
int* ListToArray(PArrayList pList){
   
    int i;
    //创建新数组
    int *newData = (int*) malloc(sizeof(int) * pList->length);
    if(newData == NULL){
   
        exit(-1);
    }
    //将集合中的元素放入数组
    for(i = 0;i < pList->length;++i){
   
        newData[i] = pList->data[i];
    }
    return newData;        //返回数组
}

//将此 ArrayList 实例的容量调整为列表的当前大小。应用程序可以使用此操作来最小化 ArrayList 实例的存储量
void TrimToSizeList(PArrayList pList){
   
    int *tmp, i, *p, *q;
    //申请集合大小的存储空间
    tmp = (int*)malloc(sizeof(int) * pList->length);
    //变量p暂时存放原数组
    p = pList->data;
    //变量q暂时存放新数组
    q = tmp;
    //将原数组的元素复制到新数组
     for (i = 0; i < pList->length; i++) {
   
        //复制元素
        *q = *p;
        //地址后移
        p++;
        q++;
    }
    //释放原数组内存
    free(pList->data);
    //集合的数组指针指向新数组
    pList->data = tmp;
    //数组大小变为当前列表的大小
    pList->size = pList->length;
}
文章标签：
索引
Java
存储
API
梳中分的坤坤
目录
相关文章
青色忘川
|
存储 编译器 C++
【C++从0到王者】第三十五站：面试官让手撕红黑树，我直接向他秀一手手撕map与set
【C++从0到王者】第三十五站：面试官让手撕红黑树，我直接向他秀一手手撕map与set
青色忘川
81 0
JavaBuild
|
7月前
|
Java API
面试官上来就让手撕HashMap的7种遍历方式，当场愣住，最后只写出了3种
面试官上来就让手撕HashMap的7种遍历方式，当场愣住，最后只写出了3种
JavaBuild
47 1
王同学睡醒了
手撕面试题
手撕面试题
王同学睡醒了
52 0
叶秋学长
|
SQL IDE 算法
手撕代码是程序员的基本功吗？
现在众多企业都要求在面试中用“手撕代码”来考验应聘者的代码能力，你觉得手敲代码是否可以体现真实的基础实力？ 本期话题： 1、你觉得手撕代码是程序员的基本功吗？ 2、为什么会用“手撕代码”来考验程序员能力
叶秋学长
218 1
非同质前端札记
面试必考: 手撕代码系列(一)
面试必考: 手撕代码系列(一)
非同质前端札记
179 0
非同质前端札记
面试必问：手撕代码系列（二）
面试必问：手撕代码系列（二）
非同质前端札记
126 0
非同质前端札记
|
缓存 调度
手撕代码系列(四)
手撕代码系列(四)
非同质前端札记
93 0
非同质前端札记
手撕代码系列(三)
手撕代码系列(三)
非同质前端札记
64 0
六月的雨在钉钉
|
算法 程序员
手撕代码
手撕代码是什么
六月的雨在钉钉
491 0
sot57do6zp33o
|
存储 机器学习/深度学习 缓存
为什么要用HashMap？这样回答面试官直呼内行【手撕HashMap系列】
为什么要用HashMap？这样回答面试官直呼内行【手撕HashMap系列】
sot57do6zp33o
303 0
为什么要用HashMap？这样回答面试官直呼内行【手撕HashMap系列】