【动手实现系列】手撕ArrayList

不念不忘少年蓝@ 2023-06-25 08:12 1阅读 0赞

### 文章目录 ###

*  说到前面
 *  实现ArrayList
 *  基本操作
 *   *  结构定义
     *  初始化集合
     *  初始化指定容量大小的集合
     *  添加元素
     *   *  将元素添加到集合中的指定位置
         *  将元素直接添加到集合尾部
     *  移除集合中的所有元素
     *  返回集合中首次出现的指定元素的索引
     *  查找集合中是否包含指定的元素
     *  返回集合中指定位置上的元素
     *  判断集合是否为空
     *  返回集合中最后一次出现的指定元素的索引
     *  移除集合中指定位置上的元素
     *  移除集合中首次出现的指定元素（如果存在）
     *  用指定的元素替代集合中指定位置上的元素
     *  返回集合中的元素个数
     *  移除集合中索引在 fromIndex（包括）和 toIndex（不包括）之间的所有元素
     *  将集合的容量调整为集合的当前大小
 *  最后
 *  源代码

# 说到前面 #

学过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;
    }