数据结构—List底层_c# list底层

作者：羊村懒王 | 2024-06-15 13:03:07

踩

c# list底层

C#的list底层原理

1、List默认构造函数

C#底层的List用数组实现。

2、Add 方法：

直接在数组的末尾添加元素。时间复杂度n(1)。

3、EnsureCapacity 函数：扩容

假如添加元素时数组空间已满，则扩充一倍。（会造成空间浪费，且扩容时数组空间越大浪费越多）

3、Remove 方法

使用Remove方法时，先调用Indexof()方法，找到元素对应的下标

IndexOf实际上又调用的是Array.IndexOf()函数

Array.Index通过for循环来遍历数组，找到对应数组下标。时间复杂度O（n）。

找到后通过RemoveAt（index）方法来删除元素

RemoveAt里面用的是 Array.Copy 来拷贝数组，从index处之后的元素往前移一位。时间复杂度为O（n）线性时间。

4Insert 方法：

insert方法，引用Array.Copy方法，和java的Copy方法类似

public static void arraycopy(Object src,int srcPos, Object dest,int desPos,int length) 数组拷贝操作

第一个参数默认是src 来源数组类型为数组
第二个参数默认是srcPos 从来源数组开始复制的位置类型为整行（其实就是下标）
第三个参数默认是dest 目标数组类型为数组
第四个参数默认是destPos 目标数组接收起始位置类型为整行（其实就是下标）
第五个参数默认是length 复制的长度。

现在给出两个数组：
· 数组A：“1，7，9，11，13，15，17，19：；
· 数组b：“2，4，6，8，10”
两个数组合并为数组c

public class T5 {

public static void main(String[] args) {
int []a = {1,7,9,11,13,15,17,19};
int []b = {2,4,6,8,10};
int []c = new int [a.length+b.length];
System.arraycopy(a, 0, c, 0, a.length);
System.arraycopy(b, 0, c, a.length, b.length);
for (int i = 0; i < c.length; i++) {
System.out.print(c[i]+ " ");
}
}