【动手实现系列】手撕ArrayList

2020-03-01 16:09 366人阅读评论(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()方法分为两种：

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

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

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

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

转载：https://blog.csdn.net/qq_42453117/article/details/103730462

查看评论

小言_互联网的博客